hash | 小菜鸟

Java 中的哈希（Hash）机制：HashMap 与 Hashtable 的实现对比

哈希（Hash）是 Java 集合框架中实现高效存储和查询的核心机制，尤其是在 HashMap 和 Hashtable 中，哈希算法的设计直接影响哈希冲突的概率和性能。本文将深入解析两者的哈希计算方法、索引定位逻辑及优化策略，揭示其减少哈希碰撞的底层原理。

哈希的核心目标

哈希的核心是通过哈希函数将任意长度的输入（如对象的 hashCode）映射到固定长度的输出（如数组索引），目标是：

均匀分布：使键值对在数组中均匀分布，减少哈希冲突（不同键映射到同一索引）；
高效计算：哈希函数和索引计算应简单快速，避免额外性能损耗。

HashMap 的哈希机制（JDK 1.8）

HashMap 采用 “二次哈希 + 与运算” 的方式，通过扰动函数增强哈希值的随机性，减少冲突。

哈希值计算（扰动函数）

HashMap 对键的原始哈希值（key.hashCode()）进行二次处理，代码如下：

static final int hash(Object key) {
    int h;
    // 1. 若 key 为 null，哈希值为 0；否则计算 h = key.hashCode()
    // 2. 高 16 位与低 16 位异或（h ^ (h >>> 16)），增强随机性
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

扰动的原因：

原始 hashCode 是 32 位整数，但数组容量（n）通常较小（默认 16，最大 2^30），导致计算索引时仅低 log2(n) 位有效（高位被忽略）。
例如：若两个键的 hashCode 高位不同但低位相同，直接使用原始哈希值会导致索引冲突。
扰动通过 “高 16 位异或低 16 位”，将高位信息混入低位，增加低位的随机性，减少冲突。

索引计算（与运算）

通过扰动后的哈希值计算数组索引：

1	int index = (n - 1) & hash; // n 为数组容量（2 的幂）

原理：

当 n 是 2 的幂时，n - 1 的二进制表示为 “全 1”（如 n=16 时，n-1=15 → 1111）。
与运算（&）等价于对 hash 取模（hash % n），但计算速度更快（位运算效率高于取模）。
例如：hash=25，n=16 时，(16-1) & 25 = 15 & 25 = 9（等价于 25 % 16 = 9）。

示例：扰动前后的对比

假设两个键的原始 hashCode 为：

h1 = 0b11000000000000001111000011111111（高位不同，低位相同）
h2 = 0b10000000000000001111000011111111
未扰动时，低 4 位均为 1111，n=16 时索引均为 15（冲突）。
扰动后（h ^ (h >>> 16)）：
- h1 扰动后低 4 位可能变为 0111
- h2 扰动后低 4 位可能变为 1111
  索引分别为 7 和 15，冲突解决。

Hashtable 的哈希机制（JDK 1.8）

Hashtable 采用 “取绝对值 + 取模” 的方式，逻辑相对简单，但冲突概率较高。

哈希值与索引计算

1 2	int hash = key.hashCode(); // 直接使用原始哈希值 int index = (hash & 0x7FFFFFFF) % tab.length; // 取绝对值后取模

步骤解析：

计算原始哈希值：直接使用 key.hashCode()，不做扰动处理。
取绝对值：hash & 0x7FFFFFFF 清除符号位（0x7FFFFFFF 二进制为 31 个 1，最高位为 0），确保哈希值为非负数。
取模计算索引：% tab.length 确保索引在数组范围内（0 <= index < tab.length）。

局限性：

无扰动处理：原始 hashCode 的高位信息未被利用，若低位重复则直接冲突。
容量非 2 的幂：Hashtable 初始容量为 11，扩容后为 2*oldCap + 1（如 11→23→47），非 2 的幂，取模运算效率低于 HashMap 的与运算。

HashMap 与 Hashtable 哈希机制对比

维度	HashMap	Hashtable
哈希值计算	二次哈希（高 16 位异或低 16 位）	直接使用 `hashCode`，无扰动
索引计算	`(n-1) & hash`（与运算，`n` 为 2 的幂）	`(hash & 0x7FFFFFFF) % n`（取模，`n` 非 2 的幂）
冲突概率	低（扰动增强随机性）	高（无扰动，低位易重复）
计算效率	高（位运算比取模快）	低（取模运算耗时）
容量要求	必须为 2 的幂（保证与运算等价于取模）	无要求（默认 11，扩容后为奇数）
null 键支持	支持（`null` 的哈希值为 0）	不支持（`key` 为 `null` 时 `hashCode` 抛异常）

哈希冲突的解决策略

无论哈希函数如何优化，哈希冲突都无法完全避免，HashMap 和 Hashtable 均采用链地址法解决冲突：

将冲突的键值对以链表形式存储在同一索引位置；
HashMap 在 JDK 8 中进一步优化：当链表长度 ≥ 8 且数组容量 ≥ 64 时，链表转为红黑树，将查询时间复杂度从 O(n) 降至 O(log n)