Java 集合底层原理剖析（List、Set、Map、Queue）
温馨提示：下面是以 Java 8 版本进行讲解，除非有特定说明。
一、Java 集合介绍
Java 集合是一个存储相同类型数据的容器，类似数组，集合可以不指定长度，但是数组必须指定长度。集合类主要从 Collection 和 Map 两个根接口派生出来，比如常用的 ArrayList、LinkedList、HashMap、HashSet、ConcurrentHashMap 等等。
二、List
2.1 ArrayList
ArrayList 是基于动态数组实现，容量能自动增长的集合。随机访问效率高，随机插入、随机删除效率低。线程不安全，多线程环境下可以使用 Collections.synchronizedList(list) 函数返回一个线程安全的 ArrayList 类，也可以使用 concurrent 并发包下的 CopyOnWriteArrayList 类。
2.1.1先说说synchronizedList(list) 底层源码如下：
static class SynchronizedList<E> extends SynchronizedCollection<E> implements List<E> { private static final long serialVersionUID = -7754090372962971524L; final List<E> list; SynchronizedList(List<E> list) { super(list); this.list = list; } SynchronizedList(List<E> list, Object mutex) { super(list, mutex); this.list = list; } public boolean equals(Object o) { if (this == o) return true; synchronized (mutex) {return list.equals(o);} } public int hashCode() { synchronized (mutex) {return list.hashCode();} } public E get(int index) { synchronized (mutex) {return list.get(index);} } public E set(int index, E element) { synchronized (mutex) {return list.set(index, element);} } public void add(int index, E element) { synchronized (mutex) {list.add(index, element);} } public E remove(int index) { synchronized (mutex) {return list.remove(index);} } public int indexOf(Object o) { synchronized (mutex) {return list.indexOf(o);} } public int lastIndexOf(Object o) { synchronized (mutex) {return list.lastIndexOf(o);} } public boolean addAll(int index, Collection<? extends E> c) { synchronized (mutex) {return list.addAll(index, c);} } public ListIterator<E> listIterator() { return list.listIterator(); // Must be manually synched by user } public ListIterator<E> listIterator(int index) { return list.listIterator(index); // Must be manually synched by user } public List<E> subList(int fromIndex, int toIndex) { synchronized (mutex) { return new SynchronizedList<>(list.subList(fromIndex, toIndex), mutex); } } @Override public void replaceAll(UnaryOperator<E> operator) { synchronized (mutex) {list.replaceAll(operator);} } @Override public void sort(Comparator<? super E> c) { synchronized (mutex) {list.sort(c);} } private Object readResolve() { return (list instanceof RandomAccess ? new SynchronizedRandomAccessList<>(list) : this); } }
使用方式如下，官方文档就是下面的使用方式
List list = Collections.synchronizedList(new ArrayList()); ... synchronized (list) { Iterator i = list.iterator(); // Must be in synchronized block while (i.hasNext()) foo(i.next()); }
既然封装类内部已经加了对象锁，为什么外部还要加一层对象锁？
看源码可知，Collections.synchronizedList中很多方法，比如equals,hasCode,get,set,add,remove,indexOf,lastIndexOf......
都添加了锁，但是List中
Iterator<E> iterator();
这个方法没有加锁，不是线程安全的，所以如果要遍历，还是必须要在外面加一层锁。
使用Iterator迭代器的话，似乎也没必要用Collections.synchronizedList的方法来包装了——反正都是必须要使用Synchronized代码块包起来的。
所以总的来说，Collections.synchronizedList这种做法，适合不需要使用Iterator、对性能要求也不高的情况。SynchronizedList和Vector最主要的区别：
- Vector扩容为原来的2倍长度，ArrayList扩容为原来1.5倍
- SynchronizedList有很好的扩展和兼容功能。他可以将所有的List的子类转成线程安全的类。
- 使用SynchronizedList的时候，进行遍历时要手动进行同步处理 。
- SynchronizedList可以指定锁定的对象。
2.1.2再说说CopyOnWriteArrayList,同样我们进源码了解：
CopyOnWriteArrayList是Java并发包中提供的一个并发容器，它是个线程安全且读操作无锁的ArrayList，写操作则通过创建底层数组的新副本来实现，是一种读写分离的并发策略，我们也可以称这种容器为"写时复制器"，Java并发包中类似的容器还有CopyOnWriteSet。
我们都知道，集合框架中的ArrayList是非线程安全的，Vector虽是线程安全的，但由于简单粗暴的锁同步机制，性能较差。而CopyOnWriteArrayList则提供了另一种不同的并发处理策略（当然是针对特定的并发场景）。
很多时候，我们的系统应对的都是读多写少的并发场景。CopyOnWriteArrayList容器允许并发读，读操作是无锁的，性能较高。至于写操作，比如向容器中添加一个元素，则首先将当前容器复制一份，然后在新副本上执行写操作，结束之后再将原容器的引用指向新容器。
优缺点分析
了解了CopyOnWriteArrayList的实现原理，分析它的优缺点及使用场景就很容易了。
优点：
读操作性能很高，因为无需任何同步措施，比较适用于读多写少的并发场景。Java的list在遍历时，若中途有别的线程对list容器进行修改，则会抛出ConcurrentModificationException异常。而CopyOnWriteArrayList由于其"读写分离"的思想，遍历和修改操作分别作用在不同的list容器，所以在使用迭代器进行遍历时候，也就不会抛出ConcurrentModificationException异常了
缺点：
缺点也很明显，一是内存占用问题，毕竟每次执行写操作都要将原容器拷贝一份，数据量大时，对内存压力较大，可能会引起频繁GC；二是无法保证实时性，Vector对于读写操作均加锁同步，可以保证读和写的强一致性。而CopyOnWriteArrayList由于其实现策略的原因，写和读分别作用在新老不同容器上，在写操作执行过程中，读不会阻塞但读取到的却是老容器的数据。
源码分析
基本原理了解了，CopyOnWriteArrayList的代码实现看起来就很容易理解了。
添加操作：
public boolean add(E e) { //ReentrantLock加锁，保证线程安全 final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); int len = elements.length; //拷贝原容器，长度为原容器长度加一 Object[] newElements = Arrays.copyOf(elements, len + 1); //在新副本上执行添加操作 newElements[len] = e; //将原容器引用指向新副本 setArray(newElements); return true; } finally { //解锁 lock.unlock(); } }
添加的逻辑很简单，先将原容器copy一份，然后在新副本上执行写操作，之后再切换引用。当然此过程是要加锁的。
删除操作
public E remove(int index) { //加锁 final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); int len = elements.length; E oldValue = get(elements, index); int numMoved = len - index - 1; if (numMoved == 0) //如果要删除的是列表末端数据，拷贝前len-1个数据到新副本上，再切换引用 setArray(Arrays.copyOf(elements, len - 1)); else { //否则，将除要删除元素之外的其他元素拷贝到新副本中，并切换引用 Object[] newElements = new Object[len - 1]; System.arraycopy(elements, 0, newElements, 0, index); System.arraycopy(elements, index + 1, newElements, index, numMoved); setArray(newElements); } return oldValue; } finally { //解锁 lock.unlock(); } }
删除操作同理，将除要删除元素之外的其他元素拷贝到新副本中，然后切换引用，将原容器引用指向新副本。同属写操作，需要加锁。
我们再来看看读操作，CopyOnWriteArrayList的读操作是不用加锁的，性能很高。
public E get(int index) { return get(getArray(), index); }
直接读取即可，无需加锁
动态数组，是指当数组容量不足以存放新的元素时，会创建新的数组，然后把原数组中的内容复制到新数组。
主要属性：
//存储实际数据，使用transient修饰，序列化的时不会被保存 transient Object[] elementData; //元素的数量，即容量。 private int size;
特征：
- 允许元素为 null；
- 查询效率高、插入、删除效率低，因为大量 copy 原来元素；
- 线程不安全。
使用场景：
- 需要快速随机访问元素
- 单线程环境
add(element) 流程：
- 判断当前数组是否为空，如果是则创建长度为 10（默认）的数组，因为 new ArrayList 的时是没有初始化；
- 判断是否需要扩容，如果当前数组的长度加 1（即 size+1）后是否大于当前数组长度，则进行扩容 grow()；
- 最后在数组末尾添加元素，并 size+1。
grow() 流程：
- 创建新数组，长度扩大为原数组的 1.5 倍；
- 如果扩大 1.5 倍还是不够，则根据实际长度来扩容，比如 addAll() 场景；
- 将原数组的数据使用 System.arraycopy（native 方法）复制到新数组中。
add(index,element) 流程：
1.检查 index 是否在数组范围内，假如数组长度是 2，则 index 必须 >=0 并且 <=2，否则报 IndexOutOfBoundsException 异常；
2.扩容检查；
3.通过拷贝方式，把数组位置为 index 至 size-1 的元素都往后移动一位，腾出位置之后放入元素，并 size+1。
set(index,element) 流程：
1.检查 index 是否在数组范围内，假如数组长度是 2，则 index 必须 >=0 并且 <2；
2.保留被覆盖的值，因为最后需要返回旧的值；
3.新元素覆盖位置为 index 的旧元素，返回旧值。
get(index) 流程：
1.判断下标有没有越界；
2.通过数组下标来获取元素，get 的时间复杂度是 O(1)。
remove(index) 流程：
1.检查指定位置是否在数组范围内，假如数组长度是 2，则 index 必须 >=0 并且 < 2；
2.保留要删除的值，因为最后需要返回旧的值；
3.计算出需要移动元素个数，再通过拷贝使数组内位置为 index+1 到 size-1 的元素往前移动一位，把数组最后一个元素设置为 null（精辟小技巧），返回旧值。
注意事项：
1.new ArrayList 创建对象时，如果没有指定集合容量则初始化为 0；如果有指定，则按照指定的大小初始化；
2.扩容时，先将集合扩大 1.5 倍，如果还是不够，则根据实际长度来扩容，保证都能存储所有数据，比如 addAll() 场景。
3.如果新扩容后数组长度大于（Integer.MAX_VALUE-8），则抛出 OutOfMemoryError。
2.2 LinkedList
LinkedList 是可以在任何位置进行插入和移除操作的有序集合，它是基于双向链表实现的，线程不安全。LinkedList 功能比较强大，可以实现栈、队列或双向队列。
主要属性：
//链表长度 transient int size = 0; //头部节点 transient Node<E> first; //尾部节点 transient Node<E> last; /** * 静态内部类，存储数据的节点 */ private static class Node<E> { //自身结点 E item; //下一个节点 Node<E> next; //上一个节点 Node<E> prev; }
特征：
允许元素为 null；
插入和删除效率高，查询效率低；
顺序访问会非常高效，而随机访问效率（比如 get 方法）比较低；
既能实现栈 Stack（后进先出），也能实现队列（先进先出）, 也能实现双向队列，因为提供了 xxxFirst()、xxxLast() 等方法；
线程不安全。
使用场景：
需要快速插入，删除元素
按照顺序访问其中的元素
单线程环境
add() 流程：
创建一个新结点，结点元素 item 为传入参数，前继节点 prev 为“当前链表 last 结点”，后继节点 next 为 null；
判断当前链表 last 结点是否为空，如果是则把新建结点作为头结点，如果不是则把新结点作为 last 结点。
最后返回 true。
get(index,element) 流程：
检查 index 是否在数组范围内，假如数组长度是 2，则 index 必须 >=0 并且 < 2；
index 小于“双向链表长度的 1/2”则从头开始往后遍历查找，否则从链表末尾开始向前遍历查找。
remove() 流程：
判断 first 结点是否为空，如果是则报 NoSuchElementException 异常；
如果不为空，则把待删除结点的 next 结点的 prev 属性赋值为 null，达到删除头结点的效果。
返回删除值。
2.3 Vector
Vector 是矢量队列，也是基于动态数组实现，容量可以自动扩容。跟 ArrayList 实现原理一样，但是 Vector 是线程安全，使用 Synchronized 实现线程安全，性能非常差，已被淘汰，使用 CopyOnWriteArrayList 替代 Vector。
主要属性：
//存储实际数据 protected Object[] elementData; //动态数组的实际大小 protected int elementCount; //动态数组的扩容系数 protected int capacityIncrement;
特征：
允许元素为 null；
查询效率高、插入、删除效率低，因为需要移动元素；
默认的初始化大小为 10，没有指定增长系数则每次都是扩容一倍，如果扩容后还不够，则直接根据参数长度来扩容；
线程安全，性能差（Synchronized），使用 CopyOnWriteArrayList 替代 Vector。
**使用场景：**多线程环境
2.4 Stack
Stack 是栈，先进后出原则，Stack 继承 Vector，也是通过数组实现，线程安全。因为效率比较低，不推荐使用，可以使用 LinkedList（线程不安全）或者 ConcurrentLinkedDeque（线程安全）来实现先进先出的效果。
**数据结构：**动态数组
**构造函数：**只有一个默认 Stack()
**特征：**先进后出
实现原理：
Stack 执行 push() 时，将数据推进栈，即把数据追加到数组的末尾。
Stack 执行 peek 时，取出栈顶数据，不删除此数据，即获取数组首个元素。
Stack 执行 pop 时，取出栈顶数据，在栈顶删除数据，即删除数组首个元素。
Stack 继承于 Vector，所以 Vector 拥有的属性和功能，Stack 都拥有，比如 add()、set() 等等。
2.5 CopyOnWriteArrayList
CopyOnWriteArrayList 是线程安全的 ArrayList，写操作（add、set、remove 等等）时，把原数组拷贝一份出来，然后在新数组进行写操作，操作完后，再将原数组引用指向到新数组。CopyOnWriteArrayList 可以替代 Collections.synchronizedList(List list)。
**数据结构：**动态数组
特征：
线程安全；
读多写少，比如缓存；
不能保证实时一致性，只能保证最终一致性。
缺点：
写操作，需要拷贝数组，比较消耗内存，如果原数组容量大的情况下，可能触发频繁的 Young GC 或者 Full GC；
不能用于实时读的场景，因为读取到数据可能是旧的，可以保证最终一致性。
实现原理：
CopyOnWriteArrayList 写操作加了锁，不然多线程进行写操作时会复制多个副本；读操作没有加锁，所以可以实现并发读，但是可能读到旧的数据，比如正在执行读操作时，同时有多个写操作在进行，遇到这种场景时，就会都到旧数据。
2.6 CopyOnWriteArraySet
CopyOnWriteArraySet 是线程安全的无序并且不能重复的集合，可以认为是线程安全的 HashSet，底层是通过 CopyOnWriteArrayList 机制实现。
**数据结构：**动态数组（CopyOnWriteArrayList），并不是散列表。
特征：
线程安全
读多写少，比如缓存
不能存储重复元素
2.7 ArrayList 和 Vector 区别
Vector 线程安全，ArrayList 线程不安全；
ArrayList 在扩容时默认是扩展 1.5 倍，Vector 是默认扩展 1 倍；
ArrayList 支持序列化，Vector 不支持；
Vector 提供 indexOf(obj, start) 接口，ArrayList 没有；
Vector 构造函数可以指定扩容增加系数，ArrayList 不可以。
2.8 ArrayList 与 LinkedList 的区别
ArrayList 的数据结构是动态数组，LinkedList 的数据结构是链表；
ArrayList 不支持高效的插入和删除元素，LinkedList 不支持高效的随机访问元素；
ArrayList 的空间浪费在数组末尾预留一定的容量空间，LinkedList 的空间浪费在每一个结点都要消耗空间来存储 prev、next 等信息。
三、Map
3.1 HashMap
HashMap 是以key-value 键值对形式存储数据，允许 key 为 null（多个则覆盖），也允许 value 为 null。底层结构是数组 + 链表 + 红黑树。
主要属性：
initialCapacity：初始容量，默认 16，2 的 N 次方。
loadFactor：负载因子，默认 0.75，用于扩容。
threshold：阈值，等于 initialCapacity * loadFactor，比如：16 * 0.75 = 12。
size：存放元素的个数，非 Node 数组长度。
Node
//存储元素的数组 transient Node<K,V>[] table; //存放元素的个数，非Node数组长度 transient int size; //记录结构性修改次数，用于快速失败 transient int modCount; //阈值 int threshold; //负载因子，默认0.75，用于扩容 final float loadFactor; /** * 静态内部类，存储数据的节点 */ static class Node<K,V> implements Map.Entry<K,V> { //节点的hash值 final int hash; //节点的key值 final K key; //节点的value值 V value; //下一个节点的引用 Node<K,V> next; }
**数据结构：**数组 + 单链表，Node 结构：hash|key|value|next
**只允许一个 key 为 Null（多个则覆盖），但允许多个 value 为 Null **
查询、插入、删除效率都高（集成了数组和单链表的特性）
** * 默认的初始化大小为 16，之后每次扩充为原来的 2 倍
线程不安全
使用场景：
快速增删改查
随机存取
缓存
哈希冲突的解决方案：
开放定址法
再散列函数法
链地址法（拉链法，常用）
put() 存储的流程（Java 8）：
（1）计算待新增数据 key 的 hash 值；
(2)判断 Node[] 数组是否为空或者数据长度为 0 的情况，则需要进行初始化；
(3)根据 hash 值通过位运算定计算出 Node 数组的下标，判断该数组第一个 Node 节点是否有数据，如果没有数据，则插入新值；
(4)如果有数据，则根据具体情况进行操作，如下：
1.如果该 Node 结点的 key（即链表头结点）与待新增的 key 相等（== 或者 equals），则直接覆盖值，最后返回旧值；
2.如果该结构是树形，则按照树的方式插入新值；
3.如果是链表结构，则判断链表长度是否大于阈值 8，如果 >=8 并且数组长度 >=64 才转为红黑树，如果 >=8 并且数组长度 < 64 则进行扩容；
4.如果不需要转为红黑树，则遍历链表，如果找到 key 和 hash 值同时相等，则进行覆盖返回旧值，如果没有找到，则将新值插入到链表的最后面（尾插法）；
5.判断数组长度是否大于阈值，如果是则进入扩容阶段。
resize() 扩容的流程（Java 8）：
扩容过程比较复杂， 迁移算法与 Java 7 不一样，Java 8 不需要每个元素都重新计算 hash，迁移过程中元素的位置要么是在原位置，要么是在原位置再移动 2 次幂的位置。
get() 查询的流程（Java 8）：
根据 put() 方法的方式计算出数组的下标；
遍历数组下标对应的链表，如果找到 key 和 hash 值同时相等就返回对应的值，否则返回 null。
get() 注意事项：Java 8 没有把 key 为 null 放到数组 table[0] 中。
remove() 删除的流程（Java 8）：
根据 get() 方法的方式计算出数组的下标，即定位到存储删除元素的 Node 结点；
如果待删结点是头节点，则用它的 next 结点顶替它作为头节点；
如果待删结点是红黑树结点，则直接调用红黑树的删除方法进行删除；
如果待删结点是链表中的一个节点，则用待删除结点的前一个节点的 next 属性指向它的 next 结点；
如果删除成功则返回被删结点的 value，否则返回 null。
remove() 注意事项：删除单个 key，注意返回是的键值对中的 value。
为什么使用位运算（&）来代替取模运算（%）：
效率高，位运算直接对内存数据进行操作，不需转成十进制，因此处理速度非常快；
可以解决负数问题，比如：-17 % 10 = -7。
HashMap 在 Java 7 和 Java 8 中的区别：
(1)存放数据的结点名称不同，作用都一样，存的都是 hashcode、key、value、next 等数据：
Java 7：使用 Entry 存放数据
Java 8：改名为 Node
(2)定位数组下标位置方法不同：
Java 7：计算 key 的 hash，将 hash 值进行了四次扰动，再进行取模得出；
Java 8：计算 key 的 hash，将 hash 值进行高 16 位异或低 16 位，再进行与运算得出。
(3）扩容算法不同：
Java 7：扩容要重新计算 hash
Java 8：不用重新计算
（4）put 方法插入链表位置不同：
Java 7：头插法
Java 8：尾插法
（5）Java 8 引入了红黑树，当链表长度 >=8 时，并且同时数组的长度 >=64 时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高 HashMap 的性能。
3.2 HashTable
和 HashMap 一样，Hashtable 也是一个哈希散列表，Hashtable 继承于 Dictionary，使用重入锁 Synchronized 实现线程安全，key 和 value 都不允许为 Null。HashTable 已被高性能的 ConcurrentHashMap 代替。
主要属性：
initialCapacity：初始容量，默认 11。
loadFactor：负载因子，默认 0.75。
threshold：阈值。
modCount：记录结构性修改次数，用于快速失败。
//真正存储数据的数组 private transient Entry<?,?>[] table; //存放元素的个数，非Entry数组长度 private transient int count; //阈值 private int threshold; //负载因子，默认0.75 private float loadFactor; //记录结构性修改次数，用于快速失败 private transient int modCount = 0; /** * 静态内部类，存储数据的节点 */ private static class Entry<K,V> implements Map.Entry<K,V> { //节点的hash值 final int hash; //节点的key值 final K key; //节点的value值 V value; //下一个节点的引用 Entry<K,V> next; }
快速失败原理是在并发场景下进行遍历操作时，如果有另外一个线程对它执行了写操作，此时迭代器可以发现并抛出 ConcurrentModificationException，而不需等到遍历完后才报异常。
**数据结构：**链表的数组，数组 + 链表，Entry 结构：hash|key|value|next
特征：
key 和 value 都不允许为 Null；
HashTable 默认的初始大小为 11，之后每次扩充为原来的 2 倍；
线程安全。
原理：
与 HashMap 不一样的流程是定位数组下标逻辑，HashTable 是在 key.hashcode() 后使用取模，HashMap 是位运算。HashTable 是 put() 之前进行判断是否扩容 resize()，而 HashMap 是 put() 之后扩容。
更多参考（总结的不错）：(26条消息) Java 集合底层原理剖析（List、Set、Map、Queue）_快乐的工程师的博客-CSDN博客