当前位置：首页 > news >正文

哈希表笔记（一）

news 来源：原创 2025/5/22 10:08:23

设计思路

核心功能和 API 设计 (Core Functionality & API Design):
- 基本操作: 必须提供核心的 put(key, value)（添加或更新键值对）、get(key)（根据键获取值）、remove(key)（根据键删除键值对）、containsKey(key)（检查键是否存在）、size()（获取元素数量）、isEmpty()（检查是否为空）、clear()（清空所有元素）等方法。
- 返回值: 仔细考虑每个操作的返回值。例如，put 是返回旧值还是 void？remove 是返回被删除的值还是一个布尔值表示成功与否？get 在键不存在时是返回 null、抛出异常，还是返回一个特定的哨兵值或使用 Optional 类型（如果语言支持）？
- 迭代: 如何遍历 Map 中的元素？提供迭代器（Iterators）来遍历键、值或键值对（Entries）是常见的做法。API 应清晰易用。
- 批量操作: 是否需要支持如 putAll 等批量操作？
键（Key）的处理:
- 哈希函数 (Hash Function):
  - 质量: 需要一个高质量的哈希函数，能够将键尽可能均匀地分布到哈希桶中，以减少冲突。
  - 一致性: 必须保证相等的键（根据 equals 方法判断）必须具有相同的哈希码（hashCode）。
  - 性能: 哈希函数本身的计算速度要快。
- 相等性判断 (Equality):
  - 如何判断两个键是否相等？通常依赖于键对象的 equals 方法（或等效的比较函数）。
  - 必须同时正确实现 hashCode 和 equals，并遵守它们之间的约定（相等对象必须有相同哈希码）。
- 不可变性 (Immutability): 强烈建议（或要求）用作键的对象是不可变的。如果一个键在插入 HashMap 后其状态发生改变，导致其 hashCode 或 equals 的结果变化，那么可能无法再正确地检索到对应的值。库文档应明确指出这一点。
- Null 键/值: 是否允许 null 作为键或值？需要明确定义并处理这种情况。Java 的 HashMap 允许一个 null 键和多个 null 值，但 Hashtable 不允许。
冲突解决策略 (Collision Resolution Strategy):
- 当不同的键哈希到同一个索引（桶）时，如何处理？
- 拉链法 (Separate Chaining): 每个桶维护一个数据结构（如链表、红黑树）来存储冲突的键值对。Java 8+ 的 HashMap 在链表长度超过一定阈值时会转换为红黑树，以优化最坏情况下的性能（从 O(n) 降到 O(log n)）。
- 开放地址法 (Open Addressing): 当发生冲突时，探测哈希表中的其他位置，直到找到一个空槽。常见的探测方法有线性探测、二次探测、双重哈希等。需要处理删除操作（标记删除而非直接移除，以避免破坏探测链）。
- 选择哪种策略会影响性能特征和实现复杂度。
性能考量 (Performance Considerations):
- 时间复杂度: 理想情况下，put, get, remove 操作的平均时间复杂度应为 O(1)。但由于冲突和可能的树化（对于拉链法），最坏情况可能是 O(n) 或 O(log n)。
- 空间复杂度: 需要存储键值对本身以及内部数据结构（如哈希表数组、链表节点、树节点）带来的开销。
- 负载因子 (Load Factor): 定义为 元素数量 / 哈希表容量。当负载因子超过某个阈值时，通常需要进行扩容（Resize）以维持 O(1) 的平均性能。默认负载因子通常在 0.75 左右，这是一个时间和空间成本的权衡。
- 初始容量 (Initial Capacity): 哈希表底层数组的初始大小。如果预知要存储大量元素，设置一个合适的初始容量可以减少扩容次数，提高性能。API 应允许用户指定初始容量和负载因子。
- 扩容机制 (Resizing): 当达到负载因子阈值时，需要创建一个更大的哈希表（通常是原容量的两倍），并将所有现有元素重新哈希（Rehash）到新表中。这是一个相对耗时的操作。
内存使用 (Memory Usage):
- 内部数据结构的选择（链表 vs. 树 vs. 开放地址）会影响内存占用。
- 负载因子较低意味着空间利用率低，但冲突少；负载因子高则相反。
- 需要考虑每个条目（Entry）的内存开销。
并发与线程安全 (Concurrency & Thread Safety):
- 标准 HashMap 实现通常不是线程安全的。如果多个线程同时修改 HashMap，可能会导致数据不一致甚至无限循环（如 JDK 7 及之前版本扩容时可能出现的问题）。
- 如果需要线程安全的版本，需要考虑：
  - 完全同步: 使用单一锁保护所有访问（如 Java 的 Hashtable 或 Collections.synchronizedMap），简单但并发性能差。
  - 分段锁 (Segmented Locking): 将哈希表分成多个段（Segment），每个段有自己的锁（如 Java 的早期 ConcurrentHashMap 实现）。
  - CAS 与无锁技术: 使用现代并发原语（如 Compare-and-Swap）实现更细粒度的并发控制，提供更高的吞吐量（如 Java 8+ 的 ConcurrentHashMap）。

Java HashMap 实现

JDK7 扩容

// newCapacity为新的容量
void resize(int newCapacity) {// 小数组，临时过度下Entry[] oldTable = table;// 扩容前的容量int oldCapacity = oldTable.length;// MAXIMUM_CAPACITY 为最大容量，2 的 30 次方 = 1<<30if (oldCapacity == MAXIMUM_CAPACITY) {// 容量调整为 Integer 的最大值 0x7fffffff（十六进制）=2 的 31 次方-1threshold = Integer.MAX_VALUE;return;}// 初始化一个新的数组（大容量）Entry[] newTable = new Entry[newCapacity];// 把小数组的元素转移到大数组中transfer(newTable, initHashSeedAsNeeded(newCapacity));// 引用新的大数组table = newTable;// 重新计算阈值threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

JDK8 哈希计算

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

h 是一个 int 类型（在 Java 中是 32 位），右移 16 位并进行异或（XOR）操作的核心原因是为了更好地将原始哈希码的高位信息混合到低位中，以减少哈希冲突，尤其是在哈希表容量较小的时候。

让我们详细解释一下 (h = key.hashCode()) ^ (h >>> 16) 这一步：

h = key.hashCode(): 首先，获取键 key 的原始 hashCode()。这是一个 32 位的 int 值。
h >>> 16:
- >>> 是 Java 中的无符号右移操作符。
- 它将 h 的二进制表示向右移动 16 位。
- 由于 int 是 32 位，右移 16 位相当于把原始哈希码的高 16 位移动到了低 16 位的位置。左边空出的位用 0 填充。
^ (XOR):
- ^ 是按位异或操作符。
- 它将原始的哈希码 h（包含原始的 32 位信息）与右移 16 位后的值（高 16 位移到了低 16 位，原来的低 16 位丢失，高 16 位补 0）进行异或运算。

为什么这么做？
HashMap 内部通常使用一个数组（称为桶或槽）来存储数据。为了确定一个键值对应该放在数组的哪个位置（哪个桶），HashMap 需要将键的哈希码转换为一个数组索引。这个转换通常是通过取模运算或者（当数组容量是 2 的幂时）位运算 hash & (capacity - 1) 来完成的。

关键在于 hash & (capacity - 1) 这个操作。当 capacity 是 2 的幂时，capacity - 1 的二进制表示是低位全为 1 的一串数字（例如，capacity=16 即 10000，capacity-1=15 即 01111）。这意味着，计算索引时，实际上只用到了最终哈希值的低位。

问题来了： 如果一个类的 hashCode() 实现虽然能产生不同的哈希码，但这些差异主要体现在高位，而低位变化不大，那么在使用 hash & (capacity - 1) 计算索引时，不同的键就很容易算得相同的索引，导致大量的哈希冲突，从而降低 HashMap 的性能（查询时间可能从 O(1) 退化到 O(n) 或 O(log n)）。

解决方案（即这行代码的作用）： 通过 h ^ (h >>> 16) 这个操作，将原始哈希码 h 的高 16 位的信息也**混合（扰动）**到了低 16 位中。这样，即使原始哈希码的差异主要在高位，经过这个混合操作后，这些差异也能体现在最终用于计算索引的低位上。这使得最终的哈希值分布更均匀，减少了冲突的可能性。

总结:

右移 16 位（>>> 16）是因为 int 是 32 位，这样可以将高 16 位移下来。进行异或（^）是为了将原始的高位信息和低位信息结合起来，产生一个低位随机性（分布性）更好的哈希值，专门用于后续通过 & (capacity - 1) 计算桶下标，从而有效减少哈希冲突，提高 HashMap 的整体性能。

代码中 (key == null) ? 0 : ... 部分则是处理了 key 为 null 的情况，规定 null 键的哈希值为 0。

为什么不尝试修改hash & (capacity - 1)而是添加低位扰动

它触及了 HashMap 设计中的一个关键权衡：性能与哈希码质量的鲁棒性。

不修改 hash & (capacity - 1) 而选择添加扰动函数（如 h ^ (h >>> 16)）的主要原因如下：

保持最高效的索引计算方式:
- 当哈希表的容量 capacity 设计为 2 的幂时，hash & (capacity - 1) 是计算桶（bucket）索引最快的方式。这利用了位运算 (&) 的高效性，它通常比取模运算 (%) 快得多。
- HashMap 的核心操作（put, get, remove）都需要计算索引，这个操作的性能至关重要。牺牲这种高效的索引计算方式会显著影响 HashMap 的整体性能。
无法控制外部 hashCode() 的质量:
- HashMap 作为一个通用库，它无法强制要求所有用作键的对象都实现一个完美的 hashCode() 方法，即一个能将哈希值均匀分布在所有 32 位上的方法。
- 很多时候，用户自定义的类或者甚至 JDK 中的某些类的 hashCode() 实现可能并不理想，产生的哈希码可能在高位区分度好，但在低位区分度差（或者反之，但低位差更影响 & 运算）。
- 如果 HashMap 不做任何处理，直接使用 key.hashCode() & (capacity - 1)，那么一旦遇到低位分布不佳的哈希码，就会导致大量的冲突，性能急剧下降。
扰动函数是对"坏" hashCode() 的一种"防御":
- 添加 h ^ (h >>> 16) 这样的扰动步骤，其目的是将原始哈希码的高位信息也混合到低位中。
- 这样做的好处是，即使原始 hashCode() 的低位区分度不高，但只要高位具有一定的区分度，通过扰动函数，这种区分度也能"传递"到最终用于索引计算的低位上。
- 这使得 HashMap 对各种不同质量的 hashCode() 实现更加鲁棒（robust），降低了因为糟糕的 hashCode() 实现而导致严重哈希冲突的风险。它是一种补偿机制。
职责分离:
- 可以认为 key.hashCode() 的职责是为对象生成一个（尽可能唯一的）整数表示。
- HashMap 内部 hash() 函数的职责是获取这个整数表示，并将其转换为一个适合在内部数组中定位的、分布尽可能均匀的值。
- 而 hash & (capacity - 1) 的职责是利用这个优化后的哈希值，以最高效的方式计算出最终的数组下标。
- 添加扰动函数是在不改变最高效索引计算的前提下，优化了传递给索引计算的值。

总结:

选择添加扰动函数而不是修改 hash & (capacity - 1)，是在性能和鲁棒性之间做出的明智权衡。

保留 hash & (capacity - 1) 是为了极致的索引计算性能。
添加扰动函数是为了增强对各种质量 hashCode() 实现的适应性，通过混合高位和低位信息，减少仅仅依赖低位可能带来的冲突风险，从而提高整体的性能稳定性。

这体现了库设计者在面对无法控制的外部因素（hashCode() 实现）时，通过内部优化来尽可能保证库自身性能和可靠性的策略。

取模运算 VS 取余运算 VS 与运算

取模运算（Modulo Operation）和取余运算（Remainder Operation）从严格意义上来讲，是两种不同的运算方式，它们在计算机中的实现也不同。

在 Java 中，通常使用 % 运算符来表示取余，用 Math.floorMod() 来表示取模。

当操作数都是正数的话，取模运算和取余运算的结果是一样的。
只有当操作数出现负数的情况，结果才会有所不同。
取模运算的商向负无穷靠近；取余运算的商向 0 靠近。这是导致它们两个在处理有负数情况下，结果不同的根本原因。
当数组的长度是 2 的 n 次方，或者 n 次幂，或者 n 的整数倍时，取模运算/取余运算可以用位运算来代替，效率更高，毕竟计算机本身只认二进制嘛。

hash & (capacity - 1)和hash % capacity 有区别吗

核心区别:

操作类型:
- %: 是**取模（Modulo）**运算，计算 hash 除以 capacity 后的余数。
- &: 是**按位与（Bitwise AND）**运算，对 hash 和 capacity - 1 的二进制表示进行逐位与操作。
对 capacity 的要求:
- %: 适用于任何正整数 capacity。无论 capacity 是多少，hash % capacity 都能正确地将 hash 映射到 [0, capacity - 1] 的范围内。
- &: 只有当 capacity 是 2 的幂（Power of 2）时，hash & (capacity - 1) 的结果才等价于 hash % capacity，并且能有效地将 hash 均匀映射到 [0, capacity - 1] 的范围。如果 capacity 不是 2 的幂，hash & (capacity - 1) 的结果虽然也在 [0, capacity - 1] 范围内（但不一定覆盖整个范围），但与取模结果不同，并且会导致哈希分布非常不均匀（某些桶永远不会被用到）。
性能:
- %: 取模运算（尤其是涉及除法）通常比位运算慢。
- &: 按位与运算是非常快的，是处理器可以直接执行的基本指令。

为什么 capacity 是 2 的幂时 & 操作有效？

当 capacity 是 2 的幂时（例如 16），它的二进制表示是 1 后面跟着若干个 0（例如 16 是 10000）。那么 capacity - 1 的二进制表示就是若干个 1（例如 15 是 01111）。

执行 hash & (capacity - 1) 操作时，这个 capacity - 1（形如 0...011...1）就像一个掩码（mask），它会保留 hash 值中对应 1 位置的那些低位比特，并将对应 0 位置的高位比特全部清零。保留下来的低位比特数正好是 log2(capacity)。这在数学上恰好等价于计算 hash 除以 capacity (2的幂) 的余数。

举例说明:

假设 hash = 123

场景 1: capacity = 16 (是 2 的幂, 2^4)

capacity - 1 = 15
二进制表示:
- hash = 123 -> 01111011
- capacity - 1 = 15 -> 00001111 (掩码，保留低 4 位)
取模运算:
- 123 % 16 = 11
按位与运算:
- 01111011 & 00001111 = 00001011 (二进制)
- 00001011 (二进制) = 11 (十进制)
结果: 两者结果相同（都是 11）。使用 & 更快。

场景 2: capacity = 10 (不是 2 的幂)

capacity - 1 = 9
二进制表示:
- hash = 123 -> 01111011
- capacity - 1 = 9 -> 00001001
取模运算:
- 123 % 10 = 3 (这是我们期望的、能利用所有 10 个桶的索引)
按位与运算:
- 01111011 & 00001001 = 00001001 (二进制)
- 00001001 (二进制) = 9 (十进制)
结果: 两者结果不同（3 vs 9）。
更严重的问题: 观察 capacity - 1 = 9 的二进制 1001。它只有第 0 位和第 3 位是 1。这意味着，无论 hash 值是多少，hash & 9 的结果中，第 1 位和第 2 位永远是 0。
- 可能的结果只有：0000(0), 0001(1), 1000(8), 1001(9)。
- 这意味着，如果数组大小是 10，使用 hash & 9 来计算索引，那么索引 2, 3, 4, 5, 6, 7 的桶永远不会被使用！这会导致哈希冲突急剧增加，性能严重下降。

总结:

特性	`hash % capacity`	`hash & (capacity - 1)`
操作	取模 (求余数)	按位与
`capacity`	任何正整数	必须是 2 的幂
性能	相对较慢	非常快
结果	范围 `[0, capacity-1]`，分布均匀	范围 `[0, capacity-1]`，仅当 capacity 是 2 的幂时分布均匀且等价于取模
HashMap 应用	理论可行，但因性能较差通常不直接用	实际采用，配合内部将 `capacity` 调整为 2 的幂的策略

因此，像 Java 的 HashMap 这样的实现选择使用 hash & (capacity - 1) 是为了获得极致的性能，但其前提是内部强制要求哈希表的容量 (capacity) 始终是 2 的幂。这也是为什么你在看 HashMap 源码时会发现，当你指定一个初始容量时，它内部会找到大于等于该值的最小的 2 的幂作为实际容量；并且在扩容时，总是将容量翻倍（乘以 2），以保持其为 2 的幂。之前讨论的 hash() 函数扰动（如 h ^ (h >>> 16)）也是为了配合这种基于低位掩码的索引计算方式，让高位的差异也能影响最终的低位索引。

设计思路

Java HashMap 实现

JDK7 扩容

JDK8 哈希计算

为什么不尝试修改hash & (capacity - 1)而是添加低位扰动

取模运算 VS 取余运算 VS 与运算

hash & (capacity - 1)和hash % capacity 有区别吗

相关文章：