个人网站

面试官问"HashMap 怎么解决哈希冲突"，大部分人只能说出"链表"，但哈希冲突的解决方案不止一种——HashMap 用了其中一种，其他方案你也应该知道。

今天咱们从"什么是哈希冲突"讲起，覆盖四种经典方案，重点讲 HashMap 选择的方案和原因。

一、先说结论：哈希冲突解决方案

方案	思路	代表
链地址法	同一个桶里挂链表	HashMap、ConcurrentHashMap
开放定址法	冲突了找下一个空位	ThreadLocalMap
再哈希法	换个 hash 函数再算	数据库布隆过滤器
建立公共溢出区	冲突的统一放到溢出区	极少使用

一句话记住：HashMap 用链地址法——桶里冲突了，往链表后面挂就行，不用搬家。

二、什么是 Hash 冲突？

Hash 函数把无限的数据映射到有限的空间，冲突不可避免：

hash("abc") = 5
hash("xyz") = 5  ← 冲突！两个 key 算出了同一个桶 👈

生活类比： 哈希冲突就像两个人分到了同一个快递柜格子——柜子只有 16 个格，但快递可能有 100 件，总有格子里要放多个。

减少冲突靠两件事：

1. 好的 hash 函数——分布均匀
2. 合适的容量——不要太拥挤

但冲突不可能完全消除，所以必须要有冲突解决策略。

三、方案一：链地址法（HashMap 选用）

思路： 每个桶不只是一个位置，而是一个链表（或树）。冲突的元素往链表后面挂。

桶[0] → null
桶[1] → Entry("abc", v1) → Entry("xyz", v2) → null   👈 两个 key 都映射到桶 1
桶[2] → null
桶[3] → Entry("hello", v3) → null

HashMap 的实现（JDK 8+）：

// 新节点插入链表尾部（尾插法）
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;  // key 相同，覆盖
else {
    for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) {
            p.next = newNode(hash, key, value, null);  // 👈 尾插
            if (binCount >= TREEIFY_THRESHOLD - 1)     // 链表 ≥ 8
                treeifyBin(tab, hash);                  // 转红黑树
            break;
        }
        // ...
    }
}

为什么选链地址法？

1. 实现简单——插入不需要搬移其他元素
2. 不怕堆积——冲突多了挂链表就行，不会像开放定址那样"一个冲突引发连锁反应"
3. 适合未知数据量——不需要预知元素数量

缺点： 链表太长查找变慢，所以 JDK 8 引入红黑树优化。

四、方案二：开放定址法

思路： 冲突了就找下一个空位置，三种探测方式：

线性探测

hash(key) = 5，桶 5 已占 → 试 6 → 试 7 → 找到空位 👈

缺点： 容易"堆积"——连续占用的区域越来越大，查找越来越慢。

二次探测

hash(key) = 5，桶 5 已占 → 试 5+1²=6 → 试 5-1²=4 → 试 5+2²=9 👈

跳跃式探测，减少堆积。

双重哈希

hash1(key) = 5，桶 5 已占
步长 = hash2(key) = 3
试 5+3=8 → 试 5+6=11 👈

步长也由 hash 决定，分布更均匀。

ThreadLocalMap 使用开放定址法：

// ThreadLocalMap 的线性探测
private static int nextIndex(int i, int len) {
    return ((i + 1 < len) ? i + 1 : 0);  // 👈 下一个位置
}

为什么 ThreadLocalMap 用开放定址？ ThreadLocal 的数据量通常很小（几个到十几个），开放定址在小数据量下缓存友好，性能更好。

五、方案三：再哈希法

思路： 冲突了换一个 hash 函数再算。

hash1(key) = 5，桶 5 已占
hash2(key) = 11 → 桶 11 👈

优点： 不容易堆积。缺点： 多个 hash 函数计算开销大。

实际应用： 数据库中的布隆过滤器用多个 hash 函数，不是解决冲突而是降低误判率。

六、方案四：建立公共溢出区

思路： 主表放不冲突的，冲突的统一放到溢出区。

主表：
桶[0] → Entry A
桶[1] → Entry B
桶[2] → null（冲突的不在这）

溢出区：
Entry C（和 A 冲突）→ Entry D（和 B 冲突）→ ... 👈

查找时： 先查主表，没找到再查溢出区。

实际很少使用，因为溢出区本身就变成了另一个需要解决冲突的结构。

HashMap 解决 Hash 冲突 全景

HashMap 解决 Hash 冲突 全景

四种方案
├── 链地址法 ── 桶里挂链表/树（HashMap 选用）
├── 开放定址法 ── 找下一个空位（ThreadLocalMap 选用）
├── 再哈希法 ── 换 hash 函数重算
└── 公共溢出区 ── 冲突的放到另一个区域

HashMap 的方案：链地址法 + 红黑树
├── 链表 ── 冲突元素挂链表，尾插法
├── 红黑树 ── 链表 ≥ 8 且数组 ≥ 64 转树
├── 转回链表 ── 树节点 ≤ 6
└── 优点 ── 实现简单、不怕堆积、适合未知数据量

减少冲突的措施
├── 好的 hash 函数 ── 扰动函数（高 16 位异或低 16 位）
├── 容量是 2 的幂 ── 分布均匀
├── 合适的负载因子 ── 0.75 平衡时间和空间
└── 扩容 ── 元素过多时扩容，降低冲突概率

口诀：链地址法挂链表，开放定址找空位，
      再哈希换函数算，溢出区单独放，
      HashMap 选链地址，冲突多了变红黑树。

回答技巧与点评

标准回答

HashMap 使用链地址法解决哈希冲突——每个桶存储一个链表，hash 值相同的元素挂到同一个链表上。JDK 8 之后，当链表长度 ≥ 8 且数组长度 ≥ 64 时，链表会转为红黑树，将查找时间复杂度从 O(n) 降为 O(log n)。除了链地址法，还有开放定址法（找下一个空位，ThreadLocalMap 使用）、再哈希法（换 hash 函数重算）和公共溢出区（冲突的单独放）。HashMap 选择链地址法是因为实现简单、不怕堆积、适合数据量不确定的场景。

加分回答

1. 开放定址 vs 链地址的取舍：开放定址法缓存友好（数据在连续数组中），适合小数据量；链地址法不怕堆积，适合大数据量。ThreadLocalMap 用开放定址是因为每个线程的 ThreadLocal 数量通常很少；HashMap 用链地址是因为数据量不可预知
2. 删除操作的影响：链地址法删除很简单——从链表摘除即可；开放定址法删除不能直接清空（会导致后续元素找不到），需要标记为"已删除"（墓碑标记）。这也是 HashMap 选择链地址法的原因之一
3. 红黑树优化的本质：链地址法的问题是极端情况下链表很长，查找退化为 O(n)。红黑树优化将极端情况的时间复杂度降为 O(log n)。但正常情况下（hash 函数好、负载因子合理），链表长度很少超过 3，红黑树是防御性设计

面试官点评

这道题考的是你对哈希冲突解决方案的知识广度。只说出"链表"是不够的，至少要知道开放定址法。能对比链地址法和开放定址法的优劣、解释 HashMap 选择链地址法的原因，才算及格。如果你能从删除操作、缓存友好性、红黑树防御性设计等角度深入分析，面试官会认为你对数据结构有系统性的理解。

原文阅读

---

内容有帮助？点赞、收藏、关注三连！评论区等你 💪