第九章 集合
循环数组是一个有界集合，容量有限。如果程序中要手机的对象数量没有上限，就用链表实现
集合框架
迭代器
next方法和remove方法的调用具有互相依赖性。next的返回值可以被remove掉。
具体集合
| 集合类型 | desc |
|---|---|
| ArrayList | 一种可以动态增长和缩减的索引队列 |
| LinkedList | 可以在任何位置进行高效的插入和删除操作的有序队列 |
| ArrayDeque | 循环数组实现的双端队列 |
| HashSet | 没有重复元素的的无序集合 |
| TreeSet | 有序集 |
| LinkedHashSet | 可以记住元素插入次序的集 |
| HashMap | 存储键值 |
| TreeMap | 键值有序排列的映射表 |
| LinkedHashMap | 可以记住键值添加次序的映射表 |
| WeakHashMap | 值不被使用可以被回收的映射表 |
链表
链表的迭代器next或previous后，指针的位置add会在当前位置，而set会在开头。
- 一个迭代器对集合进行修改，另一个进行遍历，会出现报错。（并发中）
- 如何检测到并发修改：集合可以跟踪改写操作的次数，每个迭代器维护一个独立的计数器，在每个迭代器方法的开始出检查自己改写操作的计数值是否与集合的改写操作技术之一致，不一致则报错。
- 链表不支持快速随机访问，如果要查看第n个，必须从头开始，无捷径可走。
散列集
java中，散列表用数组实现，每个列表被称为桶，要想查找表中对象的位置，就要写计算他的散列码，然后和桶的总数取余，所得到的结果就是保存这个元素的桶的索引。遇到桶被占用的情况，成为散列冲突。
装填因子
决定了合适对散列表进行再散列，例如，如果装填因子为0.75默认值，而表中超过75%的位置已经填入了元素，这个表就会用双倍的桶数自动的进行再散列。
Treeset
是一个有序集合，排序是用红黑树实现的。
优先级队列（PriorityQueue）
元素可以按照任意的顺序插入，却总是按照排序的顺序进行检索。使用了一个优雅且高效的数据结构，称为堆，堆是一个可以自我调整的二叉树，对树执行添加和删除操作，可以让最小的元素移动到根。
最近最少使用原则
-
访问顺序
每次调用get或put，受到影响的条目将从当前的位置删除，放到链表的尾部。LinkedHashMap实现了这样的散列映射表。
利用访问顺序实现。希望将访问频率高的元素放在内存中，而访问频率低的元素从数据库读取。当在表中找不到元素且表已经满了，可以将枚举的前几个元素删除掉。
重写protected boolean removeEldestEntry(Map.Entry<K,V> eldest)方法，每当方法返回true，就添加一个新条目，从而删除eldest条目。
标识散列映射
IdentityHashMap.Class有特殊作用，这个类中，键的散列值并不是用hashCode函数计算，而是通过System.identityHashCode计算，这个方法根据对象的内存地址来计算散列码时使用的方式，而且，在两个对象进行比较时，用==而不是equals，不同键的对象，即使内容相同，也被视为不同的对象。