HashMap是怎么解决哈希冲突的？

HashMap是怎么解决哈希冲突的？

引用

CSDN

1.

https://blog.csdn.net/2303_78263863/article/details/146211772

HashMap 解决哈希冲突主要通过以下几种方法，结合其内部数据结构和算法来高效处理：

1. 当我们往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
2. 存储时，如果出现hash值相同的key，此时有两种情况。
   a. 如果key相同，则覆盖原始值；
   b. 如果key不同（出现冲突），则将当前的key-value放入链表或红黑树中
3. 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。

所谓哈希冲突就是因为哈希值要计算的数是无限的，而要存入的位置是有限的，所以总会有一个键进行哈希计算时，会相同，解决方法有

1---开放定址法，如果发生哈希冲突，按照顺序，向前找一个空闲的位置存储。

2. 拉链法。存入链表

3---再哈希法，发生冲突后，再用另一个计算方法继续计算，直到不冲突为止

1. 拉链法（Separate Chaining）

• 核心思想：每个数组桶（Bucket）存储一个链表或红黑树，冲突的元素直接追加到同一桶中。
• 操作流程：

1. 插入时冲突：将新元素添加到链表末尾（JDK 1.8）或红黑树中。
2. 查询时冲突：遍历链表或树，通过equals()方法匹配键。

• 优点：实现简单，空间利用率高。
• 缺点：链表过长时查询效率低（时间复杂度O(n)）。

2. 链表转红黑树（JDK 1.8优化）

• 触发条件：
• 链表长度 ≥ 8。
• 当前数组容量 ≥ 64（否则优先扩容而非树化）。
• 退化条件：红黑树节点数 ≤ 6时退化为链表。
• 优势：
• 将最坏情况下的查询时间复杂度从O(n)优化为O(log n)。
• 避免极端哈希冲突导致性能骤降。

3. 哈希函数优化

• 扰动函数：高位与低位混合计算，减少冲突概率。
  java

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

• 效果：让哈希码的高位参与索引计算，避免低位重复导致的冲突。

4. 动态扩容（Rehashing）

• 触发条件：元素数量 > 容量 × 负载因子（默认0.75）。
• 扩容步骤：

1. 数组容量翻倍（如16 → 32）。
2. 重新计算元素位置：新索引 = 原索引 或 原索引 + 原容量。

• 优化点：无需重新计算哈希值，利用位运算快速定位新位置。

5. 冲突解决流程示例

插入键值对（Key-Value）

text

1. 计算Key的哈希值 → hash(key)
2. 计算桶索引 → index = (n-1) & hash
3. 检查桶是否为空：
- 空 → 直接插入新节点。
- 非空 → 遍历链表/树：
      a. 存在相同Key → 更新Value。
      b. 不存在相同Key → 插入到链表末尾或树中。
4. 树化检查（链表长度≥8且容量≥64）。
5. 扩容检查（元素总数 > 容量×0.75）。

6. 性能对比

场景 链表（JDK 1.7） 红黑树（JDK 1.8）
插入速度 O(1)（尾插法） O(log n)
查询速度 O(n) O(log n)
内存占用 低 较高（树节点结构复杂）

7. 适用场景与最佳实践

• 键设计：
• 使用不可变对象（如String、Integer）作为键。
• 正确重写hashCode()和equals()方法。
• 预分配容量：避免频繁扩容。
  java

// 预期存储100个元素，初始容量=100/0.75≈133 → 取256（2^8）
Map<String, Object> map = new HashMap<>(256);

总结

• 核心方案：拉链法 + 红黑树优化 + 动态扩容。
• 设计目标：在时间与空间效率间取得平衡，适应高频读写场景。
• 适用场景：单线程环境下的键值快速存取（如缓存、配置存储）。

通过以上机制，HashMap在大多数业务场景下能高效处理哈希冲突，同时保持优秀的读写性能。