上篇文章对数组做了初步整理，这篇文章主要说容器（也有一种说法叫集合类）。java.util包里有很多工具类，有事件模型方面的（如Observable、EventObject），有时间日期处理的（Date、Calendar）、也有随机数工具（Random）等，最重要的一部分还是容器类（Collection接口、子接口以及各类实现）。在java.util.concurrent子包中也有和并发相关的容器类（集合类），这里先不讨论。
对于java.util中的容器类（集合类），内容较多较杂，大致关系如上图，详细的整理和总结如下。
0. 从总体上来看，分两大类，Map和Collection。而Collection又有子接口List、Set（虽然像Set实际上和Collection的接口是等同的）、Queue 。Collection为了能够以一种高度抽象的更通用的方式给开发者使用，能够容纳下各种实现，里面声明了很多方法，尽管很多方法在具体实现中是不支持的操作。
1. 对于List主要有ArrayList和LinkedList两种实现。实现的数据结构不同，所以主要的区别也都是和数据结构相关的。ArrayList基于数组，随机访问快，而对于中间元素的插入删除效率比较低，而且需要考虑扩容问题。LinkedList，则基于链表，和ArrayList提到的正相反，随机访问慢，但对于中间元素的插入和删除更有效率。还有就是LinkedList实现了Deque(扩展了Queue，这个貌似是1.6才加的)，提供了更丰富的方法。
2. 对于Queue，主要有LinkedList和PriorityQueue，后者的顺序与比较器有关，优先级队列的实现基于堆算法。
3. Set和Map，这两个要放在一起说，因为常用的三类Set(HashSet、TreeSet、LinkedHashSet)都是基于Map实现的（至少在SunJDK中是这样的，下面的一些描述也都是根据Sun的实现来的，其它厂商对JDK的实现原则上是可以不同的），Set使用的是Map的keySet，value是一个名为PRESENT的Object对象。
Set也是一种Collection，和List比起来主要体现在元素唯一性。
对于Hash的实现，用的是散列方案，特点就是存取快性能好，所以通常是默认选择。散列表底层是基于数组的，数组索引（通俗点的说法有叫“数组下标”的）通过hash方法得来，这个与hashCode有关，即通过hashCode进行一系列位运算。此外，hashCode也影响Hash实现中的“唯一性”，如两个放入Set/Map(key)中的对象hashCode不同，则会被认为是不同的对象(优于equals方法先考虑)，会都存入容器中。所以，这个要注意放入Hash实现的容器中的对象，类要考虑重写hashCode()，因为Object的默认实现与内部地址有关，默认每new一个对象实例，hashCode()都有所不同，这在很多场景下是不适合需求的。关于hash和equals的后续再详细小结下。对于hash索引造成的散列冲突，sun jdk的实现采用（开散列）链表方案，当然冲突后的查找是在链表中效率比较低，所以要考虑尽量冲突避免，这与容量、装载因子有关，hash的扩容通过直接双倍实现，扩容后复制对象并重新做hash。
对基于Tree的实现，特点是有序，提供了更丰富和顺序有关的工具方法集。需要注意的是，放入Tree实现的容器中的对象，要实现Comparable接口，否则会出异常。更详细的实现细节后续参看实现源码做小结。
而LinkedHashSet和LinkedHashMap则是在基本的Hash实现的基础之上加了双向链表，维护了插入或访问的顺序。当构造LinkedHashMap对象时，如果对记录访问的参数设置为true，则LinkedHashMap中链表将维护访问顺序（而非插入顺序），访问顺序的记录采用LRU算法。更详细的实现细节后续参看实现源码做小结。
4. 和Arrays类似，Collections提供了丰富的方法，并且用法和Arrays的基本相同，其中shuffle()、sort()、binarySort()都是对List支持的很好的方法，sort的实现基于Arrays类中的排序算法。可参见对数组进行整理介绍的上篇文章。
5. 和比较相关的接口类似，为了方便对容器类对象的遍历，更抽象更通用地使用容器类对象，还有迭代器这样一个概念。和Collection紧密配合的有这样几个迭代相关的接口java.lang.Iterable、java.util.Iterator和java.util.ListIterator 。
其中Iterable很简单，只有一个方法iterator()，即能生成一个相关的迭代器，Collection扩展了这个接口。为了能满足特定类有多种迭代方式，可以用特定方法生成并返回Iterable类，实现适配。
Iterator则要求有hasNext()、next()、remove()方法。这个对于容器类要注意remove和现成安全问题的关系，后面文章会详细说。
ListIterator是一个增强的Iterator，除了3个方法外，还支持previous()等，功能更强大。AbstractList对Iterator和ListIterator都有分别的实现。
Iterable是1.5中才有的，一个目的就是为了和“foreach”结合使用。需要注意的一点就是，数组和实现Iterable的类都可以foreach。但数组不是Iterable。
关于迭代器相关的fail-fast，后文给出小结。
6. 其它和容器相关的杂项
本文的内容大部分是本人实践总结，主要参考了Oracle/Sun JDK 1.7.0_21的源码。关于hashCode()和equals()、上述容器类线程安全考虑、java.util.concurrent中并发容器类以及java.util容器类的实现源码分析等内容会在后面的文章中做一些整理。
联系客服
