HashMap 面试准备完整指南

拼尽全力前进

236人浏览 · 2026-05-29 11:30:05

拼尽全力前进 · 2026-05-29 11:30:05 发布

一、HashMap 基础数据结构对比

JDK 1.7

结构：数组 + 链表（Entry<K,V>[] table）
节点类：Entry<K,V>，包含 hash, key, value, next
初始容量：16，负载因子 0.75，阈值 = 容量 × 负载因子

JDK 1.8

结构：数组 + 链表 + 红黑树（Node<K,V>[] table）
节点类：Node<K,V>（链表）/ TreeNode<K,V>（红黑树）
树化条件（同时满足）：
- 链表长度 ≥ 8（TREEIFY_THRESHOLD）
- 数组长度 ≥ 64（MIN_TREEIFY_CAPACITY），否则优先扩容
退化条件：红黑树节点数 ≤ 6（UNTREEIFY_THRESHOLD）退回链表

为什么是 8？ 泊松分布下，桶中元素达到 8 的概率仅约 0.00000006，是极小概率事件，此时引入红黑树性价比最高。

二、核心源码差异详解

1. hash() 扰动函数

JDK 1.7（4 次扰动）

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

JDK 1.8（1 次扰动，更高效）

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

目的：让高 16 位参与低 16 位运算，降低 (n-1) & hash 时的冲突。

2. put() 流程

JDK 1.7：先扩容后插入，头插法

1. 计算 hash → 定位桶
2. 遍历链表，若 key 存在则覆盖
3. addEntry()：若 size ≥ threshold 且当前桶非空 → 扩容
4. createEntry()：头插新节点

JDK 1.8：先插入后扩容，尾插法

1. table 为空 → resize() 初始化
2. (n-1) & hash 定位桶，桶空 → 直接放入
3. 桶非空：
   - 首节点 key 相同 → 覆盖
   - TreeNode → 红黑树插入
   - 链表 → 尾插，插入后链表长度 ≥ 8 → treeifyBin()
4. ++size > threshold → resize()

3. resize() 扩容机制

JDK 1.7：重新计算每个元素的 hash 与位置

int i = indexFor(e.hash, newCapacity); // 重新 hash
e.next = newTable[i];                   // 头插
newTable[i] = e;

JDK 1.8：巧妙利用 e.hash & oldCap

容量始终为 2 的幂，扩容后容量翻倍
元素新位置只有两种：原位置 或 原位置 + oldCap
判断条件：(e.hash & oldCap) == 0 → 留原位；否则 → 原位 + oldCap
拆成 loHead/loTail 与 hiHead/hiTail 两条链，保持原顺序

三、多线程不安全详解

1. JDK 1.7 死循环（经典面试题）

根因：头插法 + 扩容时链表反转

复现场景（两个线程 T1、T2 同时触发 resize）：

原链表：A → B → null

T1 执行到 Entry next = e.next; 后挂起
此时 T1 局部变量：e=A, next=B

T2 完成整个扩容：
  新表中链表变为：B → A → null（头插导致反转）

T1 恢复执行：
  1. 将 A 插入新表头：newTable[i] = A, A.next = null
  2. e = next = B
  3. 将 B 插入新表头：newTable[i] = B, B.next = A
  4. e = B.next = A（此时 A 指向 null，但旧的引用关系让 A.next 指向 B）
  5. 再处理 A：A.next = B（形成环！）

最终：B ⇄ A 环形链表

后续 get() 遍历该桶 → CPU 100% 死循环。

2. JDK 1.8 仍不安全的体现

虽改用尾插法解决了死循环，但仍存在：

| 问题 | 原因 | |------|------| | 数据覆盖丢失 | 两线程同时 put 到同一空桶，if ((p = tab[i = (n-1) & hash]) == null) 都判空成功，后写覆盖先写 | | size 计数错误 | ++size 非原子操作，多线程下偏小 | | 扩容期间数据丢失 | 一个线程扩容时，另一个线程 put，可能读到旧表 | | 可见性问题 | table、size 等字段未加 volatile |

四、线程安全方案对比

1. Hashtable（已过时）

所有方法加 synchronized，锁整个表
性能极差，不允许 null key/value

2. Collections.synchronizedMap()

装饰器模式，内部 synchronized(mutex) 锁对象
与 Hashtable 类似，全局锁

3. ConcurrentHashMap（推荐）⭐

JDK 1.7：分段锁（Segment）

ConcurrentHashMap
  └── Segment[]（继承 ReentrantLock，默认 16 段）
        └── HashEntry[]
              └── HashEntry 链表

并发度 = Segment 数量（默认 16）
不同 Segment 互不影响，同一 Segment 加锁
size() 不加锁先尝试 2 次，不一致则全部加锁统计

JDK 1.8：CAS + synchronized

ConcurrentHashMap
  └── Node[]（volatile）
        └── Node 链表 / TreeBin 红黑树

核心机制：

取消 Segment，锁粒度细化到单个桶的头节点
空桶：CAS（casTabAt）无锁写入
非空桶：synchronized 锁住头节点（链表头 / TreeBin）
扩容：多线程协助扩容（helpTransfer），每个线程负责一段（步长 stride）
size 统计：baseCount + CounterCell[]（类似 LongAdder 分散热点）
不允许 null key/value（避免歧义：null 究竟是不存在还是值为 null）

put 流程关键代码：

for (Node<K,V>[] tab = table;;) {
    if (tab == null) tab = initTable();           // 懒初始化（CAS）
    else if ((f = tabAt(tab, i)) == null) {
        if (casTabAt(tab, i, null, newNode)) break; // 空桶 CAS
    }
    else if ((fh = f.hash) == MOVED)
        tab = helpTransfer(tab, f);               // 协助扩容
    else {
        synchronized (f) {                         // 锁头节点
            // 链表 / 红黑树插入逻辑
        }
    }
}
addCount(1L, binCount);                            // 累加 size

五、高频面试题速查

Q1：HashMap 容量为什么必须是 2 的幂？

(n-1) & hash 替代 hash % n，位运算更快
保证散列均匀，每一位都参与运算
扩容时可用 e.hash & oldCap 快速分流

Q2：负载因子为什么是 0.75？

时间与空间的折中：太小浪费空间，太大冲突增多
泊松分布下 0.75 时单桶元素分布最理想

Q3：HashMap 为什么允许 null key，ConcurrentHashMap 不允许？

HashMap 单线程，containsKey 可区分"不存在"与"值为 null"
ConcurrentHashMap 多线程下 get 返回 null 无法判断是 key 不存在还是值就是 null，存在二义性

Q4：为什么用红黑树而不用 AVL 树？

红黑树是"弱平衡"，插入/删除旋转次数少
AVL 严格平衡，查询略快但维护成本高
HashMap 查询和写入都频繁，红黑树更均衡

Q5：1.8 为什么改成尾插法？

头插法在并发扩容时会��成环形链表
尾插法保持插入顺序，扩容时不会反转链表

Q6：ConcurrentHashMap 1.8 为什么用 synchronized 而不是 ReentrantLock？

JDK 1.6 后 synchronized 经过偏向锁、轻量级锁优化，性能接近 Lock
锁粒度已经很细（仅锁单个桶头节点），竞争少
synchronized 由 JVM 维护，节省内存（ReentrantLock 是对象需额外开销）

Q7：ConcurrentHashMap 的 size() 如何统计？

基础值 baseCount（volatile）+ CounterCell[] 数组分散热点
无竞争时 CAS 更新 baseCount
有竞争时随机选 CounterCell 更新（类似 LongAdder）
size() = baseCount + 所有 CounterCell.value 之和（弱一致性）

Q8：ConcurrentHashMap 是强一致性还是弱一致性？

弱一致性：迭代器、size()、containsValue 等不保证实时
get 操作无锁，读取的是某一时刻快照
设计权衡：牺牲强一致性换取高并发性能

Q9：如何让 HashMap 线程安全？

Hashtable（不推荐）
Collections.synchronizedMap(new HashMap<>())
ConcurrentHashMap（推荐）

Q10：默认容量 16 能不能改？建议如何预设容量？

可通过构造器指定，内部会调整为最接近的 2 的幂（tableSizeFor）
已知元素数量 N，建议初始容量 = (int)(N / 0.75) + 1，避免多次扩容

六、记忆口诀

"七头八尾，七环八覆"

1.7 头插法，1.8 尾插法

1.7 会成环，1.8 会覆盖

"八树六链六十四"

链长 8 树化，6 退化，数组 64 才允许树化

"分段变桶锁，CAS 加 sync"

CHM：1.7 Segment 分段锁 → 1.8 桶级 CAS + synchronized