一：框架图
二：框架分析
（0）点线框表示接口，实线框表示具体的类。
（1）常用的List、Set、Queue、Map都属于集合类。前三个都是继承自Collection，但是Map不是。
（2）List不仅可以生成普通的Iterator（因为继承自Collection），还能生成ListIterator。
（3）常用的类ArrayList、LinkedList、HashSet、HashMap。这几个类请好好研读JDK源码
（4）其它需要好好掌握的容器：CopyOnWriteArrayList、TreeSet、TreeMap、HashTable、LinkedHashMap、ConcurrentHashMap。
三：容器分析
（1）ArrayList
（1.1）底层使用一个Object数组来实现。get和set操作基于这个数组。
（1.2）List在遍历的时候，如果被修改了会抛出java.util.ConcurrentModificationException异常。
（2）LinkedList
底层采用采用一个first和last的Node<E>节点，通过链表来实现。
（3）Hashmap
（3.1）底层采用Node<K,V>[] table 的数组+链表的形式来实现。
（3.2）key和value都可以为NULL。
（3.3）是线程不安全的。
（4）HashSet
底层采用HashMap来实现。
其中value使用private static final Object PRESENT = new Object()来表示。
（5）CopyOnWriteArrayList
（5.1）底层数据结构
final transient ReentrantLock lock = new ReentrantLock();
private transient volatile Object[] array;
（5.2）基本操作
get(int index)操作直接取数组对应的元素。
set(int index, E element) 操作按如下步骤：
- 调用lock.lock()
- 取index处对应的元素oldValue
- 如果oldValue和element不等，则复制原数组，然后设置index处的值为element，最后原数组指向新数组。
- 如果相等，原数组还是指向原数组。
- lock.unlock()
（6）TreeMap
（6.1）继承自AbstractMap<K,V>，实现了NavigableMap<K,V>
（6.2）底层使用红黑树实现，有一个比较器来比较元素的排列顺序，元素是有序的。
（6.3）key不能为NULL，value可以为NULL。key不能为null是因为key之间需要比较大小。
（7）TreeSet
底层使用TreeMap来实现。
（8）HashTable
（8.1）put和get方法都用synchronized修饰
（8.2）底层是Entry<?,?>[] table，也是数组+链表的形式来实现。
（8.3）put操作中会检查value是否为null，是则抛出NullPointerException。put操作中会调用key.hashCode()，所以key不能为null。综上，key和value都不能为null。
（9）LinkedHashMap
（9.1）继承自HashMap，增加了一个额外的双向链表维护key插入和访问的有序性。
（9.2）内部的Entry<K,V>基础自HashMap.Node<K,V>，并增加了两个节点： Entry<K,V> before, after。
（9.3）包含LinkedHashMap.Entry<K,V> head和LinkedHashMap.Entry<K,V> tail。
（9.4）key和value都可以为null。
（10）ConcurrentHashMap
（10.1）JDK6和JDK7中采用分段锁的设计。采用segment数组和HashEntry数组的数据结构组成，segment是一种可重入锁ReentrantLock。默认segment数组大小为16。
（10.2）是否需要扩容：在插入元素之前，会判断Segment里的HashEntry数组是否超过阈值（threshold）。如果超过阀值，则需要进行扩容。而HashMap是put后才判断。
（10.3）如何扩容：ConcurrentHashMap扩容不是针对整个容器，而是针对Segment。新创建的HashEntry数组大小是原来的两倍。
（10.4）put操作步骤
- 为key做Hash运算，得到hash值。
- 通过hash值，定位到具体的Segment对象
- 获取可重入锁
- 再次通过hash值，定位到Segment中HashEntry数组的具体位置。
- 插入或覆盖HashEntry对象。
- 释放锁。
（10.5）JDK8之后使用CAS算法