w wyl123ly 的博客
MD

数据结构-哈希表

51 KB 2026.10.11 原文件

数据结构-哈希表

一句话概括

哈希表(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

算法输出长度状态特点与用途
MD5128 位已破解,可构造碰撞仅可用于非安全的校验(如缓存键),禁止用于签名/口令
SHA-1160 位已破解(SHAttered 碰撞)逐步淘汰
SHA-256256 位安全数字签名、证书、完整性校验
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

请分别用①线性探测 ②二次探测()③双重哈希()画出最终表,并统计总冲突次数。

① 线性探测

键 探测过程最终位置冲突次数
2200 空00
4188 空80
5399 空90
4622 空20
3088 占 → 9 占 → 10 空102
1322 占 → 3 空31
111 空10
6711 占 → 2 占 → 3 占 → 4 空43

最终表(下标 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 取模)

键 探测过程最终位置冲突次数
2200 空00
4188 空80
5399 空90
4622 空20
3088 占 → 9 占 → (8+4)=12→1 空12
1322 占 → 3 空31
111 占 → 2 占 → (1+4)=5 空52
6711 占 → 2 占 → 5 占 → (1+9)=10 空103

最终表:

下标:  0   1   2   3   4   5   6   7   8   9   10
键:   22  30  46  13   -   1   -   -  41  53  67

总冲突次数 = 。注意:二次探测冲突次数反而更多(8 > 6),但元素分布更均匀——这说明冲突次数不是唯一指标,查找长度与聚集程度才是。此例中线性探测的聚集块更长,长尾查找代价更高。

③ 双重哈希()

先算步长:

键
3025
1361
116
6743
键 探测过程最终位置冲突次数
2200 空00
4188 空80
5399 空90
4622 空20
3088 占 → (8+5)=13→2 占 → (8+10)=18→7 空72
1322 占 → (2+1)=3 空31
111 空10
6711 占 → (1+3)=4 空41

最终表:

下标:  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_mapPython 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(墓碑 / 已删除标记):查找时跳过墓碑继续探测,插入时优先复用墓碑位置。

代价:墓碑会累积,导致装载因子虚高,即使真实元素很少也会让探测变长。处理办法有三种:

  1. rehash 时统一清理(最常用,本文实现)。
  2. 计数触发:维护 used / size 比值,墓碑过多时强制 rehash。
  3. 惰性删除 + 后向移位删除(Backward Shift Deletion):删除后把后续同链元素前移(Robin Hood Hashing 的做法),完全避免墓碑,但实现复杂。

墓碑相关的高频 bug

1. 删除直接置空 → 后续元素查不到(上面代码已演示)。

2. _size 与 _used 混用 → 装载因子算错,扩容时机错误。

3. 查找遇到墓碑就返回 default → 与第 1 条等价,都是截断了探测链。

4. 遍历时把墓碑当作有效元素 → 结果里出现已被删除的键。

五、哈希表与平衡树的选型对比

维度哈希表平衡树(红黑树 / AVL)
查找期望 ,最坏 最坏
插入 / 删除期望 ,最坏 最坏
有序遍历不支持(需全量排序 )中序即 升序
范围查询不支持天然支持
最值 / 前驱后继不支持
性能稳定性依赖哈希质量,可能被攻击稳定可预测
空间开销较低(有预留空位)每节点 2~3 指针 + 颜色位
实现难度简单复杂(旋转 / 染色)
典型实现Python dict、C# Dictionary、Java HashMapC# 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=10000否
k=10111否
k=10222否
k=10333否
k=10404是
k=10510是
…约 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() 结果直接当桶下标:Python hash() 可以是负数(如 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 章(二叉搜索树对比)