java集合

集合体系

Java 集合大体可以分成两套体系：Collection 和 Map。

Collection 主要表示一组元素，下面又分成 List、Set 和 Queue。

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


Collection
├── List
│   ├── ArrayList
│   └── LinkedList
│
├── Set
│   ├── HashSet
│   ├── LinkedHashSet
│   └── TreeSet
│
└── Queue / Deque
    ├── ArrayDeque
    ├── PriorityQueue
    └── LinkedList

List 的特点是有序、可以重复。

Set 的特点是元素不能重复。

Queue 主要用于队列场景，通常按照一定顺序取出元素；Deque 则支持从两端插入和删除。

Map 不属于 Collection 体系，它保存的是一组 key-value 键值对。

1
2
3
4
5


Map
├── HashMap
├── LinkedHashMap
├── TreeMap
└── ConcurrentHashMap

其中 key 通常不能重复，一个 key 对应一个 value。

ArrayList 和 LinkedList

ArrayList 底层是动态数组，LinkedList 底层是双向链表。

两者最核心的区别比较简单：

1
2
3
4
5
6
7


ArrayList
→ 随机访问 O(1)
→ 中间插入删除需要移动元素

LinkedList
→ 随机访问 O(n)
→ 已知节点位置时插入删除只需要修改指针

真正面试里更容易继续追问的是 ArrayList 的扩容机制。

ArrayList 底层使用 Object[] elementData 保存元素。

JDK 8 以后，使用默认构造方法创建：

1

new ArrayList<>();

一开始并不会立即分配长度为 10 的数组，而是先使用一个空数组。

第一次真正添加元素时，才会把容量扩到默认容量：

1

10

后续如果继续添加元素，发现当前数组已经放不下，就会进行扩容。

新的容量通常按：

1

newCapacity = oldCapacity + (oldCapacity >> 1)

计算，也就是大约扩容到原来的 1.5 倍。

例如：

1

10 → 15 → 22 → 33 ...

扩容时并不是直接把原数组“变大”，因为 Java 数组长度创建以后不能修改。

实际过程是：

1
2
3


创建一个更大的新数组
→ 把旧数组中的元素复制过去
→ elementData 指向新数组

底层会通过类似 Arrays.copyOf() 的方式完成复制。

所以 ArrayList 扩容本身是有成本的，如果提前知道集合大概有多少元素，可以直接指定初始容量：

1

new ArrayList<>(1000);

避免多次扩容和数组复制。

另外，ArrayList 删除元素时也要注意。

例如删除中间元素：

1

list.remove(index);

后面的元素需要整体向前移动，所以时间复杂度通常是 O(n)。

LinkedList 底层节点大致包含：

1
2
3


prev
item
next

它查找某个下标时，并不是固定从头开始，而是会根据下标判断距离头部近还是尾部近：

1
2
3
4
5


index < size / 2
→ 从头向后找

否则
→ 从尾向前找

但整体随机访问复杂度仍然是 O(n)。

另外，LinkedList 同时实现了 List 和 Deque，所以它既可以当普通链表使用，也可以当队列或双端队列使用。

不过实际开发中，大多数普通 List 场景还是优先使用 ArrayList；如果需要双端队列，通常也更推荐 ArrayDeque，而不是 LinkedList。

HashMap

HashMap 底层本质上是一个数组 + 链表 / 红黑树的哈希表。

最外层是一个数组，数组中的每一个位置都可以看成一个桶。

一个桶里可能没有元素，也可能只有一个节点；如果多个 key 经过计算以后落到了同一个桶里，这个桶内部就需要额外的数据结构来保存这些节点。

JDK 8 以后，桶内部可能是链表，也可能是红黑树：

1
2
3


table[3]
   ↓
Node A → Node B → Node C

或者：

1
2
3


table[3]
   ↓
红黑树

所以 HashMap 查找一个 key 时，实际上分成两步。

第一步，根据 key 的 hashCode() 计算 hash，再根据数组长度算出它属于哪个桶。

HashMap 会先对原始 hash 做一次扰动：

1

hash = h ^ (h >>> 16);

然后通过：

1

index = hash & (n - 1);

计算数组下标，其中 n 是数组长度。

这里需要注意：落到同一个桶，不代表两个 key 的完整 hash 一定相同。

因为计算桶下标时只使用了 hash 的一部分位。

例如数组长度是 16：

1

index = hash & 15

实际上主要看 hash 的低 4 位。

因此两个完整 hash 不同的 key，只要最终计算出来的 index 相同，也会进入同一个桶。

确定桶以后，才进入第二步：在桶内部查找具体节点。

如果桶是空的，就直接插入新节点。

如果桶里是链表，就沿着链表逐个比较节点。HashMap 会先比较 hash，再比较：

1

key == oldKey

或者：

1

key.equals(oldKey)

如果找到相同 key，就直接覆盖原来的 value；如果一直找到链表末尾都没有找到，就把新节点加入链表。

所以 hash 只负责确定进入哪个桶，真正桶内的位置则由链表遍历或者红黑树查找决定。

为什么桶内要同时使用链表和红黑树

哈希冲突不可避免。

如果冲突节点很少，用链表保存最简单，额外内存开销也小。

但如果大量 key 都进入同一个桶，链表会越来越长，查找复杂度可能从 HashMap 理想情况下的 O(1) 退化成：

1

O(n)

所以 JDK 8 引入了红黑树。

当桶内节点很多时，转换成红黑树以后，查找复杂度可以降低到大约：

1

O(log n)

但红黑树本身需要维护父节点、左右子节点、颜色等额外信息，所以节点较少时没有必要直接使用红黑树。

HashMap 因此采用的是一种折中设计：冲突少时使用链表，冲突严重时再转换成红黑树。

和树化相关的几个经典参数是：

1
2
3


TREEIFY_THRESHOLD = 8
UNTREEIFY_THRESHOLD = 6
MIN_TREEIFY_CAPACITY = 64

TREEIFY_THRESHOLD = 8 表示链表长度达到一定程度以后，会考虑树化。

但并不是只要达到 8 就一定变成红黑树。

还要求整个 HashMap 的数组容量至少达到64，如果数组还比较小，HashMap 更倾向于先扩容，希望通过增加桶数量，把原来冲突的节点重新分散开。优先进行扩容的原因在于:** 数组还小的时候，优先扩容解决“桶太少导致的冲突”；数组已经足够大了，冲突仍然严重，才说明这个桶确实需要树化。 **

UNTREEIFY_THRESHOLD = 6 则表示红黑树中的节点数量降到比较低的水平时，可以退化回链表。

之所以树化阈值是 8，而退化阈值是 6，而不是都用同一个数字，是为了避免结构在临界点附近频繁切换：

1
2
3
4


链表
→ 红黑树
→ 链表
→ 红黑树

中间留出一定缓冲，可以减少这种转换开销。

HashMap 的扩容

HashMap 底层数组长度不是固定的，会随着元素越来越多自动扩容。

默认负载因子是：

1

0.75

扩容阈值通常可以理解成：

1

threshold = capacity × loadFactor

例如当前数组容量是 16：

1

threshold = 16 × 0.75 = 12

这里判断的不是“已经用了多少个桶”，而是 HashMap 中一共有多少个键值对，也就是 size。

比如数组长度是 16，但 15 个元素全部因为哈希冲突挤在同一个桶里：

1
2


table[3]
→ Node1 → Node2 → ... → Node15

此时仍然是：

1
2


capacity = 16
size = 15

而不是 size = 1。

所以 HashMap 的扩容依据是：

元素总数超过容量和负载因子计算出的阈值，而不是桶使用率超过 75%。

扩容时数组容量通常直接翻倍：

1

16 → 32 → 64 → 128

扩容以后，key 的 hash 本身并不会变化，但因为数组长度变了，计算出来的桶下标可能发生变化。

原来：

1

index = hash & 15

扩容到 32 以后：

1

index = hash & 31

所以旧数组里的所有节点都需要迁移到新数组。

不过 JDK 8 对这个过程做了优化。

因为容量每次都是翻倍，所以一个节点扩容以后只会有两种可能：

1
2
3
4
5


留在原来的下标

或者

移动到 原下标 + oldCapacity

判断方式就是：

1

hash & oldCapacity

如果结果是 0，就留在原位置；否则就移动到：

1

原位置 + oldCapacity

例如原数组容量是 16，一个节点原来在桶 5，扩容到 32 后，它只可能去：

也就是：

因此 HashMap 扩容虽然仍然需要创建新数组，并迁移所有节点，整体成本仍然是 O(n)，但每个节点的新位置计算会非常简单。

这也是 HashMap 为什么喜欢让数组容量保持为 2 的幂。

put 的整体流程

一次 put(key, value) 可以概括成：

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


计算 hash
→ 根据数组长度计算桶下标

桶为空
→ 直接插入

桶不为空
→ 在链表 / 红黑树中查找 key

key 已存在
→ 覆盖 value

key 不存在
→ 插入新节点

链表过长
→ 满足条件时转红黑树

插入后 size 超过 threshold
→ 扩容

所以 HashMap 的核心设计可以理解成：

先通过 hash 快速缩小到一个桶，再在桶内部解决哈希冲突；当冲突严重时用红黑树降低查找成本，当整体元素越来越多时通过扩容重新分散节点。

Set、LinkedHashMap 和 TreeMap

Set 的特点是元素不能重复，其中最常见的是 HashSet 和 TreeSet。

HashSet 底层实际上就是基于 HashMap 实现的。加入一个元素时，会把这个元素作为 HashMap 的 key，而 value 使用一个固定的占位对象。

所以：

1
2


HashSet.add(element)
→ 本质上相当于 HashMap.put(element, 固定占位值)

也正因为 key 不能重复，HashSet 才能保证元素不重复。

判断是否重复，本质上还是依赖：

1
2
3


hashCode()
+
equals()

如果两个对象的 hash 和 equals 判断为相同，就会被认为是同一个元素。

TreeSet 则是基于 TreeMap 实现的，它除了保证元素不重复以外，还会按照一定规则进行排序。

LinkedHashMap 是在 HashMap 的基础上额外维护了一条双向链表。

HashMap 本身主要负责：

1

根据 key 快速查找 value

LinkedHashMap 在此基础上，还会把所有节点按照一定顺序串起来：

1

A <-> B <-> C <-> D

因此它可以保留元素的顺序。

默认情况下，LinkedHashMap 按照插入顺序维护链表，也就是先放进去的元素先遍历到。

它还可以配置成按照访问顺序维护：

1

new LinkedHashMap<>(16, 0.75f, true);

这种情况下，一个元素每次被访问以后，会被移动到链表尾部。

因此链表头部就是长期没有被访问的元素，这也是 LinkedHashMap 经常被用来实现 LRU 缓存的原因。

所以可以理解成：

1
2
3
4
5
6
7


HashMap
→ 快速查找

LinkedHashMap
→ HashMap
+ 双向链表
→ 额外维护顺序

TreeMap 的底层是红黑树。

它最大的特点是 key 会按照顺序排列，而不是像 HashMap 一样根据 hash 放到不同桶里。

例如：

1

TreeMap<Integer, String> map = new TreeMap<>();

插入：

遍历时会按照：

输出。

排序规则可以来自 key 自己实现的 Comparable，也可以在创建 TreeMap 时传入 Comparator。

因为底层是红黑树，所以 TreeMap 的查找、插入和删除复杂度通常是O(log n)，而 HashMap 在 hash 分布正常的情况下平均可以做到接近O(1)

所以两者的使用场景不同：

1
2
3
4
5
6
7


HashMap
→ 主要追求快速查找
→ 不保证 key 的排序

TreeMap
→ 需要按照 key 排序
→ 查找、插入、删除 O(log n)

TreeSet 则可以理解成使用 TreeMap 保存元素，只使用 key，不关心 value。

因此 Set 和 Map 之间有一组很直接的对应关系：

1
2
3
4
5


HashSet
→ 基于 HashMap

TreeSet
→ 基于 TreeMap

整体来看：

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


HashSet
→ 不重复，不保证顺序

TreeSet
→ 不重复，并且排序

LinkedHashMap
→ HashMap + 双向链表
→ 保留插入顺序或访问顺序

TreeMap
→ 红黑树
→ 按 key 排序

Queue 和 Deque

Queue 表示队列，通常按照先进先出的方式处理元素。

常用操作包括：

1
2
3


offer();  // 入队
poll();   // 出队
peek();   // 查看队头

Deque 是双端队列，支持从两端插入和删除，所以既可以当普通队列，也可以当栈来使用。

Java 中常见的实现有 ArrayDeque、LinkedList 和 PriorityQueue。

ArrayDeque

ArrayDeque 底层使用的是环形数组，不是普通数组直接做头删尾插。

它内部会维护类似 head 和 tail 的位置。

例如：

1
2
3


[ A ][ B ][ C ][   ][   ][   ]
  ↑
 head

从头部删除 A 时，不需要把后面的元素整体向前移动，只需要让 head 往后移动：

1
2
3


[   ][ B ][ C ][   ][   ][   ]
       ↑
      head

所以队头删除和队尾插入都可以做到 O(1)。

数组走到末尾以后，还可以从头部继续使用，因此逻辑上形成一个环：

1
2
3
4
5


        ┌───────────────┐
        ↓               │
[   ][ A ][ B ][ C ][ D ]
      ↑               ↑
     head            tail

这也是 ArrayDeque 比普通数组更适合实现队列的原因。

当数组已经放满，再继续插入元素时，ArrayDeque 会扩容。

扩容时会创建一个更大的新数组，然后把原来的元素按照逻辑顺序复制过去。

例如原来的环形结构可能是：

1
2
3
4
5
6
7


旧数组：

[ C ][ D ][   ][   ][ A ][ B ]

逻辑顺序：

A → B → C → D

扩容以后会重新整理成连续结构：

1
2
3


新数组：

[ A ][ B ][ C ][ D ][   ][   ][ ... ]

然后重新设置 head 和 tail。

所以 ArrayDeque 平时的头尾操作是 O(1)，只有扩容时需要进行一次 O(n) 的数组复制。

相比 LinkedList，两者的队头和队尾操作都可以做到 O(1)，但 ArrayDeque 使用连续数组，不需要为每个节点额外保存 prev、next 引用，缓存局部性也更好，因此普通队列和栈场景下一般更推荐 ArrayDeque。

LinkedList

LinkedList 底层是双向链表，同时实现了 List 和 Deque。

因此它也可以作为队列使用：

1

A <-> B <-> C

在头尾插入和删除时，同样只需要修改节点引用，复杂度是 O(1)。

不过每个节点需要额外维护前驱和后继引用，内存开销通常比 ArrayDeque 更大。

PriorityQueue

PriorityQueue 是优先队列，不按照普通 FIFO 顺序取元素，而是按照元素优先级决定谁先出队。

它底层使用堆结构。

默认情况下：

1

PriorityQueue<Integer> queue = new PriorityQueue<>();

使用的是小顶堆，所以每次取出的都是当前最小元素。

因此可以这样区分：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


ArrayDeque
→ 环形数组
→ 普通队列 / 双端队列 / 栈

LinkedList
→ 双向链表
→ 也可以作为 Deque

PriorityQueue
→ 堆
→ 按优先级出队

在普通队列或栈场景中，通常优先选择 ArrayDeque。

ConcurrentHashMap

ConcurrentHashMap 是线程安全的 Map，主要用于高并发读写场景。

JDK 8 以后，它的底层结构和 HashMap 很像，也是：

1
2
3


数组
+
链表 / 红黑树

区别主要在于并发控制。

如果目标桶为空，线程会优先通过 CAS 插入节点；如果桶里已经有数据，则会对当前桶的头节点加 synchronized，在锁内完成链表或红黑树的修改。

所以它不会像 Hashtable 那样把整个 Map 锁住，而是尽量把锁粒度控制在单个桶上。

可以理解成：

1
2
3
4
5
6
7
8


读操作
→ 基本无锁

桶为空时写
→ CAS

桶内发生冲突时写
→ synchronized 锁当前桶

JDK 7 的 ConcurrentHashMap 使用的是 Segment 分段锁，相当于把整个 Map 拆成多个小段，每个 Segment 单独加锁。

JDK 8 以后取消了 Segment，直接使用桶级别的并发控制：

1
2
3
4
5
6


JDK 7
→ Segment 分段锁

JDK 8
→ CAS + synchronized
→ 锁粒度细化到桶

ConcurrentHashMap 的扩容也和普通 HashMap 不一样。

扩容时，并不是固定由一个线程完成整个数组迁移，其他线程发现正在扩容后，也可以一起参与，把不同区间的桶迁移到新数组中。

可以理解成：

1
2
3
4
5
6
7
8


线程 A
→ 迁移一部分桶

线程 B
→ 迁移另一部分桶

线程 C
→ 继续协助迁移

某个桶迁移完成以后，旧数组对应的位置会放一个特殊的 ForwardingNode。

它的作用就是标记：

这个桶已经迁移完成，后续操作应该去新数组中查找。

所以扩容过程中，即使旧表和新表同时存在，其他线程也能够根据 ForwardingNode 判断数据已经迁移到哪里。

整体来看，ConcurrentHashMap 的核心设计就是：

尽量让无冲突的操作并发执行，只有真正发生竞争的位置才加锁；扩容时再通过多线程协作和 ForwardingNode 保证迁移过程中的并发安全。

CopyOnWriteArrayList

CopyOnWriteArrayList 是一种适合读多写少场景的线程安全 List。

它的核心思路是：读操作直接读取当前数组，不加锁；写操作时先复制出一份新的数组，在新数组上完成修改，最后再把内部引用指向新数组。

可以理解成：

1
2
3
4
5
6
7
8


读
→ 直接读旧数组

写
→ 加锁
→ 复制旧数组
→ 在新数组上修改
→ 替换数组引用

这样读线程和写线程不会直接操作同一个正在修改的数组，所以读操作基本不会被写操作阻塞。

代价也很明显：每次写入都要复制整个数组，因此写操作成本较高，而且修改完成到新数组替换之前，其他读线程看到的还是旧数据。

所以 CopyOnWriteArrayList 适合：

读非常频繁、写很少，并且允许短暂读取旧数据的场景。

BlockingQueue

BlockingQueue 是支持阻塞等待的线程安全队列。

普通 Queue 在队列为空时调用 poll()，通常直接返回；而 BlockingQueue 可以让线程在“没有数据”或者“没有空间”时主动等待。

例如消费者：

1

queue.take();

如果队列为空，线程会阻塞，直到有新的元素进入。

生产者：

1

queue.put(value);

如果使用的是有界队列，并且队列已经满了，生产者会阻塞，直到队列出现空位。

所以它非常适合生产者消费者模型：

1
2
3
4
5


生产者
→ put
→ BlockingQueue
→ take
→ 消费者

常见实现包括：

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


ArrayBlockingQueue
→ 数组实现
→ 有界队列

LinkedBlockingQueue
→ 链表实现
→ 可以指定容量，默认容量非常大

PriorityBlockingQueue
→ 带优先级的阻塞队列
→ 逻辑上无界

SynchronousQueue
→ 不真正存储元素
→ 每次 put 都需要等待一个 take 与之配对

线程池里的 workQueue 就是 BlockingQueue，任务处理不过来时先进入队列；如果是有界队列，队列满以后还可以继续触发线程扩容和拒绝策略。

所以两者可以简单理解成：

CopyOnWriteArrayList 用复制换取高效读；BlockingQueue 用阻塞机制协调生产者和消费者。

相关问题#

集合体系#

ArrayList 和 LinkedList#

HashMap#

为什么桶内要同时使用链表和红黑树#

HashMap 的扩容#

put 的整体流程#

Set、LinkedHashMap 和 TreeMap#

Queue 和 Deque#

ArrayDeque#

LinkedList#

PriorityQueue#

ConcurrentHashMap#

CopyOnWriteArrayList#

BlockingQueue#

相关问题

集合体系

ArrayList 和 LinkedList

HashMap

为什么桶内要同时使用链表和红黑树

HashMap 的扩容

put 的整体流程

Set、LinkedHashMap 和 TreeMap

Queue 和 Deque

ArrayDeque

LinkedList

PriorityQueue

ConcurrentHashMap

CopyOnWriteArrayList

BlockingQueue