Java核心技术知识点笔记—集合（二）

1、树集（TreeSet）：是一个有序集合（sorted collection），与散列集类似，但比散列集有所改进。

（1）可以以任意顺序将元素插入到集合中；

（2）遍历时，每个值将自动按照排序后的顺序呈现；例如：

        TreeSet<String> treeSet = new TreeSet<>();treeSet.add("B");treeSet.add("A");treeSet.add("C");for (String s : treeSet) {System.out.print(s);System.out.print(",");}}

输出：A,B,C,

（3）排序使用的是树结构（当前使用的是红黑树（red-black tree）），每次插入一个元素，元素都被放置在正确的排序位置上；

（4）迭代器总是以排好序的顺序访问每个元素；

（5）将元素添加到树中比添加到列表中慢，但与检查数组或链表中的重复元素比快很多；

（6）树的排序必须是全序，即任意两个元素必须是可比的，且只有当两个元素相等时结果才为0；

（7）Java SE 6起，TreeSet类实现了NavigableSet接口，这个接口增加了几个便于定位元素以及方向遍历的方法。

2、队列与双端队列：

2.1、双端队列：有两个端头的队列，可以有效地在头部和尾部同时添加或删除元素，不支持在队列中间添加元素。

（1）Java SE 6 中引入Deque接口，并由ArrayDeque和LinkedList实现。这两个类都提供了双端队列，并且可在必要时增加队列长度。

2.2、优先级队列（priority queue）：可按照任意顺序插入元素，但总按照排序的顺序进行检索。

（1）并没有对所有的元素进行排序；

（2）使用的数据结构称为堆（heap）；

（3）堆是一个可以自我调整的二叉树，对树执行添加和删除操作，可以让最小的元素移动到根，而不必花费时间对元素排序；

（4）典型示例：任务调度。每个任务有一个优先级，任务以随机顺序添加到队列中。每当启动一个新任务，都将优先级最高的任务从队列中删除（由于习惯上将1设为“最高”优先级，所以会删除最小的元素）。

3、映射：存放键/值对，提供键就能查找到值。Java中提供了两个通用的实现：HashMap和TreeMap。

3.1、基本操作

（1）散列或比较函数只能作用于键，与键关联的值不能进行散列或比较。

（2）与集一样，散列稍微快一点。如果不需要按照排列顺序访问键，最好选择散列。

（3）往映射添加对象时（put方法），必须提供一个键。

（4）检索对象（get）必须使用键。如果映射中没有与给定键对应的信息，get将返回null（getOrDefault方法可以让调用者自己提供一个默认值，如果检索没有结果，则返回提供的默认值）。

（5）键必须是唯一的。不能对同一个键存放两个在值。重复对同一个键调用put方法，后面的值会覆盖前面的值。

（6）要迭代处理映射的键和值，最简单的方式是使用forEach方法，提供一个接受键和值的lambda表达式。

（7）remove方法删除映射中给定键对应的元素；

（8）size方法返回映射中的元素数目。

3.2、三种映射视图：键集（Set<K> keySet()）、值集合（Collections<V> values()，不是一个集）、键/值对集（Set<Map.Entry<K, V>> entrySet()）。

（1）keySet()不是HashSet或TreeSet，而是实现了Set接口的某个类的对象，扩展了Collection接口，可以像使用集合一样使用。例如：

枚举一个映射的所有键：

        Set<String> keySet = map.keySet();for (String key : keySet) {System.out.println(key);}

（2）在键集视图上调用迭代器的remove方法，实际会删除映射中这个键以及与它关联的值；

（3）不能向键集视图增加元素。试图调用add方法会抛出UnsupportedOperationException。

（4）通过枚举键/值对集来同时查看键和值：

       for (Map.Entry<String, String> entry : map.entrySet()) {System.out.println("key: " + entry.getKey());System.out.println("value：" + entry.getValue());}