数据结构-哈希表
一句话概括
哈希表(Hash Table)用哈希函数把键映射到数组下标,把「按值查找」从比较模型的 下界直接降到期望 ——代价是放弃有序性、并必须处理冲突与装载因子。
本文覆盖:哈希函数设计(除留余数 / 乘法 / MD5 / SHA)、冲突解决(链地址法、线性探测、二次探测、双重哈希,含手算例题)、装载因子与 rehash 均摊分析、墓碑标记、与平衡树的选型对比、Python
dict与 C#Dictionary的实现差异、一致性哈希(虚拟节点)、布隆过滤器与哈希攻击防御。读完你将能:手写一个支持扩容与删除的哈希表、解释「 平均」的前提条件、算出给定探测序列的成功/失败平均查找长度。
一、核心思想与 平均查找的前提
1.1 从「比较查找」到「地址计算」
有序数组二分查找与平衡树都属于比较模型:它们通过比较键的大小来缩小范围。在比较模型下,从 个元素中查找需要 次比较(决策树下界)。
哈希表跳出了比较模型:
它不比较键,而是直接计算出键应该在哪个桶(Bucket)。这就是它能达到 的根本原因——不是「比较得更快」,而是「根本不需要比较」。
哈希表由两部分组成:哈希函数 + 冲突解决策略。
1.2 「 平均」的四个前提
必须记住的四个前提
1. 哈希函数计算是 :对定长键(整数、定长字符串)成立。对超长字符串,首次计算哈希是 。
2. 哈希函数把键均匀分散:若大量键映射到同一位置,退化为链表,最坏 。
3. 装载因子 有常数上界:必须扩容。 时开放寻址法性能崩溃。
4. 键的哈希值在生命周期内不变:所以 Python 中可变对象(
list、dict、set)不可哈希,不能作字典键。结论: 是期望复杂度(对哈希函数随机性取期望),最坏是 。任何声称哈希表最坏 的说法都是错的。
二、哈希函数(Hash Function)
2.1 设计要求
| 要求 | 含义 | 违反后果 |
|---|---|---|
| 确定性 | 同一个键每次必须得到同一个值 | 存进去就找不回来 |
| 均匀性 | 输出在值域上尽量均匀分布 | 聚集,性能退化 |
| 高效性 | 计算代价是 | 常数过大,抵消优势 |
| 雪崩效应 | 输入微变,输出差异巨大 | 相近键聚集 |
| 抗碰撞性(密码学场景) | 难以找到两个不同输入同哈希 | 可被伪造/攻击 |
2.2 常见构造方法
① 除留余数法(Division Method)
最常用。关键是 的选取: 取素数效果最好。若 ,则 只取决于 的低 位,高位信息被完全丢弃——若键的低位有规律(如都是偶数、都以 00 结尾),会集体聚集到少数桶。
反面例子
键为
[100, 200, 300, 400, 500],取 :全部映射到下标 0,哈希表退化为链表。若取 (素数),映射为[3, 6, 9, 12, 15],完美分散。
② 乘法散列法(Multiplication Method)
优点: 可以是 2 的幂(取模变成位运算,极快),且分散质量对 不敏感。Knuth 推荐 取黄金比例。
def hash_division(k: int, m: int) -> int:
"""除留余数法:m 取素数时分布最均匀。"""
return k % m
def hash_multiplication(k: int, m: int, A: float = 0.6180339887498949) -> int:
"""乘法散列法:取小数部分再线性映射,m 可以是 2 的幂。"""
frac = (k * A) % 1.0 # 只保留小数部分
return int(m * frac)
def demo_division_vs_multiplication():
"""对比两种方法在「键全是 100 的倍数」这一恶意输入下的表现。"""
keys = [100 * i for i in range(1, 11)]
print("除留余数 m=100:", [hash_division(k, 100) for k in keys]) # 全为 0,极差
print("除留余数 m=97 :", [hash_division(k, 97) for k in keys]) # 分散
print("乘法散列 m=16 :", [hash_multiplication(k, 16) for k in keys])
demo_division_vs_multiplication()
③ 其他常用方法
- 折叠法(Folding):把长键切成等长片段相加,适合超长数字键。
- 平方取中法(Mid-Square):取 的中间几位,中间位受所有输入位影响,分布较好。
- 字符串哈希:把字符串视为进制数,用多项式滚动哈希:
工程上取 或 、(利用自然溢出)或大素数 ,实践中碰撞率极低。
def hash_string(s: str, base: int = 131, mod: int = 2**61 - 1) -> int:
"""多项式滚动哈希。2^61-1 是梅森素数,取模分布好且可延迟取模优化。
注意:这不是密码学哈希,构造碰撞是可行的,不可用于安全场景。
"""
h = 0
for ch in s:
h = (h * base + ord(ch)) % mod
return h
print(hash_string("hello"), hash_string("hellp")) # 相邻字符串差异应很大
④ 密码学哈希:MD5 与 SHA
| 算法 | 输出长度 | 状态 | 特点与用途 |
|---|---|---|---|
| MD5 | 128 位 | 已破解,可构造碰撞 | 仅可用于非安全的校验(如缓存键),禁止用于签名/口令 |
| SHA-1 | 160 位 | 已破解(SHAttered 碰撞) | 逐步淘汰 |
| SHA-256 | 256 位 | 安全 | 数字签名、证书、完整性校验 |
| SHA-3(Keccak) | 可变 | 安全 | 与 SHA-2 结构不同,作为备用标准 |
| bcrypt / scrypt / Argon2 | 可变 | 安全 | 口令专用,故意设计成慢且耗内存,抵抗暴力破解 |
哈希与加密是两件不同的事
哈希(Hash)是单向的:不可逆,用于完整性校验与索引。
加密(Encryption)是可逆的:用于保密。
把 MD5 当加密用、或把口令做一次 SHA-256 就存库,都是严重安全缺陷——后者会被彩虹表与 GPU 暴力破解秒破,必须用加盐 + 慢哈希(bcrypt/Argon2)。参见 后端-06-认证与授权。
三、冲突解决(Collision Resolution)
冲突不可避免(鸽巢原理):若键空间大于桶数量,必有两个键映射到同一位置。
3.1 链地址法(Separate Chaining)
每个桶挂一条链表(或红黑树),冲突的键都挂上去。这是最常用、最稳健的方案。
- 查找:先算 ,再在桶内链表中顺序查找。
- 平均查找长度(成功):
- 平均查找长度(失败):
- 删除:直接摘链即可,没有墓碑问题。
- 缺点:指针开销大、缓存不友好、需要额外内存分配。
3.2 开放寻址法(Open Addressing)
所有元素都放在表内数组里,冲突时按探测序列寻找下一个空槽。优点:无指针、缓存友好、内存紧凑。缺点:装载因子不能高(一般控制在 0.7 以下),删除需要墓碑。
① 线性探测(Linear Probing)
问题是一次聚集(Primary Clustering):连续被占的槽会形成「大块」,任何映射到块内的键都要走到块尾,越长的块吸引更多的键。
② 二次探测(Quadratic Probing)
常用 ,即 。缓解一次聚集,但会产生二次聚集(Secondary Clustering):映射到同一初始位置的键探测序列完全相同。
二次探测的陷阱
二次探测不保证能探测到表中每一个槽。例如 时, 只能覆盖约一半的位置,即使表未满也可能插入失败。补救办法:取 为素数且 ,此时可证明所有槽都能被探测到。
③ 双重哈希(Double Hashing)
探测步长由第二个哈希函数决定,不同键的探测序列几乎独立,几乎消除聚集,是最优的开放寻址方案,代价是多算一次哈希。
关键约束: 必须与 互素,否则探测会陷入死循环只能覆盖部分槽。常用做法:取 为素数,令
这样 ,恒不为 0,且与素数 互素。
3.3 手算例题:三种探测法对比
题目
哈希表长度 (下标 0~10),哈希函数 。
依次插入键序列:
22, 41, 53, 46, 30, 13, 1, 67请分别用①线性探测 ②二次探测()③双重哈希()画出最终表,并统计总冲突次数。
① 线性探测
| 键 | 探测过程 | 最终位置 | 冲突次数 | |
|---|---|---|---|---|
| 22 | 0 | 0 空 | 0 | 0 |
| 41 | 8 | 8 空 | 8 | 0 |
| 53 | 9 | 9 空 | 9 | 0 |
| 46 | 2 | 2 空 | 2 | 0 |
| 30 | 8 | 8 占 → 9 占 → 10 空 | 10 | 2 |
| 13 | 2 | 2 占 → 3 空 | 3 | 1 |
| 1 | 1 | 1 空 | 1 | 0 |
| 67 | 1 | 1 占 → 2 占 → 3 占 → 4 空 | 4 | 3 |
最终表(下标 0~10):
下标: 0 1 2 3 4 5 6 7 8 9 10
键: 22 1 46 13 67 - - - 41 53 30
总冲突次数 = 。可以看到键 22, 1, 46, 13, 67 已连成 0~4 的一次聚集块,后续任何映射到 0~4 的键都要走到 5。
② 二次探测(探测序列 ,对 11 取模)
| 键 | 探测过程 | 最终位置 | 冲突次数 | |
|---|---|---|---|---|
| 22 | 0 | 0 空 | 0 | 0 |
| 41 | 8 | 8 空 | 8 | 0 |
| 53 | 9 | 9 空 | 9 | 0 |
| 46 | 2 | 2 空 | 2 | 0 |
| 30 | 8 | 8 占 → 9 占 → (8+4)=12→1 空 | 1 | 2 |
| 13 | 2 | 2 占 → 3 空 | 3 | 1 |
| 1 | 1 | 1 占 → 2 占 → (1+4)=5 空 | 5 | 2 |
| 67 | 1 | 1 占 → 2 占 → 5 占 → (1+9)=10 空 | 10 | 3 |
最终表:
下标: 0 1 2 3 4 5 6 7 8 9 10
键: 22 30 46 13 - 1 - - 41 53 67
总冲突次数 = 。注意:二次探测冲突次数反而更多(8 > 6),但元素分布更均匀——这说明冲突次数不是唯一指标,查找长度与聚集程度才是。此例中线性探测的聚集块更长,长尾查找代价更高。
③ 双重哈希()
先算步长:
| 键 | ||
|---|---|---|
| 30 | 2 | 5 |
| 13 | 6 | 1 |
| 1 | 1 | 6 |
| 67 | 4 | 3 |
| 键 | 探测过程 | 最终位置 | 冲突次数 | |
|---|---|---|---|---|
| 22 | 0 | 0 空 | 0 | 0 |
| 41 | 8 | 8 空 | 8 | 0 |
| 53 | 9 | 9 空 | 9 | 0 |
| 46 | 2 | 2 空 | 2 | 0 |
| 30 | 8 | 8 占 → (8+5)=13→2 占 → (8+10)=18→7 空 | 7 | 2 |
| 13 | 2 | 2 占 → (2+1)=3 空 | 3 | 1 |
| 1 | 1 | 1 空 | 1 | 0 |
| 67 | 1 | 1 占 → (1+3)=4 空 | 4 | 1 |
最终表:
下标: 0 1 2 3 4 5 6 7 8 9 10
键: 22 1 46 13 67 - - 30 41 53 -
总冲突次数 = ,是三种方案中最少的,且分布最分散(无长连续块)。这正是双重哈希在实践中表现最好的原因。
3.4 三种冲突解决策略对比
| 维度 | 链地址法 | 线性探测 | 二次探测 | 双重哈希 |
|---|---|---|---|---|
| 空间开销 | 高(每元素一个指针) | 低(无指针) | 低 | 低 |
| 缓存友好度 | 差 | 最好 | 好 | 好 |
| 聚集问题 | 无 | 一次聚集,严重 | 二次聚集,中等 | 几乎无 |
| 装载因子上限 | 可 > 1 | < 0.7 | < 0.5 | < 0.7 |
| 删除 | 直接摘链 | 需墓碑 | 需墓碑 | 需墓碑 |
| 查找命中 ASL | 略优 | |||
| 查找未命中 ASL | 略优 | |||
| 典型实现 | Java HashMap、std::unordered_map | Python dict(CPython 3.6+ 仍用伪探测序列) | 部分嵌入式场景 | 高性能内存表 |
class ChainingHashTable:
"""链地址法哈希表:支持任意键、自动扩容。
设计要点:
- 桶数组长度取素数,降低规律性键的聚集
- 装载因子超过阈值就扩容(rehash),保证桶内链表长度是常数
"""
_PRIMES = [11, 23, 47, 97, 197, 397, 797, 1597, 3203, 6421, 12853]
def __init__(self):
self._size = 0
self._buckets = [[] for _ in range(self._PRIMES[0])]
self._cap_index = 0
self._max_load = 0.75
@property
def capacity(self):
return len(self._buckets)
@property
def load_factor(self):
return self._size / self.capacity
def _hash(self, key):
"""先取 Python 内建哈希(对 str/bytes 已加盐抗攻击),再压缩到桶下标。"""
return hash(key) % self.capacity
def put(self, key, value):
idx = self._hash(key)
bucket = self._buckets[idx]
for i, (k, _) in enumerate(bucket): # 已存在则更新
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
self._size += 1
if self.load_factor > self._max_load:
self._resize()
def get(self, key, default=None):
for k, v in self._buckets[self._hash(key)]:
if k == key:
return v
return default
def delete(self, key):
bucket = self._buckets[self._hash(key)]
for i, (k, _) in enumerate(bucket):
if k == key:
bucket.pop(i) # 链地址法删除无墓碑问题
self._size -= 1
return True
return False
def _resize(self):
"""扩容并重新插入所有元素。单次 O(n),均摊 O(1)。"""
self._cap_index = min(self._cap_index + 1, len(self._PRIMES) - 1)
old = self._buckets
self._buckets = [[] for _ in range(self._PRIMES[self._cap_index])]
self._size = 0
for bucket in old:
for k, v in bucket:
self.put(k, v) # 重新计算下标
def __len__(self):
return self._size
def stats(self):
"""查看桶长度分布:最长链长度是哈希质量的关键指标。"""
lens = [len(b) for b in self._buckets]
return {"容量": self.capacity, "元素数": self._size,
"装载因子": round(self.load_factor, 3),
"最长链": max(lens), "非空桶": sum(1 for x in lens if x)}
if __name__ == "__main__":
ht = ChainingHashTable()
for i in range(1000):
ht.put(f"user:{i}", i * 10)
print(ht.stats())
print(ht.get("user:500")) # 5000
ht.delete("user:500")
print(ht.get("user:500")) # None
print("删除后元素数:", len(ht))
四、装载因子与扩容
装载因子(Load Factor):
其中 是已存元素数, 是桶数组长度。
| 冲突策略 | 建议 上限 | 超过后的表现 |
|---|---|---|
| 链地址法 | 0.75 ~ 1.0 | 链表变长,查找趋近 |
| 线性探测 | 0.5 ~ 0.7 | 一次聚集急剧恶化,接近 1 时性能崩溃 |
| 二次探测 / 双重哈希 | 0.5 | 探测序列变长,且可能探测不到空槽 |
4.1 rehash 的均摊代价分析
扩容时要做两件事:申请更大的数组 + 把所有元素重新计算位置插入(rehash)。
- 单次扩容代价:
- 若每次插入都扩容(),总代价 ,均摊 ——退化为线性。
- 若倍增扩容(),第 次扩容搬运 个元素,等比数列求和仍是 ,均摊到 次插入:
这与动态数组的扩容分析完全一致(见 数据结构-线性结构):只有按倍数增长才能得到均摊 。
class OpenAddressingHashTable:
"""开放寻址法哈希表:线性探测 + 墓碑标记 + 倍增扩容。
三个关键设计:
1. 容量取素数,保证探测循环能覆盖全表
2. 删除用墓碑(tombstone)而不是清空,否则会截断探测链
3. 装载因子(含墓碑)超过 0.5 就 rehash,顺便清理所有墓碑
"""
_EMPTY = object() # 从未使用过
_TOMB = object() # 曾经有值、后被删除
_PRIMES = [11, 23, 47, 97, 197, 397, 797, 1597, 3203, 6421, 12853, 25717]
def __init__(self):
self._cap_index = 0
self._keys = [self._EMPTY] * self._PRIMES[0]
self._vals = [None] * self._PRIMES[0]
self._size = 0 # 真实元素个数
self._used = 0 # 元素 + 墓碑 占用的槽数
@property
def capacity(self):
return len(self._keys)
def _probe(self, key):
"""线性探测生成器:yield 每个候选槽下标。"""
m = self.capacity
i = hash(key) % m
while True:
yield i
i = (i + 1) % m # 线性探测:+1
def put(self, key, value):
# 装载因子(含墓碑)过高会影响性能,先扩容
if (self._used + 1) / self.capacity > 0.5:
self._resize()
first_tomb = None
for i in self._probe(key):
if self._keys[i] is self._EMPTY:
# 找到空槽:若之前遇到墓碑,优先复用墓碑位置
target = first_tomb if first_tomb is not None else i
self._keys[target] = key
self._vals[target] = value
self._size += 1
if first_tomb is None:
self._used += 1 # 用的是全新槽
return
if self._keys[i] is self._TOMB:
if first_tomb is None:
first_tomb = i # 记住第一个墓碑,但继续找是否已存在该键
continue
if self._keys[i] == key: # 键已存在 -> 更新
self._vals[i] = value
return
def get(self, key, default=None):
for i in self._probe(key):
if self._keys[i] is self._EMPTY:
return default # 遇到空槽说明键不存在(墓碑不阻断)
if self._keys[i] is not self._TOMB and self._keys[i] == key:
return self._vals[i]
return default
def delete(self, key):
"""关键:删除必须留下墓碑,否则后续同哈希的键会提前遇到空槽而查找失败。"""
for i in self._probe(key):
if self._keys[i] is self._EMPTY:
return False
if self._keys[i] is not self._TOMB and self._keys[i] == key:
self._keys[i] = self._TOMB # 立墓碑
self._vals[i] = None
self._size -= 1
# 注意:_used 不减,墓碑仍占槽
return True
return False
def _resize(self):
"""扩容并重建:顺带清掉所有墓碑,这是清理墓碑的最佳时机。"""
self._cap_index = min(self._cap_index + 1, len(self._PRIMES) - 1)
new_cap = self._PRIMES[self._cap_index]
old_keys, old_vals = self._keys, self._vals
self._keys = [self._EMPTY] * new_cap
self._vals = [None] * new_cap
self._size = 0
self._used = 0
for k, v in zip(old_keys, old_vals):
if k is not self._EMPTY and k is not self._TOMB:
self.put(k, v)
def __len__(self):
return self._size
def debug_view(self):
"""把表内容渲染成可读字符串(墓碑显示为 X)。"""
return " ".join(
"·" if k is self._EMPTY else ("X" if k is self._TOMB else str(k))
for k in self._keys
)
def _verify_tombstone_bug():
"""演示「不用墓碑」会造成什么 bug。"""
# 手写一个「删除时直接清空」的错误实现,对比正确实现
class BrokenTable(OpenAddressingHashTable):
def delete(self, key):
for i in self._probe(key):
if self._keys[i] is self._EMPTY:
return False
if self._keys[i] is not self._TOMB and self._keys[i] == key:
self._keys[i] = self._EMPTY # 错误:直接清空,截断探测链
self._vals[i] = None
self._size -= 1
self._used -= 1
return True
return False
broken = BrokenTable()
# 11 个槽的表中,23 与 34 都映射到 1(23%11=1, 34%11=1)
broken.put(23, "a") # 放在 1
broken.put(34, "b") # 冲突,放到 2
broken.delete(23) # 清空槽 1
print("错误实现查 34 ->", broken.get(34)) # None!探测到槽 1 是空就返回了
good = OpenAddressingHashTable()
good.put(23, "a")
good.put(34, "b")
good.delete(23) # 立墓碑
print("正确实现查 34 ->", good.get(34)) # b
if __name__ == "__main__":
t = OpenAddressingHashTable()
for k in [22, 41, 53, 46, 30, 13, 1, 67]:
t.put(k, k * 100)
print("插入 8 个键(容量 23):", t.debug_view())
print("查 30 ->", t.get(30))
t.delete(41)
print("删除 41 后:", t.debug_view())
print("查 53(受墓碑影响仍可查到)->", t.get(53))
_verify_tombstone_bug()
4.2 墓碑标记问题(Tombstone)
开放寻址法不能把删除的槽直接置空,原因是:
查找的终止条件是「遇到空槽」,说明探测链上任何被清空的槽都会让后面的元素变得不可达。
所以删除时要标记为 TOMBSTONE(墓碑 / 已删除标记):查找时跳过墓碑继续探测,插入时优先复用墓碑位置。
代价:墓碑会累积,导致装载因子虚高,即使真实元素很少也会让探测变长。处理办法有三种:
- rehash 时统一清理(最常用,本文实现)。
- 计数触发:维护
used / size比值,墓碑过多时强制 rehash。 - 惰性删除 + 后向移位删除(Backward Shift Deletion):删除后把后续同链元素前移(Robin Hood Hashing 的做法),完全避免墓碑,但实现复杂。
墓碑相关的高频 bug
1. 删除直接置空 → 后续元素查不到(上面代码已演示)。
2.
_size与_used混用 → 装载因子算错,扩容时机错误。3. 查找遇到墓碑就返回
default→ 与第 1 条等价,都是截断了探测链。4. 遍历时把墓碑当作有效元素 → 结果里出现已被删除的键。
五、哈希表与平衡树的选型对比
| 维度 | 哈希表 | 平衡树(红黑树 / AVL) |
|---|---|---|
| 查找 | 期望 ,最坏 | 最坏 |
| 插入 / 删除 | 期望 ,最坏 | 最坏 |
| 有序遍历 | 不支持(需全量排序 ) | 中序即 升序 |
| 范围查询 | 不支持 | 天然支持 |
| 最值 / 前驱后继 | 不支持 | |
| 性能稳定性 | 依赖哈希质量,可能被攻击 | 稳定可预测 |
| 空间开销 | 较低(有预留空位) | 每节点 2~3 指针 + 颜色位 |
| 实现难度 | 简单 | 复杂(旋转 / 染色) |
| 典型实现 | Python dict、C# Dictionary、Java HashMap | C# SortedDictionary、Java TreeMap、std::map |
| 适用场景 | 纯键值查找、去重、计数 | 需要顺序、范围、排名 |
选型口诀
只要键值查找 → 哈希表;只要顺序、范围、最值 → 平衡树;两者都要 → 哈希表 + 有序索引(或直接用 B+ 树)。
数据库选 B+ 树而不是哈希索引,正是因为 SQL 的
ORDER BY、BETWEEN、>这些操作需要有序性——哈希索引只能做等值查询。这也是 MySQL 的 MEMORY 引擎支持哈希索引、而 InnoDB 默认用 B+ 树的原因。
六、Python dict 与 C# Dictionary 的实现差异
| 维度 | CPython dict | .NET Dictionary<K,V> |
|---|---|---|
| 冲突策略 | 开放寻址 + 伪随机探测序列(perturb 扰动) | 链地址法(entries 数组 + buckets 下标数组) |
| 键值存储布局 | 3.6+ 紧凑布局:indices 数组 + 连续 entries 数组 | entries 数组存 {hashCode, next, key, value},buckets 存头下标 |
| 删除处理 | 用 DKIX_DUMMY 墓碑 | 摘链(无墓碑),复用空槽 |
| 扩容倍数 | GROWTH_RATE 使 used 超过 2/3 时扩到 used * 3(约 3 倍,保证 2/3 装载因子) | 扩容到下一个素数(约 2 倍,装载因子 0.72 时触发) |
| 哈希值 | hash() 结果,str/bytes 默认加盐(PEP 456) | GetHashCode(),默认无随机化(可用 RandomizedStringEqualityComparer 开启) |
| 遍历顺序 | 插入顺序(语言规范保证,3.7+) | 不保证(实现相关) |
| 最坏情况防御 | 哈希随机化 | 哈希冲突过多时树化为红黑树(.NET Core 3.0+) |
CPython 紧凑 dict 的设计精妙之处:
- 传统实现:哈希表槽位直接存
(hash, key, value)三元组,稀疏时浪费大量内存,且遍历要跳过空槽。 - 紧凑实现:
indices数组(1/2/4/8 字节整数)存索引,entries数组按插入顺序连续存储实际数据。 - 收益:① 内存减少约 20%~25%;② 遍历
entries就是插入顺序,无需跳过空槽;③ 对 8 元素以下的小 dict 有专门优化。
怎么用实验验证「dict 保序」
下面的三行代码就能验证:插入顺序
b, a, c会被原样保留,而不是按哈希值排序。这是语言规范保证的行为(Python 3.7+),可以放心依赖。
d = {}
d["b"] = 1
d["a"] = 2
d["c"] = 3
print(list(d)) # ['b', 'a', 'c'] —— 插入顺序,不是哈希顺序
assert list(d) == ["b", "a", "c"]
七、无序与有序
哈希表的本质是用有序性换速度:
- 它只回答「键在不在、值是多少」,不能回答「最小的键是什么」「所有键在 [a, b] 之间有哪些」「第 k 小的键是谁」。
- 需要有序性时,方案有三:① 换用平衡树 / 跳表;② 排序后再处理( 一次性成本);③ 哈希表 + 堆/有序索引 组合,如「LFU 缓存」= 哈希表 + 频率桶链表。
| 需求 | 推荐结构 | 复杂度 |
|---|---|---|
| 等值查找、去重、计数 | 哈希表 / 哈希集 | 期望 |
| 有序遍历、前驱后继 | 平衡树 / 跳表 | |
| 取最值(动态) | 堆 | 插入 ,取最值 |
| 范围查询(磁盘) | B+ 树 | 次 I/O |
| 排名(第 k 小) | 平衡树 + 子树规模 |
八、一致性哈希(Consistent Hashing)
8.1 普通取模哈希在扩缩容时的灾难
缓存集群常用 server = hash(key) % N 决定键落在哪台机器。当 从 4 变成 5 时:
| 键 | % 4 | % 5 | 是否迁移 |
|---|---|---|---|
| k=100 | 0 | 0 | 否 |
| k=101 | 1 | 1 | 否 |
| k=102 | 2 | 2 | 否 |
| k=103 | 3 | 3 | 否 |
| k=104 | 0 | 4 | 是 |
| k=105 | 1 | 0 | 是 |
| … | 约 80% 的键都要迁移 |
数学结论: 时,约 的键需要重新映射。对 4 台机器就是 80% 缓存失效——缓存击穿(Cache Avalanche),数据库瞬间被打爆。
8.2 一致性哈希的环形结构
核心思想:把哈希值空间组织成一个环(如 ),服务器和键都映射到环上;键归属顺时针方向遇到的第一个服务器。
- 增加一台服务器:只有该服务器逆时针到前一台服务器之间的键需要迁移,平均只影响 的数据。
- 删除一台服务器:只有它负责的那段键转移给后继服务器。
- 迁移比例从 降到 。
8.3 虚拟节点(Virtual Node)
问题:若只有少量物理节点,它们在环上分布可能极不均匀,导致数据倾斜(一台机器扛 60% 的流量)。
解决:为每台物理机创建 个虚拟节点(如 hash("node1#0") 到 hash("node1#149")),共同映射到环上。虚拟节点越多,分布越均匀。
- 定性地说:虚拟节点数 越大,单机负载越集中到均值附近; 从 1 增到 10 的收益最明显,再继续增大收益递减(可运行下文代码实测极差/均值比值)。
- 物理机扩容时,它的 个虚拟节点会从多个物理机上分摊数据,实现负载均衡的迁移。
- 这就是 Redis Cluster 的哈希槽(Hash Slot) 思想来源:Redis 预分 16384 个槽,把槽分配给节点,本质上是「固定虚拟节点数」的一致性哈希简化版。
import bisect
import hashlib
class ConsistentHash:
"""一致性哈希:环形哈希空间 + 虚拟节点。
用 32 位哈希空间构造环,排序后的哈希值列表上用二分查找定位后继节点。
"""
def __init__(self, nodes=None, vnodes=150):
self.vnodes = vnodes
self._ring = [] # 有序的哈希值列表
self._owner = {} # 哈希值 -> 物理节点名
def _hash(self, key: str) -> int:
"""用 MD5 取前 8 字节生成 64 位整数。
注意:这里只把 MD5 当作「分布均匀的哈希」用,不涉及安全性。
"""
digest = hashlib.md5(key.encode("utf-8")).digest()
return int.from_bytes(digest[:8], "big")
def add_node(self, node: str):
"""加入物理节点:同时注册它的所有虚拟节点。"""
for i in range(self.vnodes):
h = self._hash(f"{node}#vn{i}")
self._ring.append(h)
self._owner[h] = node
self._ring.sort()
def remove_node(self, node: str):
"""移除物理节点:清理它的所有虚拟节点。"""
for i in range(self.vnodes):
h = self._hash(f"{node}#vn{i}")
if h in self._owner:
del self._owner[h]
self._ring.remove(h)
def get_node(self, key: str) -> str:
"""返回键所属的物理节点:环上顺时针第一个节点。"""
if not self._ring:
raise RuntimeError("没有可用节点")
h = self._hash(key)
idx = bisect.bisect_left(self._ring, h) # 找第一个 >= h 的位置
if idx == len(self._ring): # 越过末尾则回到环起点
idx = 0
return self._owner[self._ring[idx]]
def distribution(self, keys):
"""统计每个节点分到多少键,用来评估均衡度。"""
from collections import Counter
return Counter(self.get_node(k) for k in keys)
if __name__ == "__main__":
keys = [f"user:{i}" for i in range(10000)]
# ① 3 个节点,150 个虚拟节点
ch = ConsistentHash(vnodes=150)
for n in ["cache-A", "cache-B", "cache-C"]:
ch.add_node(n)
dist3 = ch.distribution(keys)
print("3 节点分布:", dict(dist3))
# ② 扩容到 4 个节点,统计有多少键发生了迁移
before = {k: ch.get_node(k) for k in keys}
ch.add_node("cache-D")
after = {k: ch.get_node(k) for k in keys}
moved = sum(1 for k in keys if before[k] != after[k])
print(f"一致性哈希扩容后迁移比例: {moved / len(keys):.2%}(理想值约 25%)")
# ③ 对比:普通取模哈希从 3 台扩到 4 台,迁移比例约为 3/4
mod_moved = sum(1 for k in keys if hash(k) % 3 != hash(k) % 4)
print(f"取模哈希扩容后迁移比例: {mod_moved / len(keys):.2%}(理想值约 75%)")
# ④ 观察虚拟节点数对单机负载(均衡度)的影响
# 结论:vnode 越多,单机负载的标准差越小,但收益递减
for v in [1, 10, 150]:
c = ConsistentHash(vnodes=v)
for n in ["cache-A", "cache-B", "cache-C"]:
c.add_node(n)
counts = list(c.distribution(keys).values())
spread = (max(counts) - min(counts)) / (sum(counts) / len(counts))
print(f"虚拟节点数={v:4d} 各节点键数={sorted(counts)} 极差/均值={spread:.1%}")
九、布隆过滤器(Bloom Filter)
9.1 原理
布隆过滤器用一个位数组(Bit Array) 加 个独立哈希函数,回答「某元素可能存在或一定不存在」。
- 添加元素:用 个哈希函数算出 个位置,全部置 1。
- 查询元素:算出 个位置,只要有一个是 0 → 一定不存在;全是 1 → 可能存在(可能是别的元素把这些位碰巧置了 1)。
- 不支持删除(删一个元素会影响其他元素的位)。变体:计数布隆过滤器(Counting Bloom Filter) 用计数器代替位,可支持删除但内存翻数倍。
单向确定性
布隆过滤器没有假阴性(False Negative),只有假阳性(False Positive)。这个不对称性正是它的价值:可以用它来拦截「一定不存在」的请求,从而保护后面的昂贵查询。
9.2 误判率公式
设位数组长度 、元素个数 、哈希函数个数 ,则误判率(假阳性率)为:
最优哈希函数个数(给定 )由求导得到:
此时误判率取最小值:
常用换算:若希望误判率 ,则需 比特/元素, 个哈希函数。也就是说每个元素约 10 bit 就能把误判率压到 1%,这就是布隆过滤器「省内存」的量化依据。
import hashlib
import math
class BloomFilter:
"""布隆过滤器:m 位数组 + k 个哈希函数。
用「双重哈希技巧」从一个哈希值派生出 k 个位置:
h_i(x) = h1(x) + i * h2(x),避免真正实现 k 个哈希函数。
"""
def __init__(self, expected_items: int, false_positive_rate: float = 0.01):
n, p = expected_items, false_positive_rate
# 由公式反解 m 与 k
self.m = max(1, math.ceil(-n * math.log(p) / (math.log(2) ** 2)))
self.k = max(1, round(self.m / n * math.log(2)))
self._bits = bytearray((self.m + 7) // 8) # 位数组用字节数组模拟
self._n = 0
def _hashes(self, item: str):
"""派生 k 个位下标。"""
data = hashlib.sha256(item.encode("utf-8")).digest()
h1 = int.from_bytes(data[:8], "big")
h2 = int.from_bytes(data[8:16], "big") | 1 # 保证 h2 为奇数,增加分散性
for i in range(self.k):
yield (h1 + i * h2) % self.m
def _set_bit(self, idx):
self._bits[idx >> 3] |= 1 << (idx & 7)
def _get_bit(self, idx):
return (self._bits[idx >> 3] >> (idx & 7)) & 1
def add(self, item: str):
for idx in self._hashes(item):
self._set_bit(idx)
self._n += 1
def __contains__(self, item: str) -> bool:
"""返回 True 表示「可能存在」,False 表示「一定不存在」。"""
return all(self._get_bit(idx) for idx in self._hashes(item))
def false_positive_rate(self) -> float:
"""按当前实际元素数估算误判率。"""
return (1 - math.exp(-self.k * self._n / self.m)) ** self.k
def info(self):
return {"位数组长度 m": self.m, "哈希函数个数 k": self.k,
"已插入 n": self._n, "内存字节": len(self._bits),
"理论误判率": f"{self.false_positive_rate():.4%}"}
if __name__ == "__main__":
bf = BloomFilter(expected_items=10000, false_positive_rate=0.01)
print(bf.info())
for i in range(10000):
bf.add(f"item:{i}")
# ① 已插入的元素必须全部命中(无假阴性)
assert all(f"item:{i}" in bf for i in range(10000))
print("已插入元素全部命中,确认无假阴性")
# ② 统计未插入元素的误判率
fp = sum(1 for i in range(10000, 30000) if f"item:{i}" in bf)
print(f"实测误判率:{fp / 20000:.4%}(公式估算 {bf.false_positive_rate():.4%})")
9.3 使用场景
| 场景 | 用法 | 收益 |
|---|---|---|
| 缓存穿透防护 | 请求先过布隆过滤器,不存在直接返回 | 挡住恶意不存在的 key,保护数据库 |
| 爬虫 URL 去重 | 判断 URL 是否已抓取 | 亿级 URL 只占几百 MB |
| 大数据集去重 | 先过滤「一定不在」的项,再走昂贵查询 | 减少 90%+ 无效 I/O |
| 推荐系统已读过滤 | 判断用户是否已看过 | 低延迟、低内存 |
| LSM-Tree(RocksDB/LevelDB) | 每个 SSTable 配一个布隆过滤器 | 避免无效磁盘查找 |
| 垃圾邮件/恶意域名判断 | 黑名单前置过滤 | 布隆过滤器体积远小于完整名单 |
布隆过滤器的三个限制
1. 不能删除:删除会误伤共享位;需要删除就用计数布隆过滤器或 Cuckoo Filter。
2. 不能枚举:无法遍历其中的元素,因为位里没有元素信息。
3. 误判率随插入量上升:必须按预期容量创建;实际插入远超预期时误判率会急剧上升(公式里 变大, 变大)。
十、哈希攻击与防御
10.1 哈希碰撞拒绝服务(HashDoS / Hash-Flooding Attack)
攻击原理:如果哈希函数是确定性且公开的,攻击者可以离线构造大量哈希值相同的键,一次性提交给服务器。每次查找都退化为遍历长链表, 个恶意键能让一次请求从 变成 ,总代价 ——单个请求即可打满 CPU。
历史事件:2011 年 Chaos Computer Club 在 32C3 上演示了针对 PHP、Java、Python、Ruby、ASP.NET 等多个语言的 HashDoS,多数语言的默认哈希都未加随机化。
10.2 防御手段
| 手段 | 原理 | 采用者 |
|---|---|---|
| 哈希随机化 / 加盐 | 每个进程启动时生成随机种子参与哈希计算,攻击者无法离线预测 | Python(PEP 456,str/bytes 默认加盐)、Perl、Ruby |
| 冲突树化 | 单桶元素超过阈值(Java 8:8 个)时把链表转成红黑树,最坏降到 | Java 8+ HashMap、.NET Core 3.0+ Dictionary |
| 限制请求大小 | 限制单次提交的键数量与总长度 | Web 框架层 |
| 用密码学哈希 | 计算代价高但抗碰撞 | 少数对性能不敏感的场景 |
| 改用更抗碰撞的结构 | 如 SipHash(默认带密钥) | Rust HashMap 默认用 SipHash-1-3 |
import os
import sys
def demo_hash_randomization():
"""演示 Python 的字符串哈希随机化。
同一个字符串在不同 Python 进程中哈希值不同(因为 PYTHONHASHSEED 随机)。
整数与小整数的哈希是自身,不随机化(所以不可用于安全场景)。
"""
print("本进程 hash('hello') =", hash("hello"))
print("本进程 hash(12345) =", hash(12345)) # 整数就是自身
print("PYTHONHASHSEED =", os.environ.get("PYTHONHASHSEED", "未设置(默认随机)"))
print("提示:多次运行本脚本,字符串哈希会变化,整数哈希永远不变。")
if __name__ == "__main__":
demo_hash_randomization()
自定义对象的哈希必须与相等性一致
Python 的契约是:
a == b必须推出hash(a) == hash(b)(反之不要求)。违反后果:同一个键存进去再也取不出来,或字典中出现「重复」键。下面两种写法都是错的。
class Bad:
"""错误一:定义了 __eq__ 却没定义 __hash__。"""
def __init__(self, v):
self.v = v
def __eq__(self, other):
return isinstance(other, Bad) and self.v == other.v
# Python 检测到 __eq__ 被重写而 __hash__ 未定义时,会把 __hash__ 设为 None,
# 于是该类的实例变成不可哈希对象,不能作 dict 键。
class AlsoBad:
"""错误二:用 id(self) 做哈希,但相等性基于内容。"""
def __init__(self, v):
self.v = v
def __eq__(self, other):
return isinstance(other, AlsoBad) and self.v == other.v
def __hash__(self):
return id(self) # 严重错误:两个「相等」的对象哈希不同
# 下面的正确写法:让哈希与相等性基于同一组不可变字段
from dataclasses import dataclass
@dataclass(frozen=True) # frozen=True 让 Python 自动生成一致的 __eq__ 与 __hash__
class Good:
v: int
a, b = Good(1), Good(1)
assert a == b and hash(a) == hash(b) # 契约成立
print({a: "ok"}[b]) # ok —— 用 b 能取出 a 存的值
print("不可哈希的对象:", end="")
try:
hash(Bad(1))
except TypeError as e:
print("TypeError:", e)
十一、注意事项与常见坑
哈希表高频踩坑清单
1. 可变对象作键:存入后修改字段,哈希值改变,键再也找不到。Python 中
list/dict/set直接不可哈希,是保护机制。2.
__eq__与__hash__不一致:见上一节的AlsoBad,是最隐蔽的 bug。3. 开放寻址删除不用墓碑:截断探测链,后续元素不可达。
4. 墓碑不清理:装载因子虚高,性能逐渐退化。要在 rehash 时清理。
5. 扩容倍数用加法:
m += 1使均摊代价退化为 ,必须倍数扩容。6. 表长取 且用除法散列:只用低位,规律性键全部聚集;应取素数或改用乘法散列。
7. 双重哈希的 与 不互素:探测陷入部分槽的循环,表未满却插不进去。
8.
hash()结果直接当桶下标:Pythonhash()可以是负数(如hash(-1) == -2),负数取模在 C/Java 中会得到负下标 → 数组越界。必须先取绝对值或做无符号转换。9. 依赖 C#
Dictionary的遍历顺序:其顺序是实现细节,不同运行时不保证一致;需要保序请用OrderedDictionary或自己维护顺序。10. 用浮点数作键:
0.1 + 0.2 != 0.3,看似相同的键其实不等,永远取不到值。11. 布隆过滤器按最小值创建:容量不足时误判率飙升,必须按预期峰值容量规划。
12. 在高并发下用非线程安全的哈希表:Python
dict因 GIL 单操作原子,但「检查再更新」不是原子的;C#Dictionary完全不保证并发安全,需ConcurrentDictionary。13. 在哈希表中存超大键:每次哈希都要遍历整个键,首次
hash()是 ;用长字符串作键时性能会明显下降(Python 会缓存已算过的哈希)。
十二、练习题
练习 1:手算平均查找长度(ASL)
哈希表长 ,,依次插入
[18, 26, 35, 9, 68, 74, 51, 40]。① 用线性探测画出最终表;② 计算查找成功与查找失败的平均查找长度 与 。
提示: 要分别对每个下标统计「探测到空槽所需次数」,再取平均。
练习 2:实现 LRU 缓存
用哈希表 + 双向链表实现容量为 的 LRU(Least Recently Used)缓存,要求
get与put都是 。哈希表负责 定位节点,双向链表负责 移动节点到表头 / 删除表尾。这是「哈希表提供定位、链表提供顺序」的经典组合,也是 数据结构-线性结构 中双向链表的实战。
练习 3:设计一个支持 随机取值的集合
实现
insert(val)、remove(val)、getRandom()三个操作,getRandom()必须等概率返回一个已有元素,三者都要 期望时间。提示:哈希表(值 → 数组下标)+ 动态数组。删除时把末尾元素搬到被删位置,再更新哈希表——这个技巧叫「swap-remove」。
练习 4:实现一致性哈希并验证均衡性
基于本文的
ConsistentHash,完成:① 加入虚拟节点数为 1、10、100、500 的对比实验,用标准差 / 均值(变异系数)量化均衡度;
② 模拟「删除一个节点」,统计受影响的键比例,验证是否接近 ;
③ 思考:虚拟节点数是不是越多越好?(提示:哈希计算与二分查找的开销、环数组内存)
练习 5:布隆过滤器参数设计
某系统预计存储 1 亿个 URL 用于去重。
① 若要求误判率 ,计算所需的位数组大小(MB)与哈希函数个数;
② 若把误判率放宽到 ,内存能省多少?
③ 用 Python 实现并用 100 万规模的数据实测误判率,与公式值对比。
十三、常见问题 FAQ
Q1:哈希表真的比二分查找快吗?
在纯等值查找场景下是的,而且差距很大:哈希是 期望(一次哈希 + 一次访问),二分是 次内存访问。但要注意三点:① 哈希函数的计算常数不小(字符串哈希要遍历整个字符串),键很长时优势缩小;② 二分查找的访存模式是顺序的、可预测的,缓存友好度远高于哈希的随机访存,在 较小(几百以内)时二分可能实际更快;③ 哈希不支持范围查询。理论复杂度相同或更优,不代表实测更快——一定要按真实数据规模做基准测试。
Q2:装载因子为什么不能设成 1 或更高?
对链地址法, 意味着平均每桶一个元素,查找仍需遍历链表节点(指针跳转),实测性能明显差于 。对开放寻址法, 时的查找长度按 增长: 时约 2 次探测, 时约 10 次, 时约 100 次——性能断崖式下跌。所以开放寻址法一般把阈值设在 0.5~0.7。
Q3:Python 的
dict为什么不用链地址法?CPython 选择了开放寻址 + 扰动(perturb)探测,其探测下标递推为 、。这种伪随机探测序列避免了线性探测的聚集,同时保留了开放寻址「无指针、缓存友好、内存紧凑」的优点。配合 3.6 引入的紧凑布局,
dict在内存与速度上都优于典型的链地址实现。具体细节以 CPython 源码Objects/dictobject.c为准。
Q4:一致性哈希的虚拟节点为什么能改善均衡?
哈希函数把「节点名 + 序号」映射到环上,等价于把一台物理机复制成 个独立小节点随机撒在环上。每个虚拟节点负责的环区间长度服从均匀分布, 个区间的总和(即该物理机的总负载)随着 增大而向均值集中(大数定律)。所以虚拟节点数越多,单机负载越接近平均,标准差约按 下降。工程上 取 100~200 已能获得较好均衡,再增大收益递减而内存与查找开销线性增长。
相关笔记
- 数据结构-线性结构:链地址法的桶是链表、开放寻址法与动态数组扩容的分析完全同源
- 数据结构-树与堆:冲突树化的红黑树、B+ 树索引与哈希索引的选型对比
- 算法-复杂度分析:均摊分析(rehash)、期望复杂度与实际最坏复杂度的区别
- 数据库原理:哈希索引 vs B+ 树索引、InnoDB 自适应哈希索引
- Python-02-内置数据结构:
dict/set的工程用法与可变性陷阱 - 后端-06-认证与授权:口令存储为什么必须用 bcrypt/Argon2 而非 MD5/SHA
- 后端-09-后端安全与性能:缓存穿透与布隆过滤器、限流与攻击防护
- 计算机网络:分布式缓存路由与一致性哈希的落地场景
- 00-索引:全库导航
参考来源
- Python 官方文档《内置类型 · Mapping Types — dict》,
dict语义与保序说明:https://docs.python.org/3/library/stdtypes.html#mapping-types-dict - CPython 源码
Objects/dictobject.c,探测序列、紧凑布局与GROWTH_RATE:https://github.com/python/cpython/blob/main/Objects/dictobject.c - Python 官方文档《数据模型 · object.__hash__》,
__eq__与__hash__的一致性契约:https://docs.python.org/3/reference/datamodel.html#object.__hash__ - Python 官方文档《内置函数 hash()》,含 PEP 456 哈希随机化说明:https://docs.python.org/3/library/functions.html#hash
- Microsoft Learn《Dictionary<TKey,TValue> 类》,.NET 实现与容量增长说明:https://learn.microsoft.com/zh-cn/dotnet/api/system.collections.generic.dictionary-2
- OI Wiki《哈希表》,冲突解决与复杂度推导:https://oi-wiki.org/ds/hash/
- Tom White《Consistent Hashing》(经典讲解,含虚拟节点与均衡性分析):https://www.tom-e-white.com/2007/11/consistent-hashing.html
- Wikipedia《Bloom filter》,误判率公式与最优哈希个数推导:https://en.wikipedia.org/wiki/Bloom_filter
- Cornell CS312《Hashing》讲义,开放寻址三种探测法的 ASL 公式:https://www.cs.cornell.edu/courses/cs312/2008sp/lectures/lec21.html
- Redis 官方文档《Cluster specification》,哈希槽(Hash Slot)与一致性哈希的关系:https://redis.io/docs/reference/cluster-spec/
- CLRS《算法导论》第 11 章(散列表,含全域哈希与开放寻址分析)、第 12 章(二叉搜索树对比)