哈希算法

一、什么是哈希算法

哈希算法（Hash Function） 是一种把任意长度的输入（键）映射为固定长度输出（哈希值）的函数。在数据结构中，它主要用于哈希表（Hash Table）：先计算键的哈希值，再通过取模、掩码等方式把哈希值映射到数组下标，从而让查找、插入和删除的平均时间复杂度接近 O(1)。

一个直观过程是：

key ──哈希函数──> hash(key) ──映射──> 数组下标 index

例如：

hash("apple") = 3287
index = 3287 % 16 = 7

于是 "apple" 对应的数据就放在哈希表下标为 7 的桶中。

🟡以下是关于上面提到的概念的一些解释。

---

1. key 是什么

key 是哈希表用来定位数据的“键”，也就是查找时使用的标识。

例如：

key = "apple"

在哈希表里，真正存储的通常不是单独的 "apple"，而是一个“键值对”：

("apple", 价格=5)
("apple", 库存=100)

其中 "apple" 是 key，后面的内容是 value。

哈希表的目标是：给定一个 key，快速找到它对应的 value。

---

2. 哈希函数是什么

哈希函数是一个确定性的函数：

hash(key) -> 一个整数

例如假设：

hash("apple") = 3287

这里的 3287 叫哈希值或哈希码。

• 同一个 key，每次算出来的哈希值必须一样；
• 如果不同 key 算出来的哈希值一样，就叫做哈希冲突；
• 哈希值通常是一个比较大的整数，不能直接拿来当数组下标。

例子里的 hash("apple") = 3287 只是示意，真实哈希函数算出来不一定是 3287。

---

3. hash(key) 和“数组下标”不是一回事

哈希表底层通常有一个数组，比如长度为 16：

下标:   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
桶:    []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []

数组下标只能是 0 到 15。

但哈希值 3287 远远超出这个范围，不能直接写：

array[3287] = ...

因为数组没有下标 3287。

所以需要把大整数哈希值“压缩”到数组下标范围内。

---

4. index = 3287 % 16 = 7 是什么意思

% 是取模运算，表示求余数。

3287 ÷ 16 = 205 余 7

所以：

3287 % 16 = 7

这样就把哈希值 3287 映射成了数组下标 7。

这里的 16 是哈希表当前数组容量，也就是桶数组长度。

取模的目的只有一个：

把任意大的哈希值压缩到 [0, capacity - 1] 范围内

容量是 16 时，下标范围就是：

0, 1, 2, ..., 15

所以：

index = hash(key) % capacity

例子中：

index = 3287 % 16 = 7

表示 "apple" 这个 key 应该放到下标为 7 的桶里。

---

5. “桶”是什么

“桶”可以理解为数组中的每一个槽位。

下标 0：桶 0
下标 1：桶 1
...
下标 7：桶 7

每个桶里放的不是单纯的 value，而通常放的是“键值对条目”，例如：

桶 7：
  ("apple", 价格=5)

那为什么桶里还要存 key？

因为不同 key 可能映射到同一个下标。查找时不能只看下标，还要比较 key 是否真的相同。

例如：

hash("apple")  % 16 = 7
hash("banana") % 16 = 7

两个 key 都落到下标 7，这叫哈希冲突。此时桶 7 可能长这样：

桶 7：
  ("apple",  价格=5)
  ("banana", 价格=3)

所以“桶”不一定是只能放一个元素，它可能是一个链表、红黑树，或者开放寻址法中的一个槽位。

---

6. “把数据放到桶中”完整是什么意思

完整过程不是：

"apple" -> 桶 7

而是：

1. 取 key = "apple"
2. 计算 hash("apple") = 3287
3. 计算 index = 3287 % 16 = 7
4. 把条目 ("apple", value) 放进桶数组的下标 7 中

如果桶 7 是空的，就直接放进去。

如果桶 7 已经有其他条目，就按冲突处理策略处理，例如挂到链表后面。

---

7. 查找时也不是只算下标就结束

查找 "apple" 时：

1. 计算 hash("apple") = 3287
2. 计算 index = 3287 % 16 = 7
3. 到桶 7 中查找
4. 比较桶里的 key 是否等于 "apple"
5. 找到后返回对应 value

如果桶 7 中有多个条目，就要逐个比较 key。

这也是为什么哈希表平均是 O(1)，但冲突严重时可能退化。

---

那接下来自然会遇到几个问题：

1. 不同 key 落到同一个桶怎么办？
2. 桶快满了怎么办？
3. 哈希函数应该怎么设计？
4. 哈希表操作到底为什么平均 O(1)，什么时候退化？
5. 哈希表里的哈希和密码学哈希有什么区别？

对着这五个问题我们来展开接下来的内容

---

问题一：不同 key 落到同一个桶怎么办？

1.1 这件事叫什么

不同 key 经过哈希和取模后落到同一个桶，叫🟡哈希冲突。

例如：

hash("apple")  % 16 = 7
hash("banana") % 16 = 7

两个 key 都指向桶 7，但它们不是同一个 key，不能互相覆盖。

冲突不可避免：key 的可能取值远多于桶的数量，把大量 key 映射到少量桶，必然有多个 key 共享一个桶。这叫鸽巢原理。

所以问题不是“怎么消灭冲突”，而是“冲突后怎么存、怎么找”。

1.2 办法一：链地址法

思路：每个桶不直接放一个元素，而是挂一个容器，冲突的元素都放进这个容器。最常见的是链表。

桶 7: ("apple", 5) -> ("banana", 3) -> null

插入 "banana" 时：

1. 算下标 7
2. 桶 7 已有 "apple"
3. 把 ("banana", 3) 挂到链表后面

查找 "banana" 时：

1. 算下标 7
2. 遍历桶 7 的链表
3. 逐个比较 key
4. 找到 "banana"，返回 value

关键点：下标只决定去哪个桶找，桶内还要比较 key 才能确定是不是目标元素。

链地址法的优缺点：

优点	缺点
实现简单	链表节点有额外内存开销
删除方便	冲突多时链表变长，查找退化
桶数组可以装超过桶数的元素	缓存局部性差

Java HashMap 用链地址法。当链表长度超过阈值且桶数组足够大时，链表转红黑树，最坏查找从 O(n) 降到 O(log n)。

1.3 办法二：开放寻址法

思路：不挂链表，所有元素都放在桶数组里。冲突时按某种规则找下一个空桶。

线性探测

规则：下标被占，就看下一个，再下一个。

插入 "apple"：index=7，桶 7 空，放桶 7
插入 "banana"：index=7，桶 7 被占，看 8；8 空，放桶 8
插入 "cherry"：index=7，桶 7 被占，看 8；8 被占，看 9；9 空，放桶 9

查找时按同样规则探测：

查找 "banana"：
index=7，桶 7 的 key 不是 banana；
看 8，是 banana，找到。

线性探测的问题叫聚集：连续被占的槽位越来越长，后续冲突更容易连成一片。

二次探测

不再每次加 1，而是按平方序列跳：

index, index+1², index+2², index+3², ...

即 7, 8, 11, 16, ...，对容量取模后继续找。缓解连续聚集，但可能探测不到所有槽位。

双重哈希

用第二个哈希函数决定步长：

step = hash2(key)
index = (hash1(key) + i * step) % capacity

不同 key 步长不同，分布更均匀，但计算量更大。

开放寻址法的删除问题

不能直接置空。因为查找依赖探测链：

桶 7: apple
桶 8: banana
桶 9: cherry

删除 "banana" 后如果把桶 8 置空，再查找 "cherry" 时：

index=7，不是 cherry；
看 8，空，查找误以为不存在而停止。

所以要用墓碑标记：删除位置标记为“已删除”，查找时继续探测，插入时可复用。

1.4 两种办法怎么选

维度	链地址法	开放寻址法
额外内存	需要链表节点	不需要额外节点
缓存局部性	差	好
删除	直接删	需要墓碑
装载率上限	可以超过 1	必须小于 1
冲突严重时	链表变长	探测链变长

---

问题二：桶快满了怎么办？

2.1 怎么衡量“快满了”

用负载因子：

负载因子 = 元素个数 / 桶数组长度

例如 16 个桶放了 12 个元素：

负载因子 = 12 / 16 = 0.75

负载因子越高，冲突概率越大，查找越慢。开放寻址法尤其敏感，因为所有元素都在数组里，满了就探测不动了。

2.2 超过阈值就扩容

哈希表通常设一个阈值，超过就扩容。

以 Java HashMap 为例：

默认负载因子 = 0.75
容量 16 时阈值 = 16 * 0.75 = 12

放入第 13 个元素时触发扩容，桶数组从 16 扩到 32。

2.3 扩容不是简单复制

下标依赖容量：

旧：index = hash % 16
新：index = hash % 32

同一个哈希值在容量变化后，下标可能变。所以扩容时要对每个元素重新计算下标，这个过程叫 rehash。

扩容前：
桶 7: ("apple", 5)

扩容到 32 后：
hash("apple") = 3287
3287 % 32 = 23
桶 23: ("apple", 5)

2.4 容量为什么常取 2 的幂

取模 % 相对慢。容量是 2 的幂时，可以用位运算替代：

hash % 16 等价于 hash & 15

因为 16 是 10000，15 是 01111，与运算保留低 4 位，结果正好是 0 到 15。

Java HashMap 就要求容量是 2 的幂：

index = (n - 1) & hash

但位运算只保留低位，如果哈希值低位分布不好，冲突会多。所以 Java 加了扰动函数，把高位混到低位：

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

2.5 扩容的代价

扩容要遍历所有元素重新计算下标，代价 O(n)。

但扩容不是每次都发生。容量翻倍后，能再装很多元素才触发下一次扩容。把扩容代价摊还到每次插入上，平均仍是 O(1)。这叫摊还分析。

2.6 负载因子怎么选

负载因子	效果
太低	冲突少，但内存浪费，扩容频繁
太高	内存省，但冲突多，查找慢
0.75 左右	时间和空间的常见折中

Java HashMap 默认 0.75，就是这个折中。

---

问题三：哈希函数应该怎么设计？

3.1 三个基本要求

确定性

同一个 key 每次必须得到相同哈希值。

hash("apple") 今天 = 3287
hash("apple") 明天也必须 = 3287

否则今天存进去，明天就找不到了。

均匀性

不同 key 应尽量均匀落到各个桶，避免大量 key 挤在一起。

如果 1000 个 key 有 900 个落到桶 7，哈希表就退化成链表了。

高效性

哈希计算本身要快。哈希表靠 O(1) 取胜，如果哈希函数比查找还慢，就失去意义。

3.2 常见哈希表哈希函数

函数	特点
MurmurHash	分布好、速度快，通用哈希表常用
xxHash	非常快，适合性能敏感场景
CityHash / FarmHash	Google 出品，面向字符串
Java String.hashCode	s[0]*31^(n-1) + s[1]*31^(n-2) + ...

Java 用 31 的原因：

• 31 是奇素数，分布较好；
• JVM 可以把乘 31 优化成移位减法：31 * i = (i << 5) - i。

3.3 设计时要注意的坑

坑一：低位分布差

如果容量是 2 的幂，下标只看哈希值的低位。若哈希函数低位分布差，冲突就多。

解决：扰动函数，把高位混到低位。

h ^ (h >>> 16)

坑二：相似 key 产生相似哈希

比如：

"aab" 和 "aba"

如果哈希函数只是简单相加，可能得到相同哈希值。好的哈希函数要让每个字符的位置都影响结果。

坑三：哈希函数太慢

SHA-256 分布很好，但对哈希表来说太慢。哈希表不需要抗攻击，只需要分布均匀和快。

3.4 总结

所以哈希表哈希函数的设计目标是：

确定性 + 均匀 + 快

不要求不可逆，不要求抗碰撞攻击。冲突有冲突处理机制兜底。

---

问题四：哈希表操作到底为什么平均 O(1)，什么时候退化？

4.1 平均 O(1) 的推导

设：

n = 元素个数
m = 桶数
负载因子 α = n / m

如果哈希函数均匀，每个桶平均有 α 个元素。

查找时：

1. 算哈希和下标：O(1)
2. 在桶内找目标：平均 O(α)

如果负载因子控制在常数，比如 0.75，那么：

平均查找 = O(1 + α) = O(1)

插入和删除同理，主要开销也在桶内操作。

这就是平均 O(1) 的来源：不是每一步都 O(1)，而是桶内平均元素数是常数。

4.2 三个操作的复杂度

操作	平均	最坏
查找	O(1)	O(n)
插入	O(1) 摊还	O(n)
删除	O(1)	O(n)

插入的摊还 O(1) 是因为扩容偶尔发生，代价 O(n)，但摊到每次插入上平均是 O(1)。

4.3 什么时候退化

情况一：所有 key 冲突到同一个桶

hash(key1) % 16 = 7
hash(key2) % 16 = 7
...
hash(keyn) % 16 = 7

链地址法下桶 7 变成一条长链表，查找 O(n)。

开放寻址法下探测链极长，也退化。

情况二：哈希函数分布差

如果哈希函数把大量 key 映射到少数桶，即使 key 本身不同，也会造成聚集。

情况三：负载因子过高

桶快满了还不扩容，冲突概率大增，桶内元素变多，查找变慢。

情况四：恶意构造 key

攻击者知道哈希函数，故意构造大量冲突的 key，让哈希表退化成链表。这叫哈希碰撞攻击。

Java 8 之后用红黑树缓解：链表长度超过 8 且容量 ≥ 64 时转红黑树，最坏从 O(n) 降到 O(log n)。

4.4 怎么避免退化

手段	作用
好的哈希函数	均匀分布，减少冲突
扰动函数	改善低位分布
控制负载因子	避免桶过满
及时扩容	降低冲突概率
链表转红黑树	冲突严重时兜底
随机化哈希种子	防哈希碰撞攻击

4.5 准确说法

哈希表平均 O(1)，最坏 O(n)。
平均 O(1) 依赖：哈希函数均匀 + 负载因子受控 + 冲突处理有效。

不能说“哈希表就是 O(1)”，因为它有退化条件。

---

问题五：哈希表里的哈希和密码学哈希有什么区别？

5.1 名字一样，目标不同

两者都叫哈希函数，都是把任意输入映射为固定长度输出，但设计目标完全不同。

维度	哈希表哈希	密码学哈希
代表	MurmurHash、xxHash、Java hashCode	SHA-256、SHA-3、BLAKE3
主要目标	分布均匀、计算快	安全、抗攻击
输出长度	常为 32/64 位	常为 256 位等
是否要求单向	不要求	要求不可逆
是否要求抗碰撞	不要求，冲突可处理	要求抗碰撞
是否要求雪崩效应	不强制	要求
典型用途	HashMap、布隆过滤器	数字签名、证书、密码存储

5.2 哈希表哈希：只要均匀和快

哈希表哈希不要求不可逆。就算你从哈希值反推出 key，对哈希表也没影响，因为哈希表本来就要存 key 来比较。

也不要求抗碰撞。冲突了有链地址法、开放寻址法兜底。

它最关心的是：

同一个 key 每次哈希值相同；
不同 key 尽量分散；
计算尽量快。

5.3 密码学哈希：安全性质是硬要求

密码学哈希要求：

单向性

给定哈希值，无法在可行时间内反推出原文。

抗碰撞性

很难找到两个不同输入得到相同哈希值。

雪崩效应

输入改一个比特，输出应面目全非。

抗长度扩展攻击等

这些性质用于数字签名、证书、密码存储等安全场景。

5.4 为什么哈希表不用 SHA-256

三个原因：

太慢

SHA-256 计算量远大于 MurmurHash。哈希表靠 O(1) 取胜，哈希函数太慢会拖垮性能。

没必要

哈希表能处理冲突，不需要抗碰撞。攻击者构造冲突的问题可以用随机化种子或红黑树缓解，不需要动用密码学哈希。

输出太长

SHA-256 输出 256 位，哈希表只需要几十位就能映射到桶。多出来的位数对哈希表没用。

5.5 一句话区分

哈希表哈希：为“分布”服务，冲突可处理。
密码学哈希：为“安全”服务，冲突不可接受。