⭐ 题目日期：

字节 - 2024/12/16

📝 题解：

在 Java 的 HashMap 中，哈希算法用于将键（Key）映射到哈希表的索引位置，其设计目标是减少哈希冲突并确保键值对的均匀分布。以下是 HashMap 哈希算法的定义和实现细节：

---

1. 哈希算法的核心步骤

步骤 1：获取键的原始哈希值

通过 key.hashCode() 获取键的原始哈希值（int 类型，32 位）。

步骤 2：扰动函数（二次哈希）

将原始哈希值的高 16 位与低 16 位进行异或运算（^），目的是让高位信息参与后续的索引计算，减少哈希冲突。

代码实现（JDK 8+）：

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

作用：

• 若直接使用 key.hashCode() 的低位（如 (n-1) & hashCode），当哈希表容量较小时，高位信息会被完全忽略，导致冲突概率升高。
• 通过 ^ (h >>> 16)，将高 16 位的信息“混合”到低 16 位中，使哈希值更均匀。

---

2. 索引计算

通过扰动后的哈希值，计算键在哈希表中的索引位置：

index = (n - 1) & hash;

• n：哈希表的容量（数组长度），必须是 2 的幂（如 16, 32, 64）。
• & 操作：等价于 hash % n，但效率更高（位运算替代取模）。

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

• 保证 (n - 1) 的二进制形式是全 1（如 15 → 0b1111）。
• 此时 (n - 1) & hash 相当于取哈希值的低 log2(n) 位，确保索引均匀分布在 [0, n-1] 范围内。

---

3. 哈希算法设计原则

(1) 均匀性

• 减少哈希冲突，避免键集中在少数桶中。
• 扰动函数和容量为 2 的幂共同保证均匀性。

(2) 效率

• 使用位运算（^、&）代替复杂计算，提升性能。

(3) 兼容性

• 允许 key 为 null（hash 方法对 null 返回 0）。

---

4. 示例说明

假设 key.hashCode() 为 0x12345678，哈希表容量 n = 16：

1. 原始哈希值： h = 0x12345678（二进制 0001 0010 0011 0100 0101 0110 0111 1000）。

2. 扰动操作：

   • h >>> 16（右移 16 位）：0x00001234。

   • h ^ (h >>> 16)：

     0x12345678  
     ^ 0x00001234  
     = 0x1234444C

3. 索引计算：

   • n - 1 = 15（二进制 0b1111）。
   • 0x1234444C & 15 = 0xC & 0b1111 = 12（索引为 12）。

---

5. 对比未扰动的哈希

若直接使用 key.hashCode() 计算索引：

• 0x12345678 & 15 = 0x8 & 0b1111 = 8。
• 另一个哈希值 0xABCD5678 的低 4 位也是 8，导致冲突。

扰动后的优势：

• 两个哈希值经扰动后可能变为 0x1234444C 和 0xABCD44CC，其低位不同（0xC vs 0xC），但若高位不同，扰动后的低 4 位可能不同，减少冲突。

---

6. 自定义对象的哈希优化

若使用自定义对象作为 HashMap 的键：

• 必须重写 hashCode()：确保相同对象返回相同哈希值，不同对象尽量返回不同哈希值。

• 推荐结合高位和低位信息：仿照 HashMap 的扰动思想，例如：

  @Override
  public int hashCode() {
      int h = field1.hashCode() ^ (field2.hashCode() << 16);
      return h ^ (h >>> 16); // 进一步扰动
  }

---

总结

HashMap 的哈希算法通过以下设计确保高效和低冲突：

1. 扰动函数：混合高/低位信息，避免低位重复导致的冲突。
2. 位运算优化：用 & 代替 %，提升计算效率。
3. 容量为 2 的幂：保证索引均匀分布。

理解这一设计有助于编写高效的哈希函数，并优化 HashMap 在实际应用中的性能。