Java之集合框架汇总分析（java中集合框架的层次结构）

一：框架图

二：框架分析

（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算法