HashMap 是怎么解决哈希冲突的？——链地址法、红黑树与扩容机制

面试指北 · 蔚来

题意

面试官问「HashMap 是怎么解决哈希冲突的」，表面在问一个数据结构问题，实际通常会连带考察几层内容：

1. 哈希冲突为什么一定会存在；
2. HashMap 底层用什么结构承接冲突元素；
3. 链表什么时候转红黑树，条件是不是只看长度 8；
4. 扩容机制如何降低冲突概率；
5. 除了 HashMap 的链地址法，还有哪些解决冲突的方案，各自优缺点是什么。

所以回答时不要只背一句「链表 + 红黑树 + 扩容」，而要讲清楚：HashMap 以链地址法为主，JDK 8 在链表过长时引入红黑树，同时通过负载因子和扩容机制从源头控制冲突概率。

结论

HashMap 解决哈希冲突的主方案是链地址法：底层是一个数组，数组的每个位置称为一个「桶」，当不同 key 计算出同一个数组下标时，就把这些元素挂在同一个桶下面的链表里。

JDK 8 之后，HashMap 的结构可以概括为：数组 + 链表 + 红黑树。当某个桶中的链表长度达到阈值 8，并且数组容量达到 64 时，链表会转为红黑树，把查询复杂度从链表的 O(n) 降低到红黑树的 O(log n)；如果容量还不足 64，则优先扩容，而不是直接树化。

同时，HashMap 通过负载因子 0.75 和扩容机制减少冲突：当元素数量超过「容量 × 负载因子」得到的阈值时，容量翻倍并重新分布元素。扩容后桶更多，冲突概率通常会下降。

一句话总结：冲突元素先挂链表，链表过长且容量足够时树化，元素过多时扩容 rehash。哈希冲突不能彻底消除，只能降低发生概率，并降低冲突后的查询成本。

要点展开

1. 哈希冲突的本质：输入无限，输出有限

哈希冲突的根源可以用「鸽巢原理」理解：被哈希的 key 在理论上是无限的，而哈希表数组长度是有限的，计算出来的下标范围也是有限的。既然不可能给每个 key 都分配一个唯一位置，就必然存在不同的 key 经过哈希计算后落到同一个数组下标的情况。

HashMap 中计算下标的逻辑大致是：

// JDK 8 中的 hash 扰动
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 计算数组下标
// index = (n - 1) & hash

其中 n 是数组容量，(n - 1) & hash 等价于「hash 对容量取模」，但要求容量是 2 的幂，所以位运算效率更高。hash 扰动把高 16 位异或到低 16 位，是为了让高位也参与下标计算，减少低位相同导致的冲突。

但无论怎么扰动，冲突仍然可能发生。所以 HashMap 必须有一套「冲突发生之后怎么办」的机制。

2. HashMap 的主方案：链地址法

链地址法的做法是：数组的每个下标不直接存一个元素，而是存一个链表头节点。当多个 key 计算出同一个下标时，它们就依次挂到这个下标对应的链表上。

JDK 8 中，链表插入采用尾插法；JDK 7 及之前采用头插法。尾插可以避免并发扩容时形成环形链表的问题，但要注意：JDK 8 的 HashMap 仍然不是线程安全的，只是改善了某些并发场景下的表现。

如上图，存在冲突的 key 直接以单向链表的方式存储。查找时先定位数组下标，再沿着链表逐个比较 key。

链地址法的优点很明显：

• 实现简单，插入和删除都比较直接；
• 删除元素时不需要像开放定址法那样做特殊标记；
• 装载因子可以超过 1，虽然 HashMap 默认控制在 0.75；
• 冲突较多时，JDK 8 还可以把链表升级为红黑树。

缺点是每个节点需要额外的指针开销，链表节点在内存中不连续，缓存局部性不如开放定址法。

3. 红黑树：把长链表的查询成本降下来

如果某个桶的链表很长，查找就退化成遍历链表，最坏时间复杂度是 O(n)。JDK 8 引入红黑树，就是为了在极端冲突情况下把查询复杂度降到 O(log n)。

但树化不是「链表长度一到 8 就立刻转红黑树」，准确条件是：

• 链表长度达到阈值 8（TREEIFY_THRESHOLD）；
• 并且 HashMap 的数组容量达到 64（MIN_TREEIFY_CAPACITY）。

如果链表长度到了 8，但数组容量还小于 64，HashMap 会优先执行扩容，而不是树化。因为容量较小时，冲突可能只是因为桶太少，扩容后元素会重新分布，链表自然可能变短。

另外，红黑树节点占用的空间大约是普通链表节点的两倍，所以不能一有冲突就树化。阈值 8 的选择和哈希分布有关：在理想哈希下，链表长度达到 8 的概率已经非常低，树化是「兜底」而不是常态。

当红黑树节点数量减少到 6（UNTRIEFY_THRESHOLD）时，又会退化为链表。8 和 6 之间留出缓冲，是为了避免在临界值附近频繁树化和退化。

4. 扩容机制：从源头降低冲突概率

HashMap 的扩容不是等「负载因子超过 0.75」才发生，而是看元素数量是否超过阈值：

threshold = capacity * loadFactor

默认初始容量是 16，负载因子是 0.75，所以默认阈值是 16 × 0.75 = 12。当 HashMap 中元素数量超过 12 时，就会触发扩容，容量翻倍到 32，新的阈值变成 32 × 0.75 = 24。

扩容的核心动作是：创建一个更大的数组，把旧数组中的元素重新分布到新数组中。JDK 8 在这里做了一个优化：元素在新数组中的位置要么保持不变，要么变成「原索引 + 旧容量」，并不需要把所有元素的 hash 全部重新计算一遍。判断依据是：

if ((e.hash & oldCap) == 0) {
    // 留在原索引位置
} else {
    // 移动到 原索引 + oldCap
}

这也是为什么 HashMap 的容量要设计成 2 的幂：扩容时可以利用位运算高效拆分链表或红黑树。

扩容本质上是用空间换时间。桶更多了，冲突概率下降，查询效率更稳定；但扩容本身需要搬运元素，也有成本。所以实际使用时如果能预估元素数量，可以在创建 HashMap 时指定初始容量，减少扩容次数。

5. 其他常见的哈希冲突解决方案

线性探测法

开放定址法是一类方案，线性探测法是其中一种，不能说「开放定址法也称线性探测法」。线性探测的做法是：当某个 key 计算出的位置已经被占用时，就按照固定步长（通常是向后 +1）在哈希表中寻找下一个空闲位置，把冲突元素放进去。

如图，索引 1 的位置已经存了 key=name，再添加 key=hobby 时，假设计算出的索引也是 1，就发生了哈希冲突。线性探测会按顺序继续找下一个空闲位置，把 hobby 存进去。

Java 中更准确的说法是：ThreadLocal 内部的 ThreadLocalMap 使用了开放定址法中的线性探测来解决冲突。ThreadLocalMap 的 key 是弱引用的 ThreadLocal 对象，发生冲突时向后寻找空槽。

线性探测的优点是数组连续、缓存友好、不需要额外指针；缺点是容易产生「聚集」现象：一旦某段区域被占满，后续冲突元素会不断向后挤，查找和插入都可能变慢。另外删除元素比较麻烦，不能直接把槽位置空，否则会截断探测链，通常需要标记为「已删除」或做清理。

链式寻址法

链式寻址法和链地址法本质上是同一类思路：把冲突的 key 用链表串起来。HashMap 就是典型代表。前面已经展开，这里不再重复。需要记住的是：HashMap 的链表不是单独挂在数组外面的「溢出链表」，而是每个数组下标对应一个桶，桶内用链表或红黑树组织冲突元素。

再 Hash 法

再 Hash 法的思路是：先用第一个哈希函数计算 key，如果发生冲突，再用第二个哈希函数计算，仍然冲突就继续用下一个哈希函数，直到找到空闲位置或达到上限。

这种方案可以减少某些特定哈希函数带来的聚集，但每次冲突都可能增加一次哈希计算，性能有额外开销；如果哈希函数设计不好，也可能多次计算后仍然冲突。实际系统中通常会配合其他策略使用，而不是无限再哈希。

建立公共溢出区

有的资料写成「公共移除区」，更常见的叫法是「公共溢出区」。做法是把哈希表分成两部分：基本表和溢出表。正常元素放在基本表中，凡是发生冲突的元素，统一放到溢出表中。

查找时先查基本表，找不到再去溢出表查。这种方案实现简单，适合冲突较少的场景；但如果冲突元素很多，溢出表本身也会变长，查找效率同样会下降。

6. 为什么 HashMap 选择链地址法而不是开放定址法

HashMap 是一个通用容器，需要支持较多的增删操作，并且允许元素数量增长。链地址法在删除时更直接，冲突多时还能通过树化兜底；开放定址法则对装载因子更敏感，删除需要特殊处理，冲突严重时探测链会变长。

所以 HashMap 选择「链地址法 + 红黑树 + 扩容」的组合：链地址法负责承接冲突，红黑树负责处理长链表，扩容负责从整体上降低冲突概率。三者配合，才构成完整的冲突解决方案。

易错点与对比

方案	基本做法	优点	缺点	典型例子
链地址法	同一桶的冲突元素挂链表，过长转红黑树	删除方便，冲突容忍度高，实现成熟	有指针开销，缓存局部性一般	HashMap
开放定址法 / 线性探测	冲突后按顺序找下一个空槽	数组连续，缓存友好，无指针开销	易聚集，删除麻烦，装载因子不能太高	ThreadLocalMap
再 Hash 法	冲突后换另一个哈希函数再算	可打散特定聚集	计算成本增加，可能仍冲突	某些哈希表实现
公共溢出区	基本表 + 溢出表，冲突元素放溢出表	实现简单，基本表结构清晰	溢出表可能退化，查找需两次	冲突较少的场景

几个高频易错点：

1. 树化不是只看链表长度 8。 还要看数组容量是否达到 64；容量不足时优先扩容。
2. 负载因子不是「超过 0.75 就扩容」。 负载因子是构造时设定的比例，实际触发条件是元素数量超过 capacity × loadFactor。
3. JDK 8 扩容不是把所有 hash 全部重算。 而是利用 hash & oldCap 判断元素留在原位置还是移动到「原索引 + 旧容量」。
4. ThreadLocal 本身不是哈希表。 使用线性探测的是它内部的 ThreadLocalMap。
5. 开放定址法不等于线性探测法。 开放定址法是一类方法，线性探测只是其中一种。
6. HashMap 线程不安全。 JDK 8 改善了头插导致的问题，但并发 put 仍可能丢数据、size 不准，并发场景应使用 ConcurrentHashMap。
7. 红黑树退化阈值是 6，不是 8。 8 和 6 之间留缓冲，避免频繁转换。
8. 「公共移除区」更常见的叫法是「公共溢出区」。 面试表达时用「公共溢出区」更准确。

小结

回答「HashMap 怎么解决哈希冲突」，可以按这个顺序展开：

1. 先点明哈希冲突不可避免：输入无限、数组下标有限；
2. HashMap 主方案是链地址法，冲突元素挂在同一个桶的链表上；
3. JDK 8 在链表长度达到 8 且容量达到 64 时转为红黑树，降低长链表查询成本；
4. 元素数量超过「容量 × 0.75」时扩容，容量翻倍并重新分布元素，从源头降低冲突概率；
5. 对比线性探测、再哈希、公共溢出区等方案，说明 HashMap 为什么选择链地址法。

这样既回答了「是什么」，也解释了「为什么」和「边界条件」，比只背「链表转红黑树」更完整。