大果冻-博客详情

HashMap-如何解决哈希冲突的？

在 Java 中，HashMap 是基于哈希表（数组 + 链表 / 红黑树）实现的键值对存储结构。

哈希冲突指的是：不同的键（key）通过哈希函数计算后，得到的哈希值相同，导致需要存储在数组的同一个索引位置。

HashMap 解决哈希冲突的核心方案是 “链地址法”（拉链法），并结合了 “链表转红黑树”“扰动函数”“动态扩容” 等机制优化性能。

具体如下：

一、核心方案：链地址法（拉链法）

链地址法是 HashMap 解决哈希冲突的基础手段，原理是：

HashMap 底层维护一个数组（称为 “哈希桶”，table），数组的每个元素是一个链表（或红黑树）的头节点。
当两个不同的 key 计算出相同的数组索引时，它们会被存储在该索引位置的链表（或红黑树）中，形成 “拉链” 结构。

例如： key1 和 key2 哈希冲突（索引均为 i），则 table[i] 会指向一个链表，key1 和 key2 对应的键值对（Node）会依次挂载到这个链表上。

二、优化机制：链表转红黑树（JDK 1.8+）

当同一个索引位置的链表过长时，查询效率会从 O(1) 退化到 O(n)（链表遍历）。为解决这个问题，JDK 1.8 引入了红黑树优化：

当链表的长度超过阈值（默认 8），且数组的长度大于等于 64 时，HashMap 会将该链表转换为红黑树（一种自平衡二叉查找树）。
红黑树的查询、插入、删除效率为 O(log n)，远高于长链表的 O(n)，保证了哈希冲突严重时的性能。

反之，当红黑树的节点数量减少到 6 个时，会重新退化为链表（因为少量节点时，链表的维护成本更低）。

三、减少冲突：扰动函数（哈希值优化）

哈希冲突的根源是 “不同 key 计算出相同索引”。HashMap 通过扰动函数（hash() 方法）优化哈希值的计算，减少冲突概率：

1. 计算 `key` 的哈希值

首先调用 key.hashCode() 得到一个初始哈希值（int 类型，32 位）。

2. 扰动函数处理

对初始哈希值进行 “扰动”（多次异或和右移），目的是让哈希值的高位与低位混合，增强哈希值的随机性，从而减少不同 key 计算出相同索引的概率。

JDK 1.8 的扰动函数实现：

static final int hash(Object key) {
    int h;
    // 关键：将哈希值的高位与低位异或，让高位参与索引计算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

3. 计算数组索引

通过扰动后的哈希值，与数组长度 n 进行 & 运算（等价于 hash % n，但更高效），得到最终的数组索引：

int index = (n - 1) & hash; // n 是数组长度（必须是 2 的幂次方）

四、动态扩容：降低哈希冲突频率

当 HashMap 中的元素数量过多时，每个哈希桶（数组索引）会存储更多元素，冲突概率增加。HashMap 通过动态扩容缓解这个问题：

1. 扩容触发条件

当元素数量（size）超过 负载因子（默认 0.75）× 数组长度（capacity） 时，触发扩容。例如：数组长度为 16，负载因子 0.75，当元素数超过 12 时，触发扩容。

2. 扩容过程

数组长度翻倍（新长度为原长度的 2 倍，且始终保持 2 的幂次方，确保 (n-1) & hash 计算索引的有效性）。
将原数组中的所有元素（链表 / 红黑树节点）重新计算索引，转移到新数组中（这个过程称为 “rehash”）。

扩容后，每个哈希桶存储的元素数量减少，哈希冲突的概率降低。

五、JDK 1.7 与 1.8 的差异补充

链表插入方式：JDK 1.7 采用 “头插法”（新节点插入链表头部），可能在多线程扩容时导致链表成环；JDK 1.8 改为 “尾插法”，避免了这个问题。
红黑树：JDK 1.7 中哈希桶仅用链表，无红黑树优化，长链表场景下性能较差；JDK 1.8 引入红黑树，优化了极端场景的性能。

总结

HashMap 解决哈希冲突的核心逻辑是：

链地址法：将冲突的元素存储在同一索引的链表 / 红黑树中；
红黑树优化：当链表过长时转为红黑树，保证查询效率；
扰动函数：优化哈希值计算，减少冲突概率；
动态扩容：通过扩大数组容量，降低每个桶的元素密度，减少冲突。

这些机制共同作用，使 HashMap 在哈希冲突存在的情况下，仍能保持高效的增删改查性能（平均时间复杂度接近 O(1)）。

HashMap如何解决哈希冲突的？