转自http://www.cnblogs.com/mengheng/p/3669463.html
Java2中的集合框架是广为人知的，本文打算从几个方面来说说自己对这个框架的理解。
我们常说要继承的话，到底是写个抽象类还是接口，它们区别在于：如果子类确实是父类的一种，应该使用抽象类，描述是“is-a”的关系，而接口则表示一种行为，描述的是“like-a”的关系。但在Java类库里，其实许多原则由于各种原因被打破了，比如在Collection框架里，List/Set都是Collection的一种，为什么不把Collection定义为抽象类呢？而ArrayList/LinkedList也都是List的一种，为什么不把List定义为抽象类呢？这就是原则和实际的折衷。作为Java类库而言，不仅要考虑面向对象的一些原则，也要考虑扩展性和语言本身的限制。能不能把Collection接口去掉，用AbstractCollection作为顶层？作为类库而言是不可以的，因为Java是单继承的，如果把AbstractCollection作为顶层，那么当用户自定义的类既要继承自己的父类，又要具备集合的属性，那么就做不到了(可以自定义集合接口，但就无法与Collection相互转化)。因此，Java集合框架采取的是类库广泛使用的接口+抽象类的形式，以同时获得接口和抽象类的好处，所以我们看到ArrayList extends AbstractList implements List(AbstractList本身就是实现List的，这里再写出implements List是为了使ArrayList的类结构更为清晰)。
另外我们再看Set接口，它的方法基本和Collection方法一模一样，为什么要再写一遍？一方面是作为类库而言要增加详细注释，虽然是同名的方法但实现的约束不同，比如Set的add方法是不会保存重复值的，另一方面是为了从Set接口本身能很清楚地看到它所提供的功能(比如size()方法，和Collection是完全一个含义，也重新定义了一遍)，这是从类库易读性来考虑，对于我们自己编写的类，基本就不需要这样。
说多了，回到集合框架本身。
Iterable基本是个标识接口，同时约定了所有线性集合(数组、队列、栈这种一维的都属于线性集合，Map就属于二维，不要求遍历)必须是可以遍历的(集合要给出遍历结构)，同时提供了配套的Iterator顶级接口，实现hasNext()、next()和remove()方法来完成遍历功能。为什么这里要定义remove接口方法却不定义add/set方法？个人觉得这可能是考虑在类库的使用过程中remove的频率更高，而add的方法频率要低，set的使用场景就更少了。
ListIterator相比Iterator就多提供了很多功能，包括上面提到的add/set，还有获得索引的nextIndex、previousIndex、以及往回迭代的hasPrevious()/previous()。给针对线性表的操作者更多的便利，事实上在AbstractList里就提供了iterator()和listIterator()两种方法来提供给开发者更多选择。相应的，在HashMap里头，也提供了实现Iterator接口的HashIterator内部抽象类，而在Apache Commons Collections下甚至单独写出MapIterator extends Iterator，由此可见，作为类库的设计者，在Iterator和ListIterator/HashMapIterator上是做了便捷性/易用性以及使用场景上的权衡的。
ArrayList内部结构是个数组，默认是10，在创建ArrayList对象时此数组是空的(Object[] EMPTY_ELEMENTDATA = {})只有当add的时候才扩容(如果扩容容量小于DEFAULT_CAPACITY,也就是10，就一次性扩容到10)。其扩容的机制是：当前数组容量已经无法放入更多元素的时候，增加原有数组的一半，
intoldCapacity = elementData.length;
intnewCapacity = oldCapacity + (oldCapacity >> 1);
if(newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if(newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
此数组的最大值是Integer.MAX_VALUE，也就是2^31-1。数组扩容的时候要考虑到当容量再度扩容一半的时候会越界，所以单独做了判断处理。数组扩容是在调用了本地方法去分配新的空间区域(下面是Arrays.CopyOf的代码)
publicstaticint[] copyOf(int[] original,intnewLength) {
int[] copy =newint[newLength];
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
returncopy;
}
System.arraycopy的代码如下
publicstaticnativevoidarraycopy(Object src,intsrcPos,
Object dest,intdestPos,
intlength);
按照理论上来说，对于能预先知道数组大小的，应该在定义ArrayList的时候指定其容量以减少扩容次数，但是经过以下代码试验(虚拟机64位Client模式，JDK1.7.0_45)
inttimes=1000000;
longstartTime=newDate().getTime();
List arrayList=newArrayList(times);
for(inti=0;i
arrayList.add(i);
}
longendTime=newDate().getTime();
System.out.println("ArrayList增加"+times+"次,耗费时间="+(endTime-startTime));
对于1百万次增加，使用new ArrayList(times)时耗费时间是90ms，而使用new ArrayList()的耗费时间竟然要短一些，只要81ms；把times扩大到1千万的时候，差距更明显，指定容量的要5秒多，而不指定容量的只要3秒多。具体是哪慢了不好下结论，推测应该是当实际元素较少的时候，大数组在寻址、计算等方面要慢一些，反过来说System.arraycopy的效率并没有传说中的那么低，这也是为什么用的本地方法的原因。
LinkedList我们知道内部结构是个线性链表，首先看它继承的不是AbstractList，而是继承自AbstractSequentialList，这是AbstractList的子类，实现了线性链表的骨架方法，如get/set，均是通过ListIterator迭代器来遍历实现。为什么要创造出AbstractSequentialList这个类？因为线性的不只有链表，但线性的都只有通过迭代器才能找到元素，与之对应的是随机读取——也就是数组，因此在AbstractSequentialList的类注释里明确说明：如果是随机读取的，则使用AbstractList更合适(AbstractList并没有提供随机读取的实现，类注释的意思只是说如要随机读取，则AbstractSequentialList没有任何帮助，不如实现AbstractList更准确)。事实上，为了表明集合是否可以根据索引随机读取，Collection框架专门定义了一个空接口RandomAccess，以标识该类是否可随机读，ArrayList、Vector都实现了这个接口，而没有实现这个接口的，则是不可以通过下标索引来寻址的。
LinkedList有比ArrayList在接口上有更丰富的功能，比如addFirst()、addLast()、push()、pop(),、indexOf()，同时它的listIterator()也要比iterator()更常用一些。我们以前常说对于经常删除、增加的集合，使用LinkedList比ArrayList效率要高，这是容易被误解的，LinkedList的寻址相比数组来说非常地慢，如果在频繁增/删之前需要寻址定位，那么仍然比ArrayList要慢很多，数十倍地慢，所以使用它的时候要谨慎，不能耍小聪明。LinkedList根据索引寻址的get(int index)方法，使用的是简单的“二分法”，即如果index小于size的一半，则从前往后迭代；大于size一半则从后往前迭代。这也是没有办法的事情，LinkedList是需要保证插入顺序的，所以不能做任何排序，也就不能使用任何如冒泡、快速排序之类的算法。有没有不需要保证插入顺序从而能够快速寻址的集合呢？TreeSet/HashSet可以快速寻址，但不能有重复值；TreeMap/HashMap同样是不能有重复值；Collection框架并没有给出能有重复值同时又能允许排序的List，应该是他们认为ArrayList就可以满足这种场景了，但类库中有个类IdentityHashMap，它的hash()方法用的是System.identityHashCode()而不是HashMap所用的key.hashCode。System.identityHashCode()意思是不管对象是否实现了hashCode，都取Object的hashCode也就是对象的内存地址来作为key，这样即使两个对象hashCode相等，也会被重复插入(在该类的注释中说到了它的一些使用场景，有兴趣的可以仔细看下)。
我们知道通常的集合都是非线程安全的，表现在多个线程同时增/删时，集合大小会不可预测，同时Iterator尽量保证在迭代过程中操作是安全的(不保证准确，但尽量保证不会有越界问题)，即当某线程迭代读取集合时，如有其他线程修改此集合的结构(扩大/缩小)，则会抛出ConcurrentModificationException。那么它是如何实现的呢？在集合中都会维护一个内部计数器modCount，如果有影响集合结构的操作(增加、删除、合并等，而修改不是)，modCount都会自增1。在对集合迭代时，都会检查当前迭代时的操作计数器副本expectedModCount(迭代前初始化为和modCount相等)和modCount是否相等
intexpectedModCount = modCount;
finalvoidcheckForComodification() {
if(modCount != expectedModCount)
thrownewConcurrentModificationException();
}
同样，Set、Map(获得Entry的HashIterator迭代器)中都有modCount这样的操作计数器。
Set用的相对少一些，同时它基本是依托于Map实现的。HashSet依托于HashMap，TreeSet依托与TreeMap，所以先从Map说起。
都知道Map是不继承自Collection的，是顶级接口，为什么这么设计？从根本上来说，Collection是一维的，而Map是二维的，那么是否存在三维的？j2se并没有提供这样的类库，但google的guava框架提供了这样的，如com.google.common.collect.Table，其中R是行key、C是列key，而V就是对应的值，也就是说j2se类库考虑的情况会比较多，而各开源框架就可以根据自己的定位设计出更专业化的类库。
Map接口的方法和Collection差不多，不过从键的维度、值的维度以及把键值作为一个整体的维度，有了keySet()、values()、entrySet()这样的接口方法。
Map提供了抽象类AbstractMap，使用entrySet的迭代器循环，提供如get、remove、containKey这样的默认实现。为什么Map不实现Iterable接口呢？我觉得没有必然的原因，Map实现Iterable接口也无不可，本身它内部就有以entrySet的Iterator来做遍历的使用，只是作为Map这样的结构来说，实现Iterable有些混淆，到底是迭代K呢，还是迭代V呢，或者是迭代整体？所以干脆Map本身就不提供迭代器，而是提供了分别按键、值、键值对三个迭代器接口。
HashMap也就是哈希表，我们都知道它内部是一个数组链表的结构，即一个数组，
transient Entry[] table = (Entry[]) EMPTY_TABLE;
其中放的是Entry对象的引用，而每个Entry内部又维持hash相同的下一个Entry引用形成链表。
staticclassEntry implements Map.Entry {
final K key;
Vvalue;
Entry next;
inthash;
Entry(inth, K k, V v, Entry n) {
value= v;
next = n;
key = k;
hash = h;
}
同List一样，在其内部也维护叫size的变量，保存元素个数。在new HashMap()的时候，table数组是空的，一旦put则会扩容，
privatevoidinflateTable(inttoSize) {
// Find a power of 2 >= toSize
intcapacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table =newEntry[capacity];
initHashSeedAsNeeded(capacity);
}
初始扩容的容量是16
staticfinalintDEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
，在扩容的过程中同时会计算下次扩容的阈值threshold，它=数组大小*负载因子。为什么在达到threshold的时候扩容而不是在达到数组最大长度的时候？这是为了减少每个数组元素上的Entry数，因为根据hash()方法，在把table数组占满之前，很可能在其他元素上已经有多个了(从概率角度)，但负载因子又不能太小，否则会造成很多空间浪费，所以作者权衡(这里可能也是根据hash()或某些数学原理)取0.75作为负载因子，即达到table数组3/4时就扩容，并且是扩容2倍，不是ArrayList那样扩容一半
voidaddEntry(inthash, K key, Vvalue,intbucketIndex) {
if((size >= threshold) && (null!= table[bucketIndex])) {
resize(2 * table.length);
hash = (null!= key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key,value, bucketIndex);
}
其原因和hash的算法有关。为了提高效率，在HashMap里大量使用了&、>>>这样的二进制运算，比如HashMap初始化是1<<<4，在用hashCode在table数组中取模求余时用的是hashCode&table.length-1
staticintindexFor(inth,intlength) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
returnh & (length-1);
}
所以数组大小保持是2的倍数，才能使用这些快速的二进制方式。
关于上面indexFor我们可以用两组数来算下：
假设hashCode是17，数组长度是7，那么就是10001&00110=00000，而正确结果是17%7=3；假设数组长度是8，那么就是10001&00111=00001，与正确结果17%8=1相一致。所以保持数组长度是2的倍数，就是为了提高HashMap的效率所做的一个小技巧，同时在内存分配上等都要更快一些。
在根据key来定位其hashCode的时候，并不是简单调用key.hashCode()，而是再度进行了一些运算，其目的是为了使最终哈希出来的值更均匀，
finalinthash(Object k) {
inth = hashSeed;
if(0 != h && k instanceof String) {
returnsun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
returnh ^ (h >>> 7) ^ (h >>> 4);
}
至于为什么这么做，比较复杂，我也没搞太清，尤其是其中为什么选择20、12、7、4这样的来右移。还有hashSeed的选择也不太清楚。
这里必须要提下HashMap扩容的效率问题。前面提到ArrayList的扩容性能并不差，而HashMap就完全不一样了，经实验，扩容至少带来性能下降1半以上，但有临界点，元素超过10万数量级差距就不明显了。下面是代码和测试结果
import java.util.Date;
import java.util.HashMap;
import java.util.Map;
publicclassResizePerformanceTest {
publicstaticvoidmain(String[] args) {
run(1000);
run(10000);
run(100000);
run(1000000);
run(10000000);
}
publicstaticvoidrun(inttimes) {
System.out.println("增加"+times+"次");
longstartTime=newDate().getTime();
Map map=newHashMap();
for(inti=0;i
map.put(i, i);
}
longendTime=newDate().getTime();
System.out.println("HashMap自动扩容的方式,增加"+times+"次,耗费时间="+(endTime-startTime));
longstartTime1=newDate().getTime();
Map map1=newHashMap(times);
for(inti=0;i
map1.put(i, i);
}
longendTime1=newDate().getTime();
System.out.println("HashMap预先指定空间的方式,增加"+times+"次,耗费时间="+(endTime1-startTime1));
}
}
增加1000次
HashMap自动扩容的方式,增加1000次,耗费时间=2
HashMap预先指定空间的方式,增加1000次,耗费时间=1
增加10000次
HashMap自动扩容的方式,增加10000次,耗费时间=15
HashMap预先指定空间的方式,增加10000次,耗费时间=6
增加100000次
HashMap自动扩容的方式,增加100000次,耗费时间=25
HashMap预先指定空间的方式,增加100000次,耗费时间=21
增加1000000次
HashMap自动扩容的方式,增加1000000次,耗费时间=1707
HashMap预先指定空间的方式,增加1000000次,耗费时间=1611
增加10000000次
HashMap自动扩容的方式,增加10000000次,耗费时间=21054
HashMap预先指定空间的方式,增加10000000次,耗费时间=17820
HashMap大约就说这么多，再说说TreeMap。TreeMap是种红黑树的结构，能够对元素排序(红黑树、数据库的B树、B+树，还有冒泡算法、快速排序算法这些算法领域的，现在还真是不那么掌握牢固)。为了保证排序，提供了两种方式：一种是Key对象实现Comparable接口，另外一种方式是单独提供Comparator实现类
publicTreeMap(Comparator comparator) {
this.comparator = comparator;
}
如果本身Key对象的排序是确定的，比如Integer按大小排序，String按照字典排序，这些是无疑义的，所以它们都实现了Comparable接口，但假如说Person对象，有时需要按年龄排序，有时需要按身高排序，有时需要按薪酬排序，所以就没办法使用Comparable接口了，此时可以根据不同排序方式创建相应的Comparator类。
既然是按照顺序排列的树，那自然就需要提供一些数据结构方面的方法，所以TreeMap有了firstKey()、lastKey()、pollFirstEntry()、lowerEntry(K)、floorEntry(K)、headMap(K)、tailMap(K)、desendintMap()这样的方便方法。
相比HashMap，TreeMap还有个很大的不同，就是它不仅是继承AbstractMap，还实现了NavigableMap，NavigableMap继承自SortedMap，SortedMap继承自Map。SortedMap定义了什么？firstkey()、lastKey()、headMap(K)、tailMap(K)、subMap(K,K),NavigableMap定义了pollFirstEntry()、lowerEntry(K)、floorEntry(K)等方法。为什么这么设计？SortedMap是好理解的，针对可以排序的Map单独设一个接口，但为什么要NavigableMap呢？它的lowerEntry(K)之类的方法为什么不能合并到SortedMap里去？个人觉得这应该是两个版本时期导致的，NavigableMap是JDK1.6时加入的，此时已经有了不少SortedMap的子类，不是很有必要让子类也去实现这些方法，所以新加了个NavigableMap类，在需要lower的时候实现它即可，不需要时就直接实现SortedMap。也就是设计这种类库接口时的粒度问题，基本的方法在上一级接口定义，虽然另外一些方法也是正常使用，但根据它的频率、约束性有所不同可以下放，同时又要考虑不能使接口数量太多加大复杂性。
理解了Map，再来看Set就很简单了。HashSet内部完全是以Set元素为key，new Object()为value的HashMap
// Dummy value to associate with an Object in the backing Map
privatestaticfinal Object PRESENT =newObject();
它的一些如size()、contain()方法都是直接调用map的方法。
publicintsize() {
returnmap.size();
}
publicboolean add(E e) {
returnmap.put(e, PRESENT)==null;
}
TreeSet也是一样，且也有相配套的NavigableSet、SortedSet。
从整体来说，感觉Set设计地不是太好，其大多数功能和List很像，仅非重复这个频率并不高的场景不足以单独列这一套接口，而其实现上又基本上完全依托于Map。如果开发者真有这种场景，完全可以自行用HashMap来代替。
集合框架中还有两个很有用的辅助类，分别是Collections和Arrays，这两个就不多介绍了。Collections提供了一系列synchronized集合、unmodified集合以及很少用的Checked集合(类型检查的)，以及toArray(toArray(T[] a)更好用，因为能指定返回数组的元素类型)、binarySearch(快速查找算法，需要参数列表元素能排序，否则结果就不准确)。而Arrays提供了一些如sort、merge、binarySearch、copyOf、asList这样有效的方法，注意这里的asList返回的Arrays内部实现的一个ArrayList，有些方法不支持，比如add、remove，除了set之外基本上就是一个只读列表，如果需要可add/remove，还是需要使用集合的相应构造函数或者Collections的copy方法)。
最后两个需要说的是虽然是在java.util根目录下，但基本是为java.util.concurrent准备的，就是Queue(队列)和Deque(双向队列)。Queue的一系列子类如DelayQueue、LinkedBlockQueue更多地是和并发有关，这放到将来的JUC框架时再讲吧。
