面试追问地图
| 主问题 | 必讲关键点 | 下一层追问 |
|---|---|---|
| ArrayList | 数组、扩容、随机访问 | 扩容倍数、删除成本、线程不安全位置 |
| LinkedList | 双向链表、节点开销 | 为什么实际使用少、缓存局部性 |
| CopyOnWriteArrayList | 写时复制、读无锁 | 内存开销、弱一致性、适用读写比例 |
| HashMap put/get | hash 扰动、桶定位、链表/红黑树 | resize、阈值 8/6、容量为何为 2 次幂 |
| HashMap 并发问题 | 数据竞争、覆盖、可见性 | JDK7 扩容环、JDK8 仍为何不安全 |
| ConcurrentHashMap | CAS + synchronized、节点级锁 | size 统计、扩容协助、复合操作原子性 |
| HashSet | HashMap Key、去重契约 | 可变对象、equals/hashCode 错误 |
| TreeMap/TreeSet | 红黑树、比较器 | compareTo 与 equals 不一致会怎样 |
| fail-fast | modCount 检测 | 为什么不是线程安全保证、如何安全删除 |
| LinkedHashMap | 双向链表、访问顺序 | LRU 实现、removeEldestEntry |
| Queue/Deque | 队列、双端队列、优先级堆 | ArrayDeque vs LinkedList、堆实现 |
| PriorityQueue | 二叉堆、最小堆顶 | 不保证遍历顺序、PriorityBlockingQueue |
| LinkedHashSet | 插入顺序链表、迭代性能 | 与 HashSet 差异、性能对比 |
| 不可变集合 | List.of、List.copyOf、unmodifiableList | 原集合变化是否影响视图 |
| Collections 工具类 | 排序、搜索、同步包装 | emptyList vs List.of、singleton 场景 |
| WeakHashMap | 弱引用 key、自动回收 | 与 HashMap 区别、value 泄漏风险 |
回答源码题时应能画出桶数组结构，并说明正常路径、扩容路径和并发边界。
一、List
ArrayList 和 LinkedList 的性能差异？
频次 ★★★★ · 难度 🟡
快答
- ArrayList：随机访问 O(1)，插删 O(n)
- LinkedList：随机访问 O(n)，插删 O(1)
- 实际使用：ArrayList 通常更快（cache locality）
深答
| 操作 | ArrayList | LinkedList |
|---|---|---|
| get(i) | O(1) | O(n) |
| add(E) | O(1)* | O(1) |
| add(i, E) | O(n) | O(1) |
| remove(i) | O(n) | O(1) |
| remove(E) | O(n) | O(n) |
*ArrayList.add() 摊销 O(1)，最坏 O(n)（扩容）
底层实现对比：
// ArrayList：数组
private transient Object[] elementData;
private int size;
public E get(int index) {
rangeCheck(index);
return elementData(index); // 直接数组访问，O(1)
}
// LinkedList：双向链表
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
}
public E get(int index) {
checkElementIndex(index);
return node(index).item; // 需要遍历，O(n)
}
// LinkedList.node() 的实现：从中点开始二分查找，仍是 O(n)
Node<E> node(int index) {
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}实际性能对比（有缓存行的影响）：
即使大量插删，ArrayList 由于 cpu 缓存 的优势，实际性能仍可能优于 LinkedList。
场景：100 万元素，头部插入 100 次
ArrayList：
- 时间复杂度：100 * 1000000 = 1 亿次移动
- 但内存连续，缓存效率高
LinkedList：
- 时间复杂度：100 次（链表插删理论上快）
- 但内存离散，缓存 miss 多，GC 压力大
- 实际性能反而不如 ArrayList
建议：
- 默认用 ArrayList
- 仅当大量头部插删时，考虑用 LinkedList
- 不要在中间频繁插删
通用概念：复杂度模型假设「每次内存访问代价相同」,而这个假设早已不成立——真正的差距来自局部性:数组连续预取,链表每个节点一次可能的 cache miss。
ArrayList 扩容机制
难度 🟡
是什么：ArrayList 底层 Object[]，初始容量 10，首次 add() 时才真正分配数组（懒加载）。扩容时计算新容量、复制整个数组。
扩容公式：newCapacity = oldCapacity + (oldCapacity >> 1)，即 1.5 倍。
// JDK 17 grow() 方法（简化）
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
// 1.5 倍扩容，充分利用移位运算
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity; // 首次：从 0 到 10
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
return elementData = Arrays.copyOf(elementData, newCapacity);
}1.5 倍的设计：① 移位运算效率高，不用算精确乘法；② 太慢（如 1.25 倍）复制次数多，太快（如 2 倍）空间浪费大。经验值 1.5 倍在时间和空间上折中。
实践：已知数据量时用 new ArrayList<>(n) 指定初始容量，避免边加边扩容的反复复制。
通用概念：add() 单次最坏 O(n)（触发复制）、摊还后 O(1)——复制的代价由此前那 n 次 O(1) 的 add 预付。按倍数扩容是这个结论成立的前提，按固定量扩容会退化成 O(n)。同一模式：Redis 渐进式 rehash、单调栈每个元素进出栈各一次。
ArrayList 为什么不是线程安全的？
难度 🟡
add() 方法分为三步：判断扩容 → elementData[size] = e → size++。多线程下会出现：
- 值为 null：两个线程同时往同一位置赋值，但只执行了一次 size++
- 索引越界：线程 A 判断不需要扩容，但线程 B 先完成了 size++ 导致越界
- size 不符：
size++非原子操作，多线程竞态导致计数丢失
ArrayList 和 Vector 的区别
难度 🟢
| 特性 | ArrayList | Vector |
|---|---|---|
| 线程安全 | ❌ | ✅（synchronized） |
| 扩容倍数 | 1.5 倍 | 2 倍（可指定增长因子） |
| 性能 | 高 | 低（同步开销） |
| 初始容量 | 懒加载（首次 add 分配） | 默认 10 |
Vector（以及 Collections.synchronizedList）属于”全方法加锁”的老一代同步方案，现代并发场景按读写比例选 CopyOnWriteArrayList（见下节）或并发队列，不要再答 Vector。
CopyOnWriteArrayList 适合什么场景？
频次 ★★★ · 难度 🟡
是什么：写时复制（Copy-On-Write）——写操作（add/set/remove）加锁后复制整个底层数组，在副本上改完再一次性替换引用；读操作完全无锁，读的是当时的旧数组。
// JDK 17 add() 方法（简化）
private transient volatile Object[] array;
public boolean add(E e) {
synchronized (lock) { // 写操作加锁
Object[] es = getArray();
int len = es.length;
es = Arrays.copyOf(es, len + 1); // 复制整个数组
es[len] = e; // 在副本上修改
setArray(es); // 替换引用（volatile 写，读线程可见）
return true;
}
}
public E get(int index) {
return elementAt(getArray(), index); // 读无锁，直接读 array
}为什么这么设计：把读写分离做到极致——读多写少的场景（事件监听器列表、黑白名单、路由配置）读路径零开销；代价是每次写都 O(n) 复制、瞬时内存翻倍，且迭代器是创建时刻的快照（弱一致），遍历期间的写入看不到。
常见追问
- 为什么它的迭代器不抛 ConcurrentModificationException？→ 迭代的是快照数组，结构性修改发生在新数组上，modCount 那套机制根本不适用
- 大列表频繁写会怎样？→ 每写复制一份，分配压力大、Young GC 频繁，写多场景是灾难——它是”读多写少”专用，不是通用线程安全 List
- 和
Collections.synchronizedList怎么选？→ 后者读也要加锁但写便宜；读远多于写选 COW，读写均衡选同步包装，写多考虑换数据结构
通用概念：写时复制复制的是整个数组,粒度极粗,所以只适合几乎不写的场景;fork 复制的是 4KB 的页,同一思想粒度差几个数量级。
二、HashMap
HashMap 的底层实现和扩容机制？
频次 ★★★★★ · 难度 🔴
快答
- 数组 + 链表/红黑树结构
- 初始容量 16，load factor 0.75
- 链表长度达到 8 转红黑树，小于 6 转回链表
- 扩容时容量翻倍，所有元素需要重新计算位置
深答
HashMap 采用数组 + 链表 + 红黑树的结构：
// JDK 8 HashMap 的数组
transient Node<K,V>[] table;
// Node 节点
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}put 方法的流程：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 1. 初始化或扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2. 计算数组下标，插入新节点
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 3. 处理哈希冲突：遍历链表或红黑树
Node<K,V> e; K k;
if (p.hash == hash && ((k = p.key) == key || key != null && key.equals(k)))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 遍历链表，找到插入位置或更新值
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 链表长度达到 TREEIFY_THRESHOLD(8) 时转红黑树
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || key != null && key.equals(k)))
break;
p = e;
}
}
if (e != null) { // 存在相同的 key，更新 value
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 4. 更新 size 和检查是否需要扩容
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}扩容机制（resize）：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 容量翻倍，阈值也翻倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
// 创建新数组，rehash 所有元素
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// 链表拆分：根据高位 bit 决定去新的位置还是原位置
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null) loHead = e;
else loTail.next = e;
loTail = e;
}
else {
if (hiTail == null) hiHead = e;
else hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}关键点：
hash(key)使用高位异或，减少哈希冲突(n - 1) & hash等价于hash % n（n 是 2 的幂）- 扩容时，链表元素根据
(hash & oldCap)决定位置 - 时间复杂度：get/put/remove 平均 O(1)，最坏 O(n)（全是哈希冲突）
常见追问
- 为什么负载因子是 0.75？→ 时间与空间的折中：太小频繁扩容浪费空间，太大碰撞率飙升。0.75 下桶内节点数近似泊松分布，长链概率已经极低
- 为什么转红黑树阈值是 8、退化阈值是 6？→ 泊松分布下单桶挂满 8 个节点的概率约千万分之六——正常业务几乎撞不到，撞到说明 hash 质量差或被哈希碰撞攻击，转树把最坏情况从 O(n) 压到 O(log n)；退化阈值取 6 留出滞后带，防止节点数在 7、8 之间抖动时反复树化/退化
- 扩容为什么必须翻倍？→ 保持容量是 2 的幂，
(n-1) & hash的取模等价才成立；而且翻倍后元素新下标只取决于 hash 新增的那一位——(hash & oldCap) == 0留原位，否则去原位置 + oldCap，一次遍历把链表拆成高低两条，不用重算任何 hash（见上面 resize 源码）
HashMap 的 get 过程？
难度 🟡
快答
- 计算 key 的 hash 值，通过
(n-1) & hash定位数组下标 - 先检查首节点是否匹配，再判断是链表遍历还是红黑树查找
深答
// JDK 17 getNode() 源码
public V get(Object key) {
Node<K,V> e;
return (e = getNode(key)) == null ? null : e.value;
}
final Node<K,V> getNode(Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
// 1. 桶数组非空 → 定位桶位置 (n-1) & hash
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & (hash = hash(key))]) != null) {
// 2. 检查首节点（大部分情况一次命中）
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 3. 首节点不匹配，进入链表/红黑树查找
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key); // 红黑树
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null); // 链表遍历
}
}
return null;
}常见追问
- 为什么检查首节点可以快速返回？→ 无冲突时一个桶只有一个节点，首节点就是目标；即使有冲突，Java 8 后链表尾部插入，新节点在尾，首节点总是最老的节点，但命中概率仍然最高
- 为什么用
(n-1) & hash而不是hash % n？→ 位运算快于取模，前提是 n 是 2 的幂（见下节）
HashMap 为什么容量是 2 的幂？
频次 ★★★★ · 难度 🟡
- 位运算等价取模：
hash & (length-1)等价于hash % length，前提是 length 为 2 的幂，位运算远快于除法 - 减少哈希碰撞：
length-1二进制全 1，能”接住”扰动后均匀的 hash 分布；若不是 2 的幂，部分索引位永远用不到，浪费空间且增加碰撞 - 扩容优化：扩容为 2 倍时，不需要重新算 hash，只需要看 hash 的某一位是 0 还是 1 来决定元素去原位置还是
原位置 + oldCap - 实践：预估容量按
期望元素数 / 0.75 + 1传入构造器（Guava 的Maps.newHashMapWithExpectedSize就是这么算的），HashMap 会自动取到不小于它的 2 的幂
HashMap 多线程下会出什么问题？
频次 ★★★★ · 难度 🔴
- JDK 7：头插法 + 并发扩容 → 迁移时两个线程交错操作同一条链表，next 指针互指成环，随后 get 走到环上死循环，CPU 100%（经典线上事故）
- JDK 8：扩容改尾插（resize 源码里的 lo/hi 双链尾插），不再成环；但依然不是线程安全的——并发 put 同一个桶会丢更新（互相覆盖）、
++size竞态导致计数错、树化过程有竞态、修改无 happens-before 保证（可见性） - 结论：JDK 8 只是把故障从”死循环”降级成”数据错误”，多线程写必须用 ConcurrentHashMap
常见追问
- JDK 7 为什么会成环？→ 头插法迁移会逆序重建链表；线程 A 挂起前记住了
e → next，线程 B 完成迁移后链表已反转，A 恢复后按旧指针继续头插，形成A ↔ B互指 - 为什么 JDK 8 不顺手做成线程安全？→ 同步有代价，单线程使用不该为此买单；线程安全是 ConcurrentHashMap 的职责，各管各的
HashMap 和 Hashtable 的区别
难度 🟢
| 特性 | HashMap | Hashtable |
|---|---|---|
| 线程安全 | ❌ | ✅（全方法 synchronized） |
| null key/value | 支持（null key 只能一个） | 不支持 |
| 初始容量 | 16 | 11 |
| 扩容 | 2 倍 | 2n+1 |
| 性能 | 高 | 低（已淘汰） |
三、ConcurrentHashMap
ConcurrentHashMap 如何保证线程安全？
频次 ★★★★★ · 难度 🔴
快答
- JDK 7：Segment 分段锁，一个 Segment 一把锁
- JDK 8：CAS + synchronized，锁定哈希桶而不是整个分段
- size() 方法变为非强一致，多次计数取最后一次结果
深答
JDK 7 分段锁：
// 默认 16 个 Segment
static final int DEFAULT_SEGMENTS = 16;
// 继承 ReentrantLock
static class Segment<K,V> extends ReentrantLock implements Serializable {
transient volatile HashEntry<K,V>[] table;
// ... put/get/remove 操作都在 Segment 级别加锁
}缺点：分段数固定，扩容困难，竞争激烈时仍然有瓶颈。
JDK 8 优化（CAS + synchronized）：
// 不再使用 Segment，直接用数组 + 链表/红黑树
transient volatile Node<K,V>[] table;
final V putVal(K key, V value, boolean onlyIfAbsent) {
// 1. 计算哈希值
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// 2. CAS 操作：如果桶是空的，直接插入
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break;
}
// 3. 如果正在扩容，帮助扩容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
// 4. synchronized 锁定该桶（不是整个表）
else {
V oldVal = null;
synchronized (f) {
// 再次检查
if (tabAt(tab, i) == f) {
if (fh >= 0) {
// 链表操作
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key, value, null);
break;
}
}
}
}
}
if (binCount != 0) {
// 链表转红黑树
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}CAS 原子操作：
// 使用 unsafe 类进行 CAS 操作
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE);
}
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v) {
return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}get 方法无锁：
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
// 不需要加锁，直接读取（因为 table 是 volatile 的）
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}size() 的弱一致性：
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 : (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n);
}
// 不能保证强一致性，因为在 size() 执行期间可能有其他线程在修改关键改进：
- 读操作无需加锁（volatile 保证可见性）
- 写操作只锁定哈希桶而不是整个表
- 支持并发扩容
- 初始化时使用 CAS 避免竞争
常见追问
- 单个操作线程安全，复合操作呢？→ 不安全。“先 get 再 put”的检查-再更新会被穿插，要用
putIfAbsent/computeIfAbsent/merge这类原子复合方法 - 为什么 key/value 都不允许 null？→ 并发语义下
get(key) == null无法区分”不存在”和”值就是 null”（HashMap 单线程可以用 containsKey 二次确认，并发下二次确认已经过期）
ConcurrentHashMap JDK 1.7 vs 1.8 的区别
频次 ★★★★ · 难度 🟡
| 特性 | JDK 1.7 | JDK 1.8 |
|---|---|---|
| 数据结构 | Segment 数组 + HashEntry 链表 | Node 数组 + 链表/红黑树 |
| 线程安全 | Segment 分段锁（ReentrantLock） | CAS + synchronized |
| 锁粒度 | 段级别 | 桶头节点级别 |
| 扩容 | 每个 Segment 独立扩容 | 整体扩容，支持多线程协助 |
| 并发度 | 默认 16 | 更高 |
ConcurrentHashMap 为什么同时用 CAS 和 synchronized？
难度 🟡
- 空槽位写入：用 CAS 乐观更新（hash 扰动后碰撞概率低，少量自旋即可完成）
- 哈希碰撞时：用 synchronized 加锁处理（碰撞频繁意味着线程竞争激烈，CAS 自旋效率低，synchronized 更合适）
四、Set 与有序容器
HashSet 的实现原理
难度 🟢
是什么：底层基于 HashMap 实现，所有元素作为 key 存入，value 统一为一个 PRESENT 常量。
// JDK 17 HashSet 源码（简化）
public class HashSet<E> extends AbstractSet<E> {
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object(); // 虚拟 value
public HashSet() { map = new HashMap<>(); }
public boolean add(E e) {
return map.put(e, PRESENT) == null; // key 存在时 put 返回旧 value，add 返回 false
}
public boolean contains(Object o) {
return map.containsKey(o);
}
public boolean remove(Object o) {
return map.remove(o) == PRESENT;
}
}通过 key 保证唯一性，但不保证有序。如需有序：TreeSet（按值排序）或 LinkedHashSet（按插入顺序）。
常见追问
- 把可变对象放进 HashSet 后修改参与 hashCode 的字段会怎样？→ 对象”失踪”：存的时候按旧 hash 落桶，改完后按新 hash 查找定位到别的桶，contains 返回 false、remove 删不掉，还会导致重复添加——哈希容器的 key 必须不可变（或至少不改参与 hash 的字段）
add()返回值的语义是什么？→ 返回 true 表示元素实际被加入（map.put 返回 null 意味着之前没有这个 key），返回 false 表示元素已存在
LinkedHashSet 和 HashSet 的区别是什么？
频次 ★★ · 难度 🟢
是什么：LinkedHashSet 继承 HashSet，底层基于 LinkedHashMap（维护插入顺序的双向链表）。HashSet 不保证迭代顺序，LinkedHashSet 按插入顺序迭代。
性能：LinkedHashSet 增删操作比 HashSet 略慢（维护链表开销），但迭代遍历更快（按链表顺序无需扫描数组空位）。
TreeMap 和 TreeSet：什么时候用红黑树容器？
频次 ★★ · 难度 🟡
是什么：红黑树实现的有序 Map/Set。key 按 Comparable/Comparator 排序，增删查 O(log n)；核心价值是 HashMap 给不了的有序能力——有序遍历、范围查询（subMap/headMap）、最近匹配（floorKey/ceilingKey/firstKey）。
选型：需要排序或范围操作才用 TreeMap/TreeSet，否则 HashMap/HashSet 的 O(1) 更快。典型场景：按时间戳范围取数据、一致性哈希环（TreeMap.ceilingEntry 找顺时针第一个节点）。
常见追问
- compareTo 与 equals 不一致会怎样？→ TreeMap 判定”同一个 key”只看
compareTo == 0，不调 equals。经典例子是 BigDecimal：0.1和0.10在 HashSet 里是两个元素（equals 连标度比），在 TreeSet 里是一个（compareTo 数值相等）——同一组对象换个容器语义就变，见Java基础”BigDecimal”一节 - TreeMap 的 key 为什么不能是 null？→ 定位要调 compareTo，null 没法参与比较（HashMap 允许一个 null key，hash 直接按 0 处理）
- 为什么用红黑树而不是 AVL？→ 红黑树是”近似平衡”，插删触发的旋转次数更少（均摊 O(1)），读写均衡的容器更划算；AVL 更严格平衡、查询略快但写代价高
LinkedHashMap 实现 LRU 缓存
频次 ★★★★ · 难度 🟡 · 高频：字节/美团
LinkedHashMap 通过 accessOrder 和 removeEldestEntry 实现 LRU（最近最少使用）淘汰。算法题 146. LRU 缓存 的手写双向链表版就是在模仿 LinkedHashMap 的行为。
核心原理：
accessOrder = true：每次 get/put 访问过的节点移到链表尾部（最新访问）removeEldestEntry(Map.Entry)：插入后回调，size() > capacity时返回 true 淘汰链表头部（最久未访问）
class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75f, true); // accessOrder=true
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity; // 超过容量淘汰队头
}
}为什么这样就能实现 LRU？
- 每次访问（get/put）将该条目移到双向链表尾部
removeEldestEntry在插入后自动检查容量- 超容量时移除链表头部（最久未访问的条目）
- 全部操作 O(1)，无需手动管理指针
横向对比：
| 方案 | 实现复杂度 | 性能 | 面试推荐 |
|---|---|---|---|
| LinkedHashMap | 几行代码 | O(1) | 日常可用 |
| 手写双向链表 + Map | 50+ 行 | O(1) | 算法题考核 |
| 继承 + 重写 | 最简洁 | O(1) | 体现对框架的熟悉 |
关联题： 146. LRU 缓存 手写版；460. LFU 缓存 按频率淘汰（用 LinkedHashSet 代替 LinkedHashMap）
五、Queue / Deque / PriorityQueue
频次 ★★★ · 难度 🟢
接口与实现类
Queue (FIFO)
├── LinkedList — 双向链表实现的队列/双端队列
├── PriorityQueue — 基于数组的二叉堆（默认小顶堆）
├── ArrayDeque — 循环数组实现的双端队列（推荐替代 LinkedList）
└── DelayQueue — 延迟队列，元素到期才可取出ArrayDeque vs LinkedList
| 维度 | ArrayDeque | LinkedList |
|---|---|---|
| 底层 | 循环数组 | 双向链表 |
| 随机访问 | ❌（不支持，这是 Deque 不是 List） | ❌（O(n)，但实现了 List 接口） |
| 头尾插入/删除 | O(1)，扩容时均摊 | O(1) |
| 内存开销 | 连续内存、缓存友好 | 每个节点有前后指针 + 对象头开销 |
| null | ❌ 不允许 | ✅ 允许 |
结论：作为队列/栈，ArrayDeque 优先于 LinkedList——性能更好、内存更省。LinkedList 的优势是同时实现了 List 和 Deque 两个接口。
PriorityQueue（优先队列）
是什么：基于数组存储的二叉堆，默认小顶堆（peek() 返回最小元素），通过 Comparator 可改为大顶堆。
核心特性：
- 底层
Object[]，逻辑上是完全二叉树：queue[n]的子节点是queue[2n+1]和queue[2n+2] - 插入（
offer()）：尾部追加 → 上浮（siftUp），O(log n) - 删除堆顶（
poll()）：堆顶替换为尾部 → 下沉（siftDown），O(log n)
// JDK 17 siftUp / siftDown 源码（简化）
private void siftUp(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1; // 父节点索引
Object e = queue[parent];
if (key.compareTo((E) e) >= 0) break; // 满足堆序，停止
queue[k] = e; // 父节点下沉
k = parent;
}
queue[k] = x; // 插入目标位置
}
private void siftDown(int k, E x) {
int half = size >>> 1; // 只需下滤到非叶节点
while (k < half) {
int child = (k << 1) + 1; // 左子节点
Object c = queue[child];
int right = child + 1;
if (right < size && ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right]; // 取较小的子节点
if (key.compareTo((E) c) <= 0) break; // 满足堆序，停止
queue[k] = c; // 子节点上浮
k = child;
}
queue[k] = x;
}- 删除任意元素（
remove(Object)）：找到元素 O(n) + 下沉/上浮 O(log n)，总 O(n) - 非线程安全，线程安全版用
PriorityBlockingQueue - 扩容：小于 64 时翻倍 +2，否则扩容 50%
// 大顶堆：取前 k 个最小元素
Queue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);常见追问：
- PriorityQueue 和 TreeMap 怎么选？→ PriorityQueue 只保证堆顶有序，适合动态 Top-K；TreeMap 全局有序，适合范围查询和排序遍历
- 堆排序和 PriorityQueue 的关系？→ PriorityQueue 的
poll()依次取出的就是升序序列，等价于堆排序，但用额外数组存储结果，不是原地排序 - 如何实现延迟队列？→
DelayQueue包装PriorityQueue，元素实现Delayed.getDelay()，poll()时检查过期时间
BlockingQueue（阻塞队列）
频次 ★★★★ · 难度 🟡
是什么：支持在队列空时阻塞消费者、队列满时阻塞生产者的线程安全队列。常用于生产者-消费者模型。
常用实现类：
| 实现类 | 底层 | 有界/无界 | 锁策略 | 特性 |
|---|---|---|---|---|
| ArrayBlockingQueue | 循环数组 | 有界 | 单锁（共用锁） | 容量固定，支持公平/非公平 |
| LinkedBlockingQueue | 单向链表 | 可选有界 | 双锁（takeLock/putLock） | 默认 Integer.MAX_VALUE，吞吐高 |
| SynchronousQueue | 无容量 | 0 容量 | 双栈/双队列 | 每个 put 必须等一个 take，直传不缓存 |
| PriorityBlockingQueue | 二叉堆 | 无界 | 单锁 | PriorityQueue 的线程安全版 |
| DelayQueue | 封装 PriorityQueue | 无界 | 单锁 | 元素到期才可取出 |
| LinkedTransferQueue | 链表 | 无界 | CAS（无锁） | 支持 tryTransfer 直接交付 |
ArrayBlockingQueue vs LinkedBlockingQueue：
- Array 容量固定，且使用同一把锁管理入队出队；Linked 双锁分离，入队出队互不阻塞，吞吐更高
- Array 预分配连续内存，GC 友好；Linked 每个节点是独立对象，节点数多时 GC 压力大
- 生产上做有界队列推荐 ArrayBlockingQueue（可控 + 省内存），但高并发吞吐场景要考虑双锁优势
SynchronousQueue 的特殊性：
- 内部不存储任何元素，
put()必须阻塞到另一个线程take()，反之亦然。适合”直接交付”场景——C3P0/Druid 连接池的等待队列、Executors.newCachedThreadPool 用它 - 相当于”线程之间的握手”，吞吐比有缓冲队列低但延迟更低
队列满/空时的行为（offer vs put vs add）：
| 方法 | 满时 | 空时 |
|---|---|---|
add(e) | 抛 IllegalStateException | — |
offer(e) | 返回 false | — |
offer(e, t, unit) | 阻塞 t 时间后返回 false | — |
put(e) | 阻塞直到有空间 | — |
poll() | — | 返回 null |
poll(t, unit) | — | 阻塞 t 时间后返回 null |
take() | — | 阻塞直到有元素 |
remainingCapacity() | 可用容量 | — |
常见追问：
- ArrayBlockingQueue 的公平锁会影响什么？→ 公平模式下，等待最久的线程优先获得锁，减少饥饿但降低吞吐（CAS 次数更多）
- LinkedBlockingQueue 为什么用双锁？→ 入队操作只改 tail，出队只改 head，两把锁并发执行互不阻塞，提高吞吐。这是与 Array（同一把锁）的核心差异
- 无界队列有什么风险？→ 生产者速度 > 消费者时队列无限膨胀，可能 OOM（
newFixedThreadPool+ LinkedBlockingQueue 不设上限的经典陷阱）
六、遍历与 fail-fast
List 遍历中能修改元素吗？
频次 ★★★ · 难度 🟡
- 普通 for 循环：可以
set()替换值 - foreach 循环：
add/remove会抛ConcurrentModificationException（modCount 变化），但list.set()不会 - Iterator：推荐用
Iterator.remove()或ListIterator.set()安全修改
fail-fast 机制是怎么实现的：集合内部用 modCount 记录结构性修改次数（增删算，set 不算）；迭代器创建时把它抄成 expectedModCount，每次 next() 比对，不一致立刻抛 CME。
// JDK 17 ArrayList.Itr 源码（简化）
private class Itr implements Iterator<E> {
int expectedModCount = modCount; // 创建时快照
public E next() {
checkForComodification();
// ... 正常 next 逻辑
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
public void remove() {
// ... 调用 ArrayList.this.remove() 后同步 expectedModCount
expectedModCount = modCount; // 同步，避免下次 next 抛异常
}
}foreach 是 Iterator 的语法糖，所以行为一致。remove() 后同步 expectedModCount 是为什么 Iterator.remove() 安全而 list.remove() 不安全的源码依据。
它不是线程安全保证：fail-fast 是”尽力而为的 bug 探测器”——单线程 foreach 里 remove 也会触发；反过来多线程下也可能恰好错过检测。真正的并发安全靠并发容器：CopyOnWriteArrayList / ConcurrentHashMap 的迭代器是 fail-safe（快照或弱一致），不抛 CME，代价是可能读到旧数据。
安全删除的三种姿势：it.remove()（会同步 expectedModCount）、list.removeIf(predicate)（内部迭代）、并发场景直接用并发容器。
ListIterator 和 Iterator 的区别是什么？
是什么：ListIterator 是 Iterator 的子接口，专为 List 设计，支持双向遍历（hasPrevious() / previous()）、在迭代中修改（set() 替换上次返回的元素，add() 在当前位置插入）、获取索引（nextIndex() / previousIndex()）。Iterator 只能单向遍历 + remove。
如何实现一个不可变的集合？
是什么：JDK 提供了三种方式创建不可变集合：
Collections.unmodifiableList(list)：包装原集合，修改操作抛UnsupportedOperationException，但原集合变化仍会反映到包装视图List.copyOf(collection)（Java 10+）：创建独立副本，原集合后续变化不影响List.of(e1, e2, e3)（Java 9+）：直接创建不可变集合，null 元素会抛 NPE
为什么需要不可变集合：线程安全（天然，不需要同步）、防御性编程（表明”这个集合不应该被修改”）、作为常量共享。
七、工具类与特殊容器
Collections 工具类常用方法
频次 ★★★ · 难度 🟢
是什么：java.util.Collections 是操作集合的静态工具类，提供排序、搜索、同步包装、不可变包装等方法。
常用方法：
| 分类 | 方法 | 说明 |
|---|---|---|
| 排序 | sort(List) | 自然排序，要求元素实现 Comparable |
| 搜索 | binarySearch(List, key) | 二分查找，前提是列表已排序 |
| 反转 | reverse(List) | 反转列表元素顺序 |
| 打乱 | shuffle(List) | 随机打乱元素顺序 |
| 极值 | min(Collection) / max(Collection) | 获取最小/最大元素 |
| 频率 | frequency(Collection, Object) | 统计元素出现次数 |
| 不相交 | disjoint(Collection, Collection) | 判断两个集合是否有交集 |
| 填充 | fill(List, Object) | 用指定元素替换列表所有元素 |
| 复制 | copy(List, List) | 将源列表复制到目标列表 |
| 旋转 | rotate(List, int) | 旋转列表元素 |
| 交换 | swap(List, int, int) | 交换指定位置元素 |
同步包装：synchronizedList(list) / synchronizedMap(map) / synchronizedSet(set)——对集合的所有方法加 synchronized 块，适合需要简单同步包装的场景。但迭代器仍需外部同步（不会自动加锁），且复合操作（如”先检查再添加”）也不安全。
不可变包装：unmodifiableList(list) / unmodifiableMap(map)——任何修改操作抛 UnsupportedOperationException，但原集合变化会反映到视图。Java 9+ 的 List.of() 才是真正不可变。
空/单元素集合：emptyList() / emptyMap() / emptySet()（返回类型安全的空集合，不含元素）；singletonList(o) / singletonMap(k, v) / singleton(o)（返回只含一个元素的不可变集合，用于方法返回不需要修改的集合）。
常见追问：Collections.emptyList() 和 List.of() 的区别？→ 前者返回空集合，add 操作抛 UnsupportedOperationException；后者 Java 9+ 引入，也是不可变且元素不可为 null。
WeakHashMap：弱引用 Map
频次 ★★ · 难度 🟡
是什么：WeakHashMap 的 key 使用弱引用（WeakReference），当 key 不再被外部强引用时，GC 会自动回收其 Entry。与 HashMap 的区别在于 Entry 的生命周期——HashMap 的 key 只要不被主动删除就永远在，WeakHashMap 的 key 一旦失去外部强引用，下次 GC 后自动消失。
典型场景：缓存（如 ClassLoader 的缓存）、监听器注册表、ThreadLocal 的 ThreadLocalMap 的 key 就用了弱引用。
实现原理：Entry 继承 WeakReference<Object>，ReferenceQueue 记录被 GC 回收的 key。getTable() 在每次访问前先调用 expungeStaleEntries() 清理 ReferenceQueue 中已回收的 key 对应的 Entry。
private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
V value;
final int hash;
Entry<K,V> next;
Entry(K key, V value, ReferenceQueue<Object> queue, int hash, Entry<K,V> next) {
super(key, queue); // key 是弱引用
this.value = value;
this.hash = hash;
this.next = next;
}
}常见追问：
- WeakHashMap 和 HashMap 怎么选？→ 缓存场景用 WeakHashMap（key 失去引用自动清理），常规 Map 用 HashMap
- WeakHashMap 的 value 会泄漏吗？→ 会。Entry 继承 WeakReference 只让 key 弱引用，value 是强引用——WeakHashMap 的清理机制只清除 key 被 GC 的 Entry 的 value，但若清理不及时，value 仍可能泄漏。和 ThreadLocal 的泄漏道理一样（见并发编程）
- WeakHashMap 的 key 被置 null 会怎样？→ 置 null 只是失去强引用，GC 会回收弱引用指向的对象，Entry 在下一次
getTable()时被清理