Java 集合框架八股：从全景架构到 HashMap 连环追问

面试场景：从"说一下 Java 有哪些集合"开始，一路追到 HashMap 源码级细节。本文完整还原这条追问链条。

一、全景图：Java 集合框架架构

先搭骨架。Java 集合框架整体分为 两大接口体系：

Iterable (接口)
|
Collection (接口)
/ | \\
List Set Queue
/ \\ / \\ / \\
ArrayList LinkedList HashSet TreeSet PriorityQueue ArrayDeque
Vector (也实现了 LinkedHashSet LinkedList
Stack Deque) (也实现了Deque)

Map (接口) ← 独立体系，不继承Collection
/ | \\
HashMap TreeMap Hashtable
| | |
LinkedHashMap (红黑树) Properties
|
ConcurrentHashMap

1.1 Collection 体系

设计要点：

• Collection 不提供具体实现，只定义"容器能做什么"
• 所有 Collection 实现类都可以用 Iterator / foreach 遍历
• AbstractCollection / AbstractList / AbstractSet 等抽象类提供了骨架实现（模板方法模式）

1.2 Map 体系

Map 独立于 Collection，存储的是键值对映射关系：

二、HashMap 连环追问

从这里开始是面试的核心战场。面试官通常会从一个开放性问题开始，然后逐层深入。

🔥 第1问：HashMap 的底层数据结构是什么？

回答：

JDK 8 中，HashMap 采用 数组 + 链表 + 红黑树 的复合结构：

HashMap 内部结构示意：

bucket[0] → (hash, key, value, next) → (hash, key, value, next) → null ← 链表
bucket[1] → null
bucket[2] → (hash, key, value, next) → null
…
bucket[n] → TreeNode ↔ TreeNode ↔ TreeNode ← 红黑树（链表长度≥8且数组长度≥64时）

核心字段（源码级）：

// 桶数组，大小始终是2的幂
transient Node<K,V>[] table;

// 默认初始容量：16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

// 最大容量：2^30
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认负载因子：0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 链表转红黑树的阈值：8
static final int TREEIFY_THRESHOLD = 8;

// 红黑树退化为链表的阈值：6
static final int UNTREEIFY_THRESHOLD = 6;

// 树化的最小数组长度：64（数组太小时优先扩容而非树化）
static final int MIN_TREEIFY_CAPACITY = 64;

Node 节点结构：

static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // key的hash值，存下来避免重复计算
final K key;
V value;
Node<K,V> next; // 链表指针
}

一句话总结：哈希桶数组提供 O(1) 定位，链表解决哈希冲突，红黑树避免极端冲突时链表过长导致 O(n)。

🔥 第2问：HashMap 的 hash 函数是怎么设计的？为什么？

回答：

static final int hash(Object key) {
int h;
// key.hashCode() 的高16位 与 低16位 做异或
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

设计思路（两层）：

第一层：为什么要扰动？

计算桶下标时用的是 (n – 1) & hash，n 是数组长度（2的幂）。当 n 较小时（比如默认16），n-1 的二进制只有低4位有效（0000 1111），hash 的高位完全被忽略。

如果不扰动，hashCode 不同的两个 key，只要低几位相同就会撞到同一个桶 — 冲突率极高。

第二层：为什么是异或 + 无符号右移16位？

将 hashCode 的高16位与低16位做异或：让高位也参与进下标计算。这是一个时间-空间-效果的折中：

• 只做一次位运算，几乎零开销
• 让 hashCode 的所有32位都贡献到最终的桶下标
• 异或比 & 或 | 分布更均匀（50%概率混合）

为什么 key 为 null 时 hash = 0？

HashMap 允许 null 键，统一放在 0 号桶。

🔥 第3问：HashMap 的 put 方法完整流程是怎样的？

回答：

public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

putVal 的完整流程（分7步）：

put(key, value)
│
▼
① 计算 hash = hash(key)
│
▼
② 判断 table 是否为空或 length==0
┌── 是 → resize() 初始化（延迟初始化，构造时不分配空间）
│
▼
③ 计算桶下标 i = (n – 1) & hash
│
▼
④ 判断 table[i] 是否为空
┌── 是 → 直接创建新Node放入 → 跳到⑦
│
▼
⑤ 发生哈希冲突，判断当前节点类型：
│
├── 头节点正好是目标key（hash相等 && (== 或 equals)）
│ → 记录该节点为 e，准备覆盖value
│
├── 头节点是 TreeNode（红黑树）
│ → 执行 putTreeVal() 插入树
│
└── 否则是链表
→ 遍历链表，同时记录长度 binCount
├── 找到相同key → 记录节点 e，跳出
└── 遍历到末尾没找到 → 尾插法追加新节点
└── binCount >= TREEIFY_THRESHOLD – 1（即7）
→ treeifyBin() 尝试树化
└── 若 table.length < 64 → 优先扩容
若 table.length >= 64 → 转为红黑树
│
▼
⑥ 如果 e != null（存在旧值）
→ 根据 onlyIfAbsent 决定是否覆盖
→ 返回旧值
│
▼
⑦ modCount++，size++
若 size > threshold → resize() 扩容
返回 null（插入新key）

关键代码片段（putVal 核心逻辑）：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 步骤②：延迟初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步骤③④：定位桶，空则直接放
if ((p = tab[i = (n – 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 步骤⑤：冲突处理
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); // 尾插法
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) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 步骤⑦：扩容检查
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

🔥 第4问：HashMap 的扩容机制是怎样的？resize() 详解

回答：

触发时机：

扩容过程（3大步骤）：

扩容前：capacity=16, threshold=12
↓
扩容后：capacity=32, threshold=24

resize() 流程：
┌──────────────────────────────────────────┐
│ Step 1: 计算新容量和阈值 │
│ – 旧容量 > 0 → 新容量 = 旧容量 << 1 │
│ – 新阈值 = 旧阈值 << 1 │
│ – 边界保护：不超过 MAXIMUM_CAPACITY │
├──────────────────────────────────────────┤
│ Step 2: 创建新数组 newTab[newCap] │
├──────────────────────────────────────────┤
│ Step 3: 迁移数据（重哈希） │
│ 遍历每个旧桶： │
│ ├── 单节点 → 直接放入新桶 │
│ ├── 红黑树 → split 拆分 │
│ └── 链表 → 拆分为高低两条链 │
└──────────────────────────────────────────┘

链表迁移的精妙设计（核心）：

因为容量始终是 2 的幂，扩容后，一个旧桶的元素只可能落在两个新桶中：

• 原位置 i
• 原位置 + 旧容量 i + oldCap

// resize() 中链表迁移的核心代码
Node<K,V> loHead = null, loTail = null; // 低链：保持原位置
Node<K,V> hiHead = null, hiTail = null; // 高链：移到新位置
Node<K,V> next;

do {
next = e.next;
// 关键：e.hash & oldCap == 0 说明该位为0，留在原位置
if ((e.hash & oldCap) == 0) {
if (loTail == null) loHead = e;
else loTail.next = e;
loTail = e;
} else {
// 该位为1，移到 i + oldCap
if (hiTail == null) hiHead = e;
else hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);

// 低链挂到 newTab[j]
if (loTail != null) { loTail.next = null; newTab[j] = loHead; }
// 高链挂到 newTab[j + oldCap]
if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }

为什么 e.hash & oldCap 能判断位置？

旧容量 16 = 0001 0000（二进制）

扩容前，桶下标由 hash & (16-1) = hash & 0000 1111 决定（低4位）
扩容后，桶下标由 hash & (32-1) = hash & 0001 1111 决定（低5位）

变化的只是第5位（oldCap对应的位）：
– 如果 hash 的第5位为 0 → hash & oldCap == 0 → 新下标 = 旧下标
– 如果 hash 的第5位为 1 → hash & oldCap != 0 → 新下标 = 旧下标 + 16

这个设计避免了 JDK 7 中每个元素都重新 hash & (newCap-1) 的开销，扩容效率大幅提升。

JDK 7 vs JDK 8 扩容对比（重要！）：

⚠️ JDK 7 头插法死循环问题：多线程同时扩容时，transfer() 中的头插法可能导致链表成环，后续 get 操作陷入死循环。JDK 8 用尾插法 + 高低链拆分彻底解决了这个 bug。

🔥 第5问：为什么 HashMap 的容量必须是 2 的幂次方？

回答：

核心原因是 用位运算替代取模运算。

// 计算桶下标
i = (n – 1) & hash // 当 n = 2^k 时，等价于 hash % n，但快得多

展开解释：

当 n = 2^k 时，n – 1 的二进制是连续 k 个 1：

n=16: n-1 = 15 = 0000 1111
n=32: n-1 = 31 = 0001 1111

hash & (n-1) 相当于保留了 hash 的低 k 位，结果一定在 [0, n-1] 范围内，完美映射到数组下标。

如果是任意数 → 必须用 hash % n，模运算比位运算慢一个数量级。

额外好处：

// 保证容量始终为2的幂 —— tableSizeFor
static final int tableSizeFor(int cap) {
int n = cap – 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

🔥 第6问：为什么负载因子默认是 0.75？

回答：

这是时间与空间的折中，来自泊松分布的数学推导。

源码注释中的数学依据：

HashMap 源码注释给出了理想哈希下，桶中元素数量的泊松分布概率：

λ ≈ 0.5 (平均每个桶0.5个元素，对应loadFactor=0.75时)

0: 0.60653066 ← 60%的桶是空的
1: 0.30326533 ← 30%的桶有1个元素
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006 ← 千万分之六的概率达到8

当负载因子为 0.75 时，链表长度达到 8 的概率是千万分之六，几乎不可能发生。一旦真的发生了，大概率是因为 hashCode 分布不均，此时转红黑树是合理的选择。

🎯 所以 TREEIFY_THRESHOLD = 8 和 DEFAULT_LOAD_FACTOR = 0.75 是配套设计的：正常情况下不会触发树化，树化是应对极端情况的"保险丝"。

🔥 第7问：JDK 8 中 HashMap 做了哪些重大优化？

回答：

红黑树转换的细节：

• 链表 → 红黑树：binCount >= 8 且 table.length >= 64（先扩容，不行再树化）
• 红黑树 → 链表：节点数 ≤ 6 时退化为链表
• 为什么阈值是 8 不是其他数？见第6问的泊松分布 — 正常情况根本到不了 8

final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 关键判断：数组太小时优先扩容，不树化
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n – 1) & hash]) != null) {
// 转换为 TreeNode 并组织成红黑树
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null) hd = p;
else { p.prev = tl; tl.next = p; }
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}

🔥 第8问：HashMap 是线程安全的吗？有什么替代方案？

回答：

HashMap 线程不安全，具体表现在：

替代方案：

🔥 第9问：ConcurrentHashMap 如何实现线程安全？JDK 7 和 JDK 8 的区别

回答：

这是面试官的"压轴题"，考察广度（是否了解演进过程）和深度（是否看过源码）。

JDK 7：分段锁（Segment）

ConcurrentHashMap (JDK 7)

[ Segment₀ ] → [ HashEntry[] ] → 链表
[ Segment₁ ] → [ HashEntry[] ] → 链表
…
[ Segment₁₅ ] → [ HashEntry[] ] → 链表

默认 16 个 Segment（并发度 = 16）
每个 Segment 继承 ReentrantLock，独立加锁

• 不同 Segment 之间可以并发操作
• put 时先 tryLock，失败则自旋重试，超时后阻塞
• size() 先乐观统计（不加锁），不一致才全锁
• 缺点：Segment 数量初始化后不可改，哈希到 Segment 层面粒度不够细

JDK 8：CAS + synchronized

ConcurrentHashMap (JDK 8)

结构完全对齐 HashMap（数组 + 链表 + 红黑树）
同步粒度为单个桶（bin）：

put 流程：
┌──────────────────────────────────────────────┐
│ ① 桶为空 → CAS 尝试放入 │
│ ② 桶正在扩容 → 帮助迁移（helpTransfer） │
│ ③ 桶非空 → synchronized(头节点) 然后插入 │
└──────────────────────────────────────────────┘

核心代码片段（putVal）：

final V putVal(K key, V value, boolean onlyIfAbsent) {
// …
for (Node<K,V>[] tab = table;;) {
// 情况1：桶为空 → CAS 插入
if ((f = tabAt(tab, i = (n – 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
break; // CAS 成功
}
// 情况2：正在扩容 → 帮助迁移
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
// 情况3：桶非空 → 锁住头节点
synchronized (f) {
if (tabAt(tab, i) == f) { // 双重检查
// … 链表或红黑树插入逻辑（对齐 HashMap）
}
}
}
}
}

JDK 7 vs JDK 8 对比总结

为什么 JDK 8 改用 synchronized 而不是继续用 ReentrantLock？

🔥 第10问（拔高）：对比 HashMap、TreeMap、LinkedHashMap

LinkedHashMap 实现 LRU 缓存（高频考点）：

// 构造时 accessOrder=true → 按访问顺序排序
LinkedHashMap<String, String> lruCache = new LinkedHashMap<String, String>(
16, 0.75f, true // accessOrder = true
) {
@Override
protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
return size() > 100; // 超过100个元素就淘汰最老的
}
};

原理：每次 get 或 put 已存在的 key 时，afterNodeAccess() 将该节点移到链表末尾。removeEldestEntry() 默认返回 false，重写后可以在插入后自动淘汰链表头部（最久未访问的）。

三、面试追问路线图

面试中，一个 HashMap 可以问出 30+ 个问题。下面是典型的追问路线：

"说一下 HashMap"
│
├── 底层结构？→ 数组+链表+红黑树
│ └── 红黑树是什么？为什么要用？阈值为什么是8？
│ └── 链表转红黑树的条件？退化条件是6为什么不是8？
│
├── put 流程？→ 7步完整描述
│ └── 哈希冲突怎么处理？→ 链表/红黑树
│ └── equals 和 hashCode 的关系？
│ └── 为什么重写 equals 必须重写 hashCode？
│
├── hash 函数怎么设计的？→ 高16位异或低16位
│ └── 为什么这样设计？为什么是异或不是与或？
│ └── 容量为什么是2的幂？→ 位运算替代取模
│
├── 扩容机制？→ 高低链拆分
│ └── 负载因子为什么是0.75？→ 泊松分布
│ └── 多线程扩容有什么问题？→ 死循环（JDK7）
│
├── 线程安全吗？→ HashMap 不是
│ └── ConcurrentHashMap 怎么保证？→ CAS + synchronized
│ └── JDK 7 的分段锁和 JDK 8 的 CAS 区别？
│
└── 和 TreeMap / LinkedHashMap 的区别？
└── 怎么用 LinkedHashMap 实现 LRU？

四、记忆口诀

集合分类：Collection 单列 Map 双，List 有序 Set 不重

HashMap 结构：数组桶，链表链，红黑树来防蜕变

Hash 函数：高十六异或低十六，一次扰动就足够

容量 2 的幂：取模变位算，扩容高低判

负载因子 0.75：泊松分布的答案，千万之六才到八

JDK 7→8 演进：头插改尾插，死循环不发；链表改红黑，查找不再累

线程安全：HashTable 全锁已淘汰，CHM 分段变 CAS 是正道

本文基于 JDK 8 源码分析，核心逻辑在 JDK 11/17/21 LTS 中保持一致。如需深入，建议直接阅读 java.util.HashMap 和 java.util.concurrent.ConcurrentHashMap 源码。