第九章 集合

9.1 Java集合框架

在Java类库中，集合类的基本接口是Collection接口。

访问集合元素时，使用“for each”循环编译器会将其翻译成带有迭代器的循环。

元素被访问的数据取决于集合类型，对于ArrayList进行迭代就会按顺序得到元素。

而访问HashSet的元素则会获得一个随机的元素序列。

对于C++而言，迭代器就是直接指向元素的，而对于Java而言，迭代器是夹在元素之间的，每调用一次next方法就返回一个刚刚越过的元素。

Iterator接口的remove方法是删除上一次调用next返回的元素，打个比方说就是如果要删除第一个元素，要先调用一次next方法，此时再调用remove就会删除第一个元素。

9.2 具体的集合

ArrayList是数组列表，LinkedList是双向链表。

对于链表而言，如果向一个指向链表表头的迭代器调用add方法，新增加的元素会变成列表的新表头。若迭代器越过了最后一个元素，此时调用add方法就会向表尾新增元素。如果链表有n个元素，有n+1个位置可以添加新元素。

为避免迭代器变成无效，应该只设置一个可读可写的迭代器，其他迭代器仅可读。

LinkedList的get方法有一定的优化，比如传入的索引大于长度的一半就会从尾部开始搜索元素。

Iterator接口为了抽象在有序集合和无序集合之上，如add方法仅对于有序集合才有意义，因此在Iterator接口中并没有add方法，但在它的子接口ListIterator中就有这个方法了。

动态数组可以使用ArrayList或者Vector，但是Vector的所有方法是同步的，会产生相应的开销。所以在不需要同步时应用ArrayList。

HashSet是一个基于散列表的集合。

TreeSet是一个有序集合，可以以任意顺序将元素插入集合，但遍历时会得到一个有序序列。

优先队列采用了堆实现，它是一个可以自我调整的二叉树，对树进行添加和删除操作时可以让最小的元素移动到根。

9.3 映射

散列映射HashMap对键进行散列，树映射用键的整体顺序对元素进行排序，并将其组织成树。

散列或比较函数只能作用于键。散列映射相比树映射不需要排序，建立映射更快。

对一个键调用两次put方法，后一次的值会覆盖前一次的值。put有返回值，就是上一次该键存储的值。

entrySet是键值对集视图，集中可以删除但不能新增。

LinkedHashMap链接散列映射可以采用访问顺序而不是插入顺序对映射条目进行迭代。每次调用get或put时受到影响的条目将从当前位置删除并放到条目链表的尾部。

9.4 视图和包装器

Arrays.asList方法返回的对象并不是ArrayList，而是一个视图对象。

视图只包装了接口而不是实际的集合对象，只能访问接口中定义的方法。

9.5 算法

二分查找binarySearch若返回负数，代表该元素未找到。返回值的相反数再-1则是查找值应该插入的位置。

集合转数组时使用的toArray方法得到的是一个对象数组，而且不能对其直接强转。相反，应该是在toArray的参数中传入所需类型且长度为0的数组。

Properties类实现了Map接口。