-Flyぁ梦-

Java源码学习的第二个重点块，也是jdk中最有意义最有价值的一块，这里的集合类都是数据结构和算法，上手快学到的东西也多，而且在日常Java代码中出现率仅次于java.lang包。java.util中集合类必须是最重要的一块了，当然其他还有日期日历时区、货币、线程等工具类，不过这些类并没有太大的价值去精读。

java.util中的集合类整体，在javadoc中被称为Java Collections Framework，详细可wiki。

主要有以下线路：(I)表示接口，(A)表示抽象类

• (I)Iterable->(I)Collection->(I)List [ArrayList、LinkedList、Vector、Stack]
• (I)Iterable->(I)Collection->(I)Set [HashSet、LinkedHashSet、TreeSet]
• (I)Iterable->(I)Collection->(I)Queue [ArrayDeque、PriorityQueue]
• (I)Map [HashMap、LinkedHashMap、IdentityHashMap、TreeMap、WeakHashMap]
• (A)Dictionary->Hashtable
• BitSet、Arrays、Collections

List

ArrayList<E>

由数组实现的链表，每次调用add(E e)时调用ensureCapacity(size + 1)，可能导致元素数组扩容1.5倍。因为它是随机访问的（即实现RandomAccess接口），javadoc中表示使用for(int i = 0)的循环遍历会比Iterator遍历和foreach()循环快（foreach循环即Iterator遍历），这也在很多源码中体现出来若实例为RandomAccess的，会采取for循环来遍历。

LinkedList<E>

由结点链接而成的链表，API较多用来当做栈、队列、双向队列都可以。

Vector<E> 和 Stack<E> extands Vector<E>

Vector类似ArrayList，但是此为线程安全版本。小有区别的，每次需要扩容时元素数组扩容2倍。

Stack就是个线程安全的栈，没啥好说。

Queue

ArrayDeque<E> implements Deque<E>

由数组实现的双向队列（Deque接口）。这个类的代码实现有点意思的，元素数组大小一定是power-of-2，然后可以方便地使用位运算来判断长度溢出等。因为要保持数组容量的这个特性，数组扩容代码也挺有意思，有个简单的算法将某个数二进制中最高位1右边所有的位全部置为1，然后再+1，即得到了一个更大的power-of-2。

PriorityQueue<E>

由数组实现的优先队列，元素E必须实现Comparable接口或选择带有Comparator的PriorityQueue构造，因为在比较元素E时会强制转化类型为Comparable。看这个类的源代码可以好好复习下优先队列及满二叉树的实现。数组扩容的代码有点意思，当原容量<64时，扩容2倍，否则扩容1.5倍，综合ArrayList和Vector的扩容方案。

Set

set是Java Collections Framework最坑爹的实现了，因为它根本没有任何实现，所有的set都在内部保存有一个对应的map类型实例…

Map

map是Java Collections Framework最复杂的一块。

HashMap<K, V>

一般的Hash表实现，冲突机制使用在原位置接链表的方式。与教科书推荐的不太一样的是，桶的个数并不是推荐的质数个（据说这样可以减小冲突率）而是power-of-2，为的是通过位操作的代码高效实现。

• 默认加载因子是0.75，即75%的桶被沾满了就会扩容重新hash，每次double容量
• 冲突机制：接链表
• hash函数，static int hash(int h)，对元素E.hashCode()再进行一次hash，hash算法很复杂各种移位抑或操作，表示看不懂…
• 允许null键，而且null键必定位于0号位桶
• 键的比较采用Object.equals()方法（null键带有特判）
• foreach循环或Iterator遍历，按照桶的顺序（当一个桶有多个键时，按照插入顺序遍历）

Hashtable<K, V>

姑且算放在Map这里吧，主要可以和HashMap来个对比。算是线程安全的HashMap，但是相比来说代码没有HashMap优化的好。

Hashtable与HashMap的不同之处：

• Hashtable继承自Dictionary抽象类；HashMap继承自AbstractMap抽象类
• Hashtable的hash函数直接使用的E.hashCode()，使用取余操作；HashMap使用位操作并进一步hash
• Hashtable不允许null键，也不允许null值；HashMap都允许
• Hashtable中是contains()方法；HashMap是containsKey()或containsValue()
• Hashtable中由Enumerator来实现Enumeration和Iterator；HashMap则单由Iterator实现

LinkedHashMap<K, V> extends HashMap<K, V>

数据存储和读取和HashMap无异，但是多了一个链表来保存插入键的顺序。当foreach循环或Iterator遍历时，会按照这个链表来遍历。比较有意思的是，LinkedHashMap为后续提供了一个LRU容器的选择，可以自建个类继承自LinkedHashMap，重写protected boolean removeEldestEntry()然后return true。

IdentityHashMap<K, V>

对外而言这个Map与HashMap最大的不同在于比较Key用==操作符，其实内部实现有很大的区别。同样使用power-of-2大小的元素数组，但是没有用一个内部静态类去封装Key和Value，用偶数桶存放Key奇数桶存放Value，即每一项占用2个桶，然后冲突策略使用的index + 2策略，即冲突就往下一个最近的桶放。

• 冲突机制：开放定址法，并为线性探测；效率低、删除元素非常麻烦
• hash函数：对System.identityHashCode(E)继续一些位操作来得到hash值
• 允许null键
• 键比较采用==操作符
• foreach循环或Iterator遍历，按照桶的顺序
• OO封装不好，key、value连着放除了性能上很小的提升外没有啥优点

TreeMap<K, V>

由红黑树实现的Map，Key必须实现Comparable接口或选择带有Comparator的TreeMap构造。也是非常值得精读的一个类，不仅仅在于了解一下红黑树这个效率比较优秀的平衡二叉树的实现更在于对一般的二叉树这个数据结构和算法的掌握。为了看懂源码学习了一会儿红黑树，真心表示复杂，所以觉得大致了解红黑树就可以了无需看懂插入元素和删除元素的每一步操作这么具体。因为TreeMap是唯一实现SortedMap接口的Map，很多API的代码实现对二叉树的操作十分的美，特别是static successor()、static predecessor()、getCeilingEntry()、getFloorEntry()的实现很关键。

• 拒绝null键，因为键需要比较，但允许null值
• 树的重建，用最平衡的方法重建红黑树，递归则重建左子树、中间节点、右子树。而且红色节点计算很方便，最后一层（若没有满）则所有节点都是红色的（即保证所有的黑色节点为一棵满树）

WeekHashMap<K, V>

基本和HashMap一样，就是Entry的实现继承自WeakReference，key是弱引用，value是强引用。适用于元素量巨大，内存可能不足够用的时候，自动GC某些key并在下次访问Map时删除这些映射。适合作缓存，某些项突然消失也无关紧要的那种。

• Entry<K,V> extends WeakReference<K>，当GC工作时某些Key会被GC并放入WeekHashMap的ReferenceQueue中。每次对WeekHashMap的调用，会检查ReferenceQueue中已被GC的Key，然后找到那项Entry将里面的强引用Value给设置为null便于GC，并删除Map中对此Entry的引用，更新计数。
• 键冲突机制、hash函数、null键、键比较、遍历全部与HashMap相同

BitSet

使用long数组来实现的位向量，使用了大量位运算，值得一读。

Arrays

全静态方法的针对数组的工具类。主要提供了排序、二分搜索、复制、填充等功能。

排序方法中：

• 所有Java基础类型的数组排序使用QuickSort，在元素量<7时使用InsertSort。选取pivot有一定改进。
• 对double和float数组的排序有预处理，将NaN放到数组最后不参与排序，将-0.0d设为0.0d参与排序
• 对Java类型的数组排序使用MergeSort，在元素量<7时使用InsertSort。改进：当2个子序列a和b，max(a)<=min(b)则直接copy a和b至目标数组

Collections

全静态方法的针对集合类的工具类。主要提供排序、元素移位、封装集合为不可变集合、封装集合为线程安全集合、封装集合为类型检查集合等功能。

所有的集合封装方法，都是将传入的集合封装一层类，然后在外层提供的API中拒绝修改方法（抛出UnsupportedOperationException）、提供线程安全（synchronized关键字）、检查插入类与泛型类来实现。

综合

• 所有的集合类都有modCount这个field，它的作用是记录集合实例被改变的次数，特别是调用Iterator时这个modCount会被保存副本，在遍历过程中若发现集合实例被修改（即副本modCount与集合类实例的modCount不相等），立即停止遍历并抛出异常，即javadoc中提到的iterator 和 listIterator 方法返回的迭代器是快速失败的。
• Map和Set中支持KeySet、ValueSet、EntrySet这些方法，返回的Set并不是一个独立的Set，内部无任何元素只有一个指向原来集合实例的指针（内部类），所以一般只用来作遍历用，如果修改这些Set会同步地修改原来集合实例。
• 所有的集合类实现了java.lang.Cloneable接口，从而支持clone()方法，然后又全部重写clone()方法，集合实例的确被clone了，但是内部包含的所有集合元素只是copy了引用，而没有完整copy一份（当然因为元素本身不一定实现了Cloneable不能被clone），因为本质只是调用了System.arraycopy()而已。

感想

• 大多数集合类的实现其实一点都不难，慢慢改进调试我们也写得出来
• 有很好的OO思想直接体现在整个Java Collections Framework的层次结构设计，是值得学习的
• Iterator思想也是很值得学习的，因为这一点也许接触地更少
• 也许算Java语言的一个无奈之处，因为基础类型没有共同可替代的方式，所以针对基础类型的方法全部要重载一遍，而不像针对类类型只要写一个Object版本就可以。这导致基础类型的方法中，比如System.out.println()，比如Arrays的所有方法，代码大量冗余重复，这是非常不美的地方啊，不知道以后的Java会不会改进