Java 集合底层原理剖析（List、Set、Map、Queue）_java中几种集合的底层原理?

Java 集合底层原理剖析（List、Set、Map、Queue）

温馨提示：下面是以 Java 8 版本进行讲解，除非有特定说明。

一、Java 集合介绍

Java 集合是一个存储相同类型数据的容器，类似数组，集合可以不指定长度，但是数组必须指定长度。集合类主要从 Collection 和 Map 两个根接口派生出来，比如常用的 ArrayList、LinkedList、HashMap、HashSet、ConcurrentHashMap 等等。

Collection 根接口框架结构图：

Map 根接口框架结构图：

二、List

2.1 ArrayList

ArrayList 是基于动态数组实现，容量能自动增长的集合。随机访问效率高，随机插入、随机删除效率低。线程不安全，多线程环境下可以使用 Collections.synchronizedList(list) 函数返回一个线程安全的 ArrayList 类，也可以使用 concurrent 并发包下的 CopyOnWriteArrayList 类。

动态数组，是指当数组容量不足以存放新的元素时，会创建新的数组，然后把原数组中的内容复制到新数组。

主要属性：

//存储实际数据，使用transient修饰，序列化的时不会被保存
transient Object[] elementData;
//元素的数量，即容量。
private int size;

1
2
3
4
5

**数据结构：**动态数组

特征：

1. 允许元素为 null；
2. 查询效率高、插入、删除效率低，因为大量 copy 原来元素；
3. 线程不安全。

使用场景：

1. 需要快速随机访问元素
2. 单线程环境

add(element) 流程：

1. 判断当前数组是否为空，如果是则创建长度为 10（默认）的数组，因为 new ArrayList 的时是没有初始化；
2. 判断是否需要扩容，如果当前数组的长度加 1（即 size+1）后是否大于当前数组长度，则进行扩容 grow()；
3. 最后在数组末尾添加元素，并 size+1。

grow() 流程：

1. 创建新数组，长度扩大为原数组的 1.5 倍；
2. 如果扩大 1.5 倍还是不够，则根据实际长度来扩容，比如 addAll() 场景；
3. 将原数组的数据使用 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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

**数据结构：**双向链表

特征：

1. 允许元素为 null；
2. 插入和删除效率高，查询效率低；
3. 顺序访问会非常高效，而随机访问效率（比如 get 方法）比较低；
4. 既能实现栈 Stack（后进先出），也能实现队列（先进先出）, 也能实现双向队列，因为提供了 xxxFirst()、xxxLast() 等方法；
5. 线程不安全。

使用场景：

1. 需要快速插入，删除元素
2. 按照顺序访问其中的元素
3. 单线程环境

add() 流程：

1. 创建一个新结点，结点元素 item 为传入参数，前继节点 prev 为“当前链表 last 结点”，后继节点 next 为 null；
2. 判断当前链表 last 结点是否为空，如果是则把新建结点作为头结点，如果不是则把新结点作为 last 结点。
3. 最后返回 true。

get(index,element) 流程：

1. 检查 index 是否在数组范围内，假如数组长度是 2，则 index 必须 >=0 并且 < 2；
2. index 小于“双向链表长度的 1/2”则从头开始往后遍历查找，否则从链表末尾开始向前遍历查找。

remove() 流程：

1. 判断 first 结点是否为空，如果是则报 NoSuchElementException 异常；
2. 如果不为空，则把待删除结点的 next 结点的 prev 属性赋值为 null，达到删除头结点的效果。
3. 返回删除值。

2.3 Vector

Vector 是矢量队列，也是基于动态数组实现，容量可以自动扩容。跟 ArrayList 实现原理一样，但是 Vector 是线程安全，使用 Synchronized 实现线程安全，性能非常差，已被淘汰，使用 CopyOnWriteArrayList 替代 Vector。

主要属性：

//存储实际数据
protected Object[] elementData;
//动态数组的实际大小
protected int elementCount;
//动态数组的扩容系数
protected int capacityIncrement;

1
2
3
4
5
6
7

**数据结构：**动态数组

特征：

1. 允许元素为 null；
2. 查询效率高、插入、删除效率低，因为需要移动元素；
3. 默认的初始化大小为 10，没有指定增长系数则每次都是扩容一倍，如果扩容后还不够，则直接根据参数长度来扩容；
4. 线程安全，性能差（Synchronized），使用 CopyOnWriteArrayList 替代 Vector。

**使用场景：**多线程环境

2.4 Stack

Stack 是栈，先进后出原则，Stack 继承 Vector，也是通过数组实现，线程安全。因为效率比较低，不推荐使用，可以使用 LinkedList（线程不安全）或者 ConcurrentLinkedDeque（线程安全）来实现先进先出的效果。

**数据结构：**动态数组

**构造函数：**只有一个默认 Stack()

**特征：**先进后出

实现原理：

1. Stack 执行 push() 时，将数据推进栈，即把数据追加到数组的末尾。
2. Stack 执行 peek 时，取出栈顶数据，不删除此数据，即获取数组首个元素。
3. Stack 执行 pop 时，取出栈顶数据，在栈顶删除数据，即删除数组首个元素。
4. Stack 继承于 Vector，所以 Vector 拥有的属性和功能，Stack 都拥有，比如 add()、set() 等等。

2.5 CopyOnWriteArrayList

CopyOnWriteArrayList 是线程安全的 ArrayList，写操作（add、set、remove 等等）时，把原数组拷贝一份出来，然后在新数组进行写操作，操作完后，再将原数组引用指向到新数组。CopyOnWriteArrayList 可以替代 Collections.synchronizedList(List list)。

**数据结构：**动态数组

特征：

1. 线程安全；
2. 读多写少，比如缓存；
3. 不能保证实时一致性，只能保证最终一致性。

缺点：

1. 写操作，需要拷贝数组，比较消耗内存，如果原数组容量大的情况下，可能触发频繁的 Young GC 或者 Full GC；
2. 不能用于实时读的场景，因为读取到数据可能是旧的，可以保证最终一致性。

实现原理：

CopyOnWriteArrayList 写操作加了锁，不然多线程进行写操作时会复制多个副本；读操作没有加锁，所以可以实现并发读，但是可能读到旧的数据，比如正在执行读操作时，同时有多个写操作在进行，遇到这种场景时，就会都到旧数据。

2.6 CopyOnWriteArraySet

CopyOnWriteArraySet 是线程安全的无序并且不能重复的集合，可以认为是线程安全的 HashSet，底层是通过 CopyOnWriteArrayList 机制实现。

**数据结构：**动态数组（CopyOnWriteArrayList），并不是散列表。

特征：

1. 线程安全
2. 读多写少，比如缓存
3. 不能存储重复元素

2.7 ArrayList 和 Vector 区别

1. Vector 线程安全，ArrayList 线程不安全；
2. ArrayList 在扩容时默认是扩展 1.5 倍，Vector 是默认扩展 1 倍；
3. ArrayList 支持序列化，Vector 不支持；
4. Vector 提供 indexOf(obj, start) 接口，ArrayList 没有；
5. Vector 构造函数可以指定扩容增加系数，ArrayList 不可以。

2.8 ArrayList 与 LinkedList 的区别

1. ArrayList 的数据结构是动态数组，LinkedList 的数据结构是链表；
2. ArrayList 不支持高效的插入和删除元素，LinkedList 不支持高效的随机访问元素；
3. 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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

**数据结构：**数组 + 单链表，Node 结构：hash|key|value|next

**只允许一个 key 为 Null（多个则覆盖），但允许多个 value 为 Null **

• 查询、插入、删除效率都高（集成了数组和单链表的特性）
  ** * 默认的初始化大小为 16，之后每次扩充为原来的 2 倍
• 线程不安全

使用场景：

1. 快速增删改查
2. 随机存取
3. 缓存

哈希冲突的解决方案：

1. 开放定址法
2. 再散列函数法
3. 链地址法（拉链法，常用）

put() 存储的流程（Java 8）：

1. 计算待新增数据 key 的 hash 值；
2. 判断 Node[] 数组是否为空或者数据长度为 0 的情况，则需要进行初始化；
3. 根据 hash 值通过位运算定计算出 Node 数组的下标，判断该数组第一个 Node 节点是否有数据，如果没有数据，则插入新值；
4. 如果有数据，则根据具体情况进行操作，如下：

• 如果该 Node 结点的 key（即链表头结点）与待新增的 key 相等（== 或者 equals），则直接覆盖值，最后返回旧值；
• 如果该结构是树形，则按照树的方式插入新值；
• 如果是链表结构，则判断链表长度是否大于阈值 8，如果 >=8 并且数组长度 >=64 才转为红黑树，如果 >=8 并且数组长度 < 64 则进行扩容；
• 如果不需要转为红黑树，则遍历链表，如果找到 key 和 hash 值同时相等，则进行覆盖返回旧值，如果没有找到，则将新值插入到链表的最后面（尾插法）；

5. 判断数组长度是否大于阈值，如果是则进入扩容阶段。

resize() 扩容的流程（Java 8）：

扩容过程比较复杂， 迁移算法与 Java 7 不一样，Java 8 不需要每个元素都重新计算 hash，迁移过程中元素的位置要么是在原位置，要么是在原位置再移动 2 次幂的位置。

get() 查询的流程（Java 8）：

1. 根据 put() 方法的方式计算出数组的下标；
2. 遍历数组下标对应的链表，如果找到 key 和 hash 值同时相等就返回对应的值，否则返回 null。

get() 注意事项：Java 8 没有把 key 为 null 放到数组 table[0] 中。

remove() 删除的流程（Java 8）：

1. 根据 get() 方法的方式计算出数组的下标，即定位到存储删除元素的 Node 结点；
2. 如果待删结点是头节点，则用它的 next 结点顶替它作为头节点；
3. 如果待删结点是红黑树结点，则直接调用红黑树的删除方法进行删除；
4. 如果待删结点是链表中的一个节点，则用待删除结点的前一个节点的 next 属性指向它的 next 结点；
5. 如果删除成功则返回被删结点的 value，否则返回 null。

remove() 注意事项：删除单个 key，注意返回是的键值对中的 value。

为什么使用位运算（&）来代替取模运算（%）：

1. 效率高，位运算直接对内存数据进行操作，不需转成十进制，因此处理速度非常快；
2. 可以解决负数问题，比如：-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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

快速失败原理是在并发场景下进行遍历操作时，如果有另外一个线程对它执行了写操作，此时迭代器可以发现并抛出 ConcurrentModificationException，而不需等到遍历完后才报异常。

**数据结构：**链表的数组，数组 + 链表，Entry 结构：hash|key|value|next

特征：

1. key 和 value 都不允许为 Null；
2. HashTable 默认的初始大小为 11，之后每次扩充为原来的 2 倍；
3. 线程安全。

原理：

与 HashMap 不一样的流程是定位数组下标逻辑，HashTable 是在 key.hashcode() 后使用取模，HashMap 是位运算。HashTable 是 put() 之前进行判断是否扩容 resize()，而 HashMap 是 put() 之后扩容。

3.3 ConcurrentHashMap

ConcurrentHashMap 在 Java 8 版本中丢弃了 Segment（分锁段）、ReentrantLock、HashEntry 数组这些概念，而是采用CAS + Synchronized 实现锁操作，Node 改名为 HashEntry，引入了红黑树保证查询效率，底层数据结构由数组 + 链表 + 红黑树组成，Node 数组默认为 16。数据结构如下图：

数据结构（Java 8)：Node[] 数组 + 单链表 + 红黑树

---

• 判断待新增数据 key 和 value 是否为空，如果是则抛空指针异常；
  ** * 计算待新增数据 key 的 hash 值；
• 判断 Node[] 数组是否为空或者数据长度为 0 的情况，则需要进行初始化；
• 根据 hash 值通过位运算定计算出 Node 数组的下标，判断该数组第一个 Node 节点是否有数据，如果没有数据，则使用 CAS 操作将这个新值插入；
• 如果有数据，则判断头结点的 hashCode 是否等于 MOVED（即 -1），即检查是否正在扩容，如果等于 - 1 则帮助扩容；
• 如果有数据，则对头结点进行加锁（synchronized），如果头结点的 hashCode>=0，说明是链表，遍历链表，如果找到 key 和 hash 值同时相等，则进行覆盖，如果没有找到，则将新值插入到链表的最后面（尾插法）；如果 hashCode<0，说明是红黑树，调用红黑树的插值方法插入新节点；
• 插值完成之后，判断链表元素是否 >=8，如果 >=8 并且数组长度 >=64 才转为红黑树，如果 >=8 并且数组长度 < 64 则进行扩容。

resize() 扩容的流程（Java 8）：

扩容的原理是创建新的数组，长度是原来的两倍，然后把旧数组数据迁移到新的数组中，在多线程情况下，需要注意线程安全问题，在解决安全问题的同时，还需要关注其效率。

get() 查询的流程（Java 8）：

1. 计算获取数据 key 的 hash 值；
2. 根据 hashCode 通过位运算定得到 Node 数组的下标，即得到头节点；
3. 如果头结点为空，则返回 null；
4. 如果头结点的 key 与参数 key 可以相等，则返回头结点的值；
5. 如果头结点的 hashCode 小于 0，说明是红黑树，则调用 find() 方法按照树的方式获取值；
6. 如果都不满足 3、4 和 5 条件，说明是链表，则按照链表的方式遍历获取值。整个过程都不需要加锁。

get() 注意事项：

整个过程都不需要加锁，因为读取数据的属性使用 volatile 修饰，实现线程可见性。

remove() 删除的流程（Java 8）：

1. 计算待新增数据 key 的 hash 值；
2. 判断 Node[] 数组是否为空或者数据长度为 0 的情况，如果是则返回 null；如果不是则根据 hashCode 通过位运算定得到 Node 数组的下标，即得到头结点；
3. 判断头结点的 hashCode 是否等于 MOVED（即 -1），检查是否正在扩容，如果是则帮助扩容；
4. 如果都不满足 2 和 3 条件，则加锁进行删除操作；
5. 首先判断头结点有无发生变化（步骤 3 点转移操作会改变头结点），如果有改变则返回 null；
6. 如果头结点的 hashCode 大于 0 说明是链表，则按照链表方式遍历删值；
7. 如果头结点是 TreeBin 类型，说明是红黑树，则按照树的方式删值。

remove() 注意事项：

remove 函数底层是调用 replaceNode 函数实现结点的删除。

**使用场景：**并发、线程不安全场景

ConcurrentHashMap 在 Java 7 和 Java 8 中的区别：

1. Java 7 使用 Segment 分段加锁机制，Segment 继承 ReentrantLock 实现锁操作，而 Java 8 使用 CAS + Synchronized 实现锁操作；
2. Java 7 查询时遍历链表效率低，而 Java 8 采用红黑树提高查询效率；
3. Java 7 使用 HashEntry 存放数据，而 Java 8 改名为 Node，作用都是一样，存放的都是 hashcode、key、value、next 等数据。
4. Java 7 是把数据插入到链表的表头（头插法），而 Java 8 是将数据插入到链表的最后面（尾插法）；
5. Java 7 先扩容，再插值，而 Java 8 先插值，再扩容；
6. Java 7 的最大并发个数是 Segment 的个数默认值是 16，锁住整个段，不影响其他段；而 Java 8 去掉了分段锁，更细粒度，只锁住一个 Node 节点，不影响其他 Node 节点；
7. Java 7 在扩容时锁住一个段，当前段可读不能写，其他段可读写，只开启一个线程执行扩容操作；而 Java 8 锁住一个 Node 结点，当前结点可读不能写，其他结点可读写，1 个线程执行扩容 + 可能多个 put()/remove 线程帮助扩容。

HashMap、Hashtable、ConccurentHashMap 三者的区别（Java 8）：

1. HashMap 线程不安全，没有锁机制，数组 + 链表 + 红黑树
2. Hashtable 线程安全，锁住整个对象，数组 + 链表
3. ConccurentHashMap 线程安全，CAS+Synchronized，数组 + 链表 + 红黑树
4. HashMap 的 key 和 value 都可为 null，其他两个都不可以。

3.4 TreeMap

TreeMap 实现了 SotredMap 接口，意味着可以排序，是一个有序的集合。底层数据结构是红黑树结构，TreeMap 中的每个元素都存放在红黑树的节点上，默认使用自然排序，也可以自定排序，线程不安全。

主要属性：

//排序比较器
private final Comparator<? super K> comparator;
//红黑树根节点
private transient Entry<K,V> root;
//集合长度
private transient int size = 0;
//记录结构性修改次数，用于快速失败
private transient int modCount = 0;

//红黑树常量
private static final boolean RED   = false;
private static final boolean BLACK = true;

/\*\* \* 实际存储数据的节点 \*/
static final class Entry\<K,V\> implements Map.Entry\<K,V\> {
    //节点的key值
    K key;
    //节点的value值
    V value;
    //左子树引用
    Entry<K,V> left;
    //右子树引用
    Entry<K,V> right;
    //父节点引用
    Entry<K,V> parent;
    //节点颜色（默认黑色）
    boolean color = BLACK;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

**数据结构：**红黑树（高效的检索二叉树），Entry 结构：key|value|left|right|parent|color

特征：

1. key 不允许为 Null，但允许多个 value 为 Null
2. 线程不安全

put() 存储的流程：

主要分为两个步骤，构建排序二叉树和构建平衡二叉树。

构建排序二叉树，过程如下：

1. 从根节点 root 开始查找；
2. 如果 root 节点比待插入节点值小，则在 root 节点左子树查找，如果大于，则在右子树查找；
3. 递归循环步骤 2，找到合适的节点为止；
4. 把待插入节点与步骤 3 中找到的节点进行比较，如果待插入节点小于找到节点，则把待插入节点作为左子节点；否则作为右子节点。

举个栗子：put(9)，步骤如下：

**

** * 从 root 节点 8 开始检索；

• 如果 8 小于 9，则从 8 的右子树继续找，10 大于 9，10 没有左子树；
• 循环递归步骤 2，找到 10 这个合适节点；
  **1. 10box-sizing:border-box;outline:0px;">构建平衡二叉树，经过左旋、右旋、着色这些步骤后，得到一棵平衡二叉树。

remove() 的流程：比 put() 复杂，也是分两个步骤，删除节点和着色旋转。

删除节点，删除时出现以下 3 种情况：

1. 待删除节点，如果没有左和右子节点时，则直接删除；
2. 待删除节点，如果有一个子节点时，则把它的子节点指向它的上级节点（即父节点）；
3. 待删除节点，如果有两个非空的子节点时，流程复杂，暂不在此解释。

着色旋转，进行颜色的对调和旋转，达到红黑树的特征。

3.5 LinkedHashMap

LinkedHashMap 是使用 HashMap 机制实现。LinkedHashMap 在 HashMap 的基础上增加 before 和 after 两个属性来保证了迭代顺序。迭代顺序可以是插入顺序（默认），也可以是访问顺序。线程不安全。

主要属性：

/\*\* \* 静态内部类，存储数据的节点 \*/
static class Entry\<K,V\> extends HashMap.Node\<K,V\> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

//头结点
transient LinkedHashMap.Entry<K,V> head;
//尾结点
transient LinkedHashMap.Entry<K,V> tail;
//排序标识，true访问顺序迭代； false插入顺序迭代（默认）
final boolean accessOrder;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

**数据结构：**数组 + 双向链表，Entry 结构：before|hash|key|value|next|after，before 和 after 用于维护整个双向链表。

特征：

1. 只允许一个 key 为 Null（多个则覆盖），允许多个 value 为 Null；
2. 线程不安全。

原理：

LinkedHashMap 继承了 HashMap，hash 算法也是跟 HashMap 一致。LinkedHashMap 在 Entry 中新增了 before 和 after 两个属性来维护双向链表的迭代顺序。Entry 的 next 属性是维护 Entry 连接顺序，而 after 是维护迭代顺序。LinkedHashMap 使用 LRU 算法实现访问顺序排序，比如 get() 操作后的元素会移动到链表末尾，从而实现按访问顺序迭代。

**使用场景：**保证插入和访问顺序

插入顺序（默认）和访问顺序区别，请看下面的代码：

public static void main(String[] args) {
        LinkedHashMap<String, String> map1 = new LinkedHashMap<>();
        map1.put("name", "joseph");
        map1.put("age", "33");
        map1.put("job", "敲代码");
        map1.put("hobby", "打篮球");
        map1.get("job");
        System.out.println("----start----按插入顺序遍历----");

        Iterator<Map.Entry<String, String>> iterator = map1.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<String, String> entry = iterator.next();
            System.out.println("key=" + entry.getKey() + ", value=" + entry.getValue());
        }

        System.out.println("-----end----按插入顺序遍历-----");
        System.out.println();
        System.out.println("----start----按访问顺序遍历----");

        LinkedHashMap<String, String> map2 = new LinkedHashMap<>(16, 0.75f, true);
        map2.put("name", "joseph");
        map2.put("age", "33");
        map2.put("job", "敲代码");
        map2.put("hobby", "打篮球");

        map2.get("job");

        Iterator<Map.Entry<String, String>> iterator2 = map2.entrySet().iterator();
        while (iterator2.hasNext()) {
            Map.Entry<String, String> entry = iterator2.next();
            System.out.println("key=" + entry.getKey() + ", value=" + entry.getValue());
        }
        System.out.println("----end----按访问顺序遍历-----");
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

输出结果：

—-start—- 按插入顺序遍历—-
key=name, value=joseph
key=age, value=33
key=job, value = 敲代码
key=hobby, value = 打篮球 
—–end—- 按插入顺序遍历—–

—-start—- 按访问顺序遍历—-
key=name, value=joseph
key=age, value=33
key=hobby, value = 打篮球
key=job, value = 敲代码 
—-end—- 按访问顺序遍历—–

1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.6 WeakHashMap

WeakHashMap 中的 Weak 是“弱”的含义，即弱化版的 HashMap。key 和 value 都允许为 null，线程不安全。

3.7 HashMap 与 Hashtable 的区别

1. HashMap 只允许一个 key 为 Null（多个则覆盖），允许多个 value 为 Null，HashTable 中的 key 和 value 都不允许为 null；
2. HashMap 线程不安全，效率高，HashTable 线程安全，效率低；
3. HashMap 和 Hashtable 二者都实现了 Map 接口，HashMap 是继承于 AbstractMap，HashTable 继承于 Dictionary 类；
4. 定位存储位置逻辑不一样，HashMap 是在 key.hashcode() 后使用位运算，HashTable 是在 key.hashcode() 后使用取模；
5. 判断扩容顺序不一样，HashMap 是 put() 之后扩容，HashTabel 是 put() 之前扩容；
6. 初始容量不一样，HashMap 默认 16，HashTabel 默认 11。

3.8 HashMap 与 TreeMap 的区别

1. 数据结构不一样，HashMap 基于“数组 + 单链表”实现（达到一定条件时转为红黑树），TreeMap 基于红黑树实现 ；
2. HashMap 随机存储，TreeMap 默认按 key 的字典升序排序；
3. HashMap 只允许一个 key 为 Null（多个则覆盖)，允许多个 value 为 Null，TreeMap 的 key 不允许为 Null，但允许多个 value 为 Null；
4. HashMap 效率高，TreeMap 效率低。

四、Set

4.1 HashSet

HashSet 是用来存储没有重复元素的集合类，并且是无序的。实现了 Set 接口。底层使用 HashMap 机制实现，所以也是线程不安全。

主要属性：

//定义了一个HashMap类型的成员变量，即拥有HashMap的所有属性
private transient HashMap<E,Object> map;

1
2
3

特征：

1. 不可重复
2. 无序
3. 线程不安全
4. 集合元素可以是 null，但只能放入一个 null

**使用场景：**去重、不要求顺序

**原理：**底层使用 HashMap 的 key 不能重复机制来实现没有重复的 HashSet。

4.2 TreeSet

TreeSet 实现了 SortedSet 接口，意味着可以排序，它是一个有序并且没有重复的集合类，底层是通过 TreeMap 实现。TreeSet 并不是根据插入的顺序来排序，而是字典自然排序。线程不安全。

TreeSet 支持两种排序方式：自然升序排序和自定义排序。

特征：

1. 不可重复
2. 有序，默认自然升序排序
3. 线程不安全
4. 集合元素不可以为 null

原理：

TreeSet 底层是基于 treeMap（红黑树结构）实现的，可以自定义比较器对元素进行排序，或是使用元素的自然顺序。

**使用场景：**去重、要求排序

4.3 LinkedHashSet

LinkedHashSet 是使用 HashSet 机制实现，它是一个可以保证插入顺序或是访问顺序，并且没有重复的集合类。线程不安全。

**数据结构：**数组 + 双向链表，Entry 结构：before|hash|key|value|next|after，before 和 after 用于维护整个双向链表。

特征：

1. 集合元素不可以为 null；
2. 线程不安全。

原理：

LinkedHashSet 底层使用了 LinkedHashMap 机制（比如 before 和 after），加上又继承了 HashSet，所以可以实现既可以保证迭代顺序，又可以达到不出现重复元素。

**使用场景：**去重、需要保证插入或者访问顺序

4.4 HashSet、TreeSet、LinkedHashSet 的区别

HashSet，TreeSet，LinkedHashSet 之间的区别：HashSet 只去重，TreeSet 去重并排序，LinkedHashSet 去重并保证迭代顺序。

五、队列（Queue）

Queue 是一个**先入先出（FIFO）**的集合，它有 3 种实现方式：阻塞队列、非阻塞队列、双向队列。Queue 跟 List、Set 一样，也是继承了 Collection 接口。

5.1 阻塞队列

阻塞队列是一个可以阻塞的先进先出集合，比如某个线程在空队列获取元素时、或者在已存满队列存储元素时，都会被阻塞。BlockingQueue 接口常用的实现类如下：

• ArrayBlockingQueue ：基于数组的有界阻塞队列，必须指定大小。
• LinkedBlockingQueue ：基于单链表的无界阻塞队列，不需指定大小。
• DelayQueue：基于延迟、优先级、无界阻塞队列。
• SynchronousQueue ：基于 CAS 的阻塞队列。

常用方法：

• add()：新增一个元索，假如队列已满，则抛异常。
• offer()：新增一个元素，假如队列没满则返回 true，假如队列已满，则返回 false。
• put()：新增一个元素，假如队列满，则阻塞。
• element()：获取队列头部一个元素，假如队列为空，则抛异常。
• peek()：获取队列头部一个元素，假如队列为空，则返回 null。
• remove()：执行删除操作，返回队列头部的元素，假如队列为空，则抛异常。
• poll()：执行删除操作，返回队列头部的元素，假如队列为空，则返回 null。
• take()：执行删除操作，返回队列头部的元素，假如队列为空，则阻塞。

5.2 非阻塞队列

非阻塞队列是使用**CAS（compare and set）**机制实现，类似 volatile，并发性能好。常用的阻塞队列有 PriorityQueue 和 ConcurrentLinkedQueue。

• PriorityQueue ：基于优先级的无界优先级队列
• ConcurrentLinkedDeque：基于双向链表结构的无界并发队列。

5.3 双端队列（Deque）

Deque 是一个既可以在头部操作元素，又可以为尾部操作元素，俗称为双向（双端）队列。Deque 继承自 Queue，Deque 实现类有 LinkedList、 ArrayDeque、ConcurrentLinkedDeque 等等。

• LinkedList：基于单链表的无界双端队列，允许元素为 null。
• ArrayDeque：基于数组的有界双端队列，不允许 null。

PS：如有写错请指正，感谢您阅读。

---

欢迎关注我的公众号，回复关键字“Java” ，将会有大礼相送！！！ 祝各位面试成功！！！