数学重学 - 19 哈希数学

这是 数学重学路线图 阶段三的子页面

本页与 密码学数学 相关联，建议搭配阅读。

哈希数学：从散列到安全

直觉比喻：哈希函数就像一台”绞肉机”——任意大小的肉（输入）进去，出来固定大小的肉馅（哈希值）。你无法从肉馅还原出那头牛长什么样。

哈希在安全（密码存储、完整性校验）、大数据（去重、基数统计）、后端（HashMap、分布式缓存）中无处不在。搞懂它的数学，才能正确使用它。

一、哈希函数的数学性质

1.1 确定性

相同输入 → 永远得到相同输出

hash("hello") 调用一亿次，结果都一样

这是哈希能用于校验的基础

1.2 均匀分布

理想哈希函数的输出在整个值域上均匀分布

如果哈希值是0-99，那么对大量随机输入，每个值出现的概率应该接近1%

为什么重要：不均匀→哈希表某些桶特别拥挤→性能退化

好的哈希函数输出分布：
桶0: ████████ (12%)
桶1: ███████  (11%)
桶2: ████████ (12%)
桶3: ███████  (10%)
桶4: █████████(13%)

差的哈希函数输出分布：
桶0: ██████████████████ (35%)
桶1: ███ (5%)
桶2: ██ (3%)
桶3: █ (2%)
桶4: ████████████████████████ (55%)

1.3 雪崩效应

输入改变1个bit → 输出约50%的bit翻转

直觉比喻：蝴蝶效应。改一个字母，哈希值面目全非。

SHA-256("hello") = 2cf24d...
SHA-256("hallo") = d3751d...  ← 只改了一个字母，完全不同

为什么重要：没有雪崩效应→相似输入产生相似哈希→容易被攻击者利用

1.4 抗碰撞性

找到两个不同输入x和y使得hash(x)=hash(y)，在计算上应该不可行

强抗碰撞：找任意碰撞都难

弱抗碰撞（第二原像抗性）：给定x，找y使hash(y)=hash(x)很难

这两个性质的难度不同——生日攻击就利用了这个差距

1.5 单向性（原像抗性）

给定哈希值h，找到任意x使得hash(x)=h，在计算上不可行

这就是”绞肉机”比喻——不可逆

二、生日悖论

2.1 问题引入

直觉感受：一个房间里至少要多少人，才有超过50%的概率两人同天生日？

大多数人猜：183人（365的一半）

正确答案：23人！ 远比直觉少得多

2.2 数学推导

反向思考：计算所有人生日都不同的概率，再用1减去它

n个人都不同天生日的概率：

P(不碰撞) = 365/365 × 364/365 × 363/365 × ... × (365-n+1)/365

     = 365! / [365^n × (365-n)!]

P(至少一对碰撞) = 1 - P(不碰撞)

代入n=23：

P = 1 - (365×364×363×...×343) / 365^23
≈ 1 - 0.4927
≈ 0.5073
> 50%!

2.3 为什么碰撞比直觉快

关键洞察：不是”某个特定人”和别人碰撞，而是”任意两人”之间碰撞

23人中的”配对数” = C(23,2) = 253对

253次独立的”碰撞机会”，每次概率1/365，累积起来就超过50%了

近似公式：当n远小于总天数N时

P(碰撞) ≈ 1 - e^(-n²/(2N))

令P=0.5: n ≈ √(2N × ln2) ≈ 1.177 × √N

N=365: n ≈ 1.177 × √365 ≈ 22.5 → 取23

2.4 生日悖论的规律

| 总天数N | 50%碰撞所需人数 |
| 365 | 23 |
| 1000 | 38 |
| 10000 | 119 |
| 2^128 | 2^64 |
| 2^256 | 2^128 |

规律：约 √N 就够了，这就是”平方根律”

三、生日攻击

3.1 从悖论到攻击

哈希函数输出n位 → 值域大小 N = 2^n

找碰撞不需要尝试2^n次，只需约 2^(n/2) 次

这就是生日攻击的数学基础

3.2 各哈希算法的碰撞安全性

算法       输出位数   暴力碰撞     生日攻击
MD5        128位     2^128        2^64        ← 已被实际攻破！
SHA-1      160位     2^160        2^80        ← 2017年Google攻破
SHA-256    256位     2^256        2^128       ← 目前安全
SHA-512    512位     2^512        2^256       ← 非常安全

MD5的2^64次操作，现代GPU集群可以在合理时间内完成

SHA-256的2^128次操作，全人类的算力加起来也不够

3.3 安全启示

不要用MD5做安全用途：数字签名、证书、完整性校验都不安全

MD5做文件校验（非安全场景，如下载校验）还勉强能用

密码哈希不是普通哈希——后面会讲bcrypt/Argon2

四、哈希表数学

4.1 基本结构

哈希表 = 数组 + 哈希函数

index = hash(key) % array_size

理想情况：O(1)查找，但碰撞会让性能退化

4.2 负载因子

负载因子 α = 已存元素数 / 桶数(数组长度)

α = 0.5 → 半满
α = 0.75 → 3/4满 (Java HashMap默认扩容阈值)
α = 1.0 → 满了
α > 1.0 → 链地址法下可以超过1

4.3 链地址法（Separate Chaining）

每个桶是一个链表，碰撞了就追加到链表

期望查找长度 = 1 + α/2（成功查找）

α=0.5 → 期望 1.25 次比较
α=0.75 → 期望 1.375 次比较
α=1.0 → 期望 1.5 次比较
α=2.0 → 期望 2.0 次比较

即使α>1也能工作，只是性能线性退化

4.4 开放寻址法（Open Addressing）

碰撞了就往后找空位（线性探测、二次探测等）

期望查找长度 ≈ 1/(1-α)（成功查找的简化估计）

α=0.5 → 期望 2 次探测
α=0.75 → 期望 4 次探测
α=0.9 → 期望 10 次探测
α=0.95 → 期望 20 次探测

α不能>=1（桶满了就没法存了）

所以开放寻址法必须在α较低时扩容

4.5 Java HashMap 为什么 α=0.75 扩容

链地址法下，α=0.75是时间与空间的平衡点

α太小：浪费内存（大量空桶）

α太大：链表太长，查找变慢

0.75是经验值，此时期望查找约1.375次，仍接近O(1)

扩容策略：容量翻倍，所有元素rehash到新数组

五、一致性哈希

5.1 问题：普通取模的灾难

分布式缓存3台机器：server = hash(key) % 3

加一台变4台：server = hash(key) % 4

key=7: hash%3=1, hash%4=3  ← 迁移
key=8: hash%3=2, hash%4=0  ← 迁移
key=9: hash%3=0, hash%4=1  ← 迁移

几乎所有key都要迁移！如果有1亿条缓存数据...

5.2 哈希环

直觉比喻：把哈希值空间想象成一个钟表盘（0到2^32-1首尾相连成环）

每台服务器在环上有一个位置（hash(服务器IP)）

每个key顺时针找到的第一台服务器就是它的归属

哈希环示意（0在顶部，顺时针）：

    0
   /|\
  / | \
S3 /  |  \ S1
/   |   \
/    |    \
/     |     \
------+------
    |
    S2

key1 在S1和S2之间 → 归S2
key2 在S2和S3之间 → 归S3

5.3 加减节点的优势

加一台S4：只有S4逆时针到前一个节点之间的key需要迁移

理论上只影响 1/N 的数据（N=节点数）

从”几乎全部迁移”变成”只迁移一小部分”

5.4 虚拟节点

问题：3台机器在环上只有3个点，数据分布可能很不均匀

解决：每台机器虚拟出多个节点（如每台150个虚拟节点）

物理节点S1 → 虚拟节点 S1#0, S1#1, S1#2, ..., S1#149
物理节点S2 → 虚拟节点 S2#0, S2#1, S2#2, ..., S2#149
物理节点S3 → 虚拟节点 S3#0, S3#1, S3#2, ..., S3#149

环上450个点，分布更均匀

虚拟节点越多，数据分布越均匀，但路由表越大

一般150-200个虚拟节点/物理节点是常用值

六、布隆过滤器

6.1 问题引入

场景：爬虫已经爬了10亿个URL，新来一个URL要判断”爬过没有”

用HashSet？10亿条URL大约要几十GB内存

布隆过滤器：只需要约1.2GB，代价是有小概率误判

6.2 原理

一个m位的bit数组（初始全0）+ k个独立哈希函数

插入：对元素计算k个哈希值，将对应的k个位设为1

查询：对元素计算k个哈希值，如果k个位都是1→”可能存在”，有一个是0→”一定不存在”

m=16位, k=3个哈希函数

插入 "hello":
h1("hello")=2, h2("hello")=5, h3("hello")=11

bit数组: 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0
          ^       ^               ^

查询 "world":
h1("world")=1, h2("world")=5, h3("world")=9

位1=0 → 一定不存在！（即使位5碰巧是1）

查询 "foo":
h1("foo")=2, h2("foo")=5, h3("foo")=11

位2=1, 位5=1, 位11=1 → 可能存在（误判！foo没插入过）

6.3 数学公式

误判率公式：

误判率 ≈ (1 - e^(-kn/m))^k

n = 已插入元素数
m = bit数组大小
k = 哈希函数个数

最优k值（使误判率最小）：

k_optimal = (m/n) × ln2 ≈ 0.693 × (m/n)

给定目标误判率p，所需bit数：

m = -n × ln(p) / (ln2)²

例：n=1亿, p=1% → m ≈ 9.58亿bit ≈ 114MB
例：n=1亿, p=0.1% → m ≈ 14.4亿bit ≈ 172MB

6.4 核心特性

**可能误判”存在”**（false positive）：某元素没插入但查询说存在

**绝不误判”不存在”**（no false negative）：说不存在就一定不存在

不能删除元素：把某个位设为0会影响其他元素（Counting Bloom Filter可以解决）

空间极省：1%误判率约需9.6 bit/元素

七、HyperLogLog

7.1 问题引入

场景：统计网站的UV（独立访客数），日活可能上亿

精确去重：HashSet存所有用户ID，内存爆炸

HyperLogLog：只用约12KB内存，就能估算上亿基数，误差约0.81%

7.2 核心思想

直觉比喻：扔硬币，如果你看到有人连续扔出了10个正面，你会猜”他大概扔了1000多次”（2^10≈1024）

对每个元素计算哈希值，看哈希值二进制表示中前导0的最大个数

前导0越多 → 说明尝试的元素越多

hash(user1) = 0001011... → 前导0 = 3个
hash(user2) = 0000001... → 前导0 = 6个
hash(user3) = 0100101... → 前导0 = 1个

最大前导0 = 6 → 估算基数 ≈ 2^6 = 64

7.3 分桶取调和平均

单个估计波动太大，所以分成多个桶（通常2^14=16384个）

每个桶独立估计，最后取调和平均

调和平均对极端值不敏感，比算术平均更稳定

Redis的HyperLogLog就是用16384个桶，每个桶6bit → 总共12KB

7.4 误差

标准误差 ≈ 1.04/√m（m为桶数）

m=16384 → 误差 ≈ 1.04/128 ≈ 0.81%

对于”统计UV”这种场景，0.81%的误差完全可以接受

八、安全应用

8.1 密码哈希：为什么不能用SHA-256

SHA-256很快，GPU每秒可以算数十亿次

攻击者暴力破解6位密码：36^6=21.7亿，几秒搞定

专用密码哈希函数：故意设计得很慢

SHA-256:     ~10亿次/秒 (GPU)
bcrypt:      ~10万次/秒 (CPU, cost=12)
Argon2:      ~1万次/秒  (需要大量内存，抗GPU/ASIC)

同样的密码空间，攻击时间差10万倍

8.2 bcrypt的代价参数

bcrypt有个cost参数（通常10-14），每增加1，计算时间翻倍

cost=10: ~100ms/次
cost=11: ~200ms/次
cost=12: ~400ms/次  ← 推荐最低值
cost=14: ~1.6s/次

用户登录等400ms无感，但攻击者暴力破解就很痛苦

8.3 Argon2：内存硬函数

不仅慢，还要求大量内存（如256MB）

GPU有很多核心但每个核心内存少 → Argon2天然抗GPU并行攻击

这是2015年密码哈希竞赛的冠军算法

8.4 彩虹表与加盐

彩虹表：预先计算”常见密码→哈希值”的映射表

密码        SHA-256
123456   → e10adc...
password → 5baa61...
admin    → 8c6976...
... 数十亿条

拿到数据库泄露的哈希值，直接查表→秒破

加盐（Salt）防御：每个用户一个随机salt，存储 hash(salt + password)

用户1: salt=a7f3, 存储 hash("a7f3" + "123456")
用户2: salt=b2e1, 存储 hash("b2e1" + "123456")

两人密码相同，但哈希值完全不同
彩虹表失效——你得为每个salt建一张表

九、大数据应用

9.1 布隆过滤器的应用

爬虫URL去重：10亿URL用布隆过滤器只需约1GB内存

推荐系统已读过滤：用户已经看过的内容不再推荐

数据库查询加速：先用布隆过滤器判断key是否存在，避免无谓的磁盘IO（LevelDB、RocksDB都用了）

垃圾邮件过滤：已知垃圾邮件发件人黑名单

9.2 HyperLogLog的应用

UV统计：Redis PFADD/PFCOUNT 命令，12KB统计上亿UV

数据去重计数：日志中有多少不同的IP？

基数估算：数据库表某列有多少不同值？（查询优化器用这个决定索引策略）

9.3 MinHash / SimHash

相似度估算：两篇文档有多相似？两组用户有多重叠？

也是基于哈希的概率算法，大数据场景中常见

十、后端应用

10.1 HashMap设计与扩容

Java HashMap：初始容量16，负载因子0.75 → 存12个元素就扩容到32

扩容 = 新建2倍大小数组 + 所有元素rehash → O(n)操作

所以如果知道大概要存多少元素，初始化时指定容量可以避免多次扩容

# Python dict 也有类似机制
# 初始化时指定大小可以减少rehash
# CPython中 dict 在 2/3 满时扩容

10.2 Redis 渐进式 rehash

Redis不能一次性rehash（会阻塞服务）

策略：同时维护新旧两张表，每次操作时顺便迁移一小部分

渐进式rehash过程：

旧表: [a,b,c,d,e,f,g,h] (8桶，快满了)
新表: [_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_] (16桶)

每次GET/SET/DEL操作时，额外迁移旧表的1个桶到新表
查询时两张表都查
直到旧表完全清空，切换到新表

这样扩容的开销被分摊到每次操作中，不会突然卡顿

10.3 分布式缓存一致性哈希

Memcached/Redis集群的数据分片

节点宕机时只影响该节点的数据，其他节点不受影响

结合虚拟节点实现负载均衡

十一、Python 代码实战

11.1 生日悖论蒙特卡罗模拟

import random

def birthday_simulation(n_people, n_experiments=100000):
"""
模拟生日悖论：n_people个人中至少两人同天生日的概率
"""
collision_count = 0

for _ in range(n_experiments):
    birthdays = set()
    found_collision = False
    for _ in range(n_people):
        b = random.randint(1, 365)
        if b in birthdays:
            found_collision = True
            break
        birthdays.add(b)
    if found_collision:
        collision_count += 1

return collision_count / n_experiments

# 理论值计算
import math

def birthday_theoretical(n_people):
"""精确理论概率"""
p_no_collision = 1.0
for i in range(n_people):
    p_no_collision *= (365 - i) / 365
return 1 - p_no_collision

print("=" * 55)
print(f"{'人数':>4} | {'模拟概率':>10} | {'理论概率':>10} | {'差异':>8}")
print("=" * 55)

for n in [5, 10, 15, 20, 23, 30, 40, 50, 60, 70]:
sim = birthday_simulation(n)
theo = birthday_theoretical(n)
print(f"{n:>4} | {sim:>10.4f} | {theo:>10.4f} | {abs(sim-theo):>8.4f}")

print()
print("关键发现：23人时概率就超过50%！")
print("50人时概率已经高达97%！")
print("70人时几乎100%！")

11.2 简单布隆过滤器实现

import hashlib
import math

class BloomFilter:
"""简单布隆过滤器实现"""

def __init__(self, expected_items, false_positive_rate=0.01):
    """
    expected_items: 预计插入的元素数量
    false_positive_rate: 目标误判率
    """
    # 计算最优参数
    self.n = expected_items
    self.p = false_positive_rate
    
    # m = -n * ln(p) / (ln2)^2
    self.m = int(-expected_items * math.log(false_positive_rate) 
                 / (math.log(2) ** 2))
    
    # k = (m/n) * ln2
    self.k = int((self.m / expected_items) * math.log(2))
    self.k = max(1, self.k)
    
    # bit数组（用bytearray模拟）
    self.bit_array = bytearray(self.m // 8 + 1)
    self.count = 0
    
    print(f"布隆过滤器初始化:")
    print(f"  预计元素数 n = {self.n}")
    print(f"  目标误判率 p = {self.p}")
    print(f"  bit数组大小 m = {self.m} bits ({self.m/8/1024:.1f} KB)")
    print(f"  哈希函数数 k = {self.k}")

def _hashes(self, item):
    """用双重哈希模拟k个独立哈希函数"""
    h1 = int(hashlib.md5(str(item).encode()).hexdigest(), 16)
    h2 = int(hashlib.sha1(str(item).encode()).hexdigest(), 16)
    for i in range(self.k):
        yield (h1 + i * h2) % self.m

def _set_bit(self, pos):
    byte_idx = pos // 8
    bit_idx = pos % 8
    self.bit_array[byte_idx] |= (1 << bit_idx)

def _get_bit(self, pos):
    byte_idx = pos // 8
    bit_idx = pos % 8
    return (self.bit_array[byte_idx] >> bit_idx) & 1

def add(self, item):
    """插入元素"""
    for pos in self._hashes(item):
        self._set_bit(pos)
    self.count += 1

def might_contain(self, item):
    """查询元素（可能误判存在，不会误判不存在）"""
    return all(self._get_bit(pos) for pos in self._hashes(item))

# 测试
bf = BloomFilter(expected_items=10000, false_positive_rate=0.01)

# 插入10000个元素
for i in range(10000):
bf.add(f"item_{i}")

# 检查已插入的元素（应该全部返回True）
false_negatives = sum(
1 for i in range(10000) 
if not bf.might_contain(f"item_{i}")
)
print(f"\n已插入元素查询：{false_negatives}个漏报（应为0）")

# 检查未插入的元素（统计误报率）
false_positives = sum(
1 for i in range(10000, 20000) 
if bf.might_contain(f"item_{i}")
)
print(f"未插入元素查询：{false_positives}/10000 误报")
print(f"实际误判率：{false_positives/10000*100:.2f}%（目标：1%）")

11.3 一致性哈希环实现（带虚拟节点）

import hashlib
from collections import defaultdict

class ConsistentHash:
"""一致性哈希环，带虚拟节点"""

def __init__(self, virtual_nodes=150):
    self.virtual_nodes = virtual_nodes  # 每个物理节点的虚拟节点数
    self.ring = {}        # 哈希值 → 物理节点名
    self.sorted_keys = [] # 排序后的哈希值列表
    self.nodes = set()    # 物理节点集合

def _hash(self, key):
    """计算哈希值（取32位整数）"""
    return int(hashlib.md5(key.encode()).hexdigest(), 16) % (2**32)

def add_node(self, node):
    """添加物理节点（自动创建虚拟节点）"""
    self.nodes.add(node)
    for i in range(self.virtual_nodes):
        virtual_key = f"{node}#v{i}"
        h = self._hash(virtual_key)
        self.ring[h] = node
        self.sorted_keys.append(h)
    self.sorted_keys.sort()
    print(f"添加节点 {node}（{self.virtual_nodes}个虚拟节点）")

def remove_node(self, node):
    """移除物理节点"""
    self.nodes.discard(node)
    self.sorted_keys = [
        k for k in self.sorted_keys if self.ring.get(k) != node
    ]
    self.ring = {k: v for k, v in self.ring.items() if v != node}
    print(f"移除节点 {node}")

def get_node(self, key):
    """查找key应该存储在哪个节点"""
    if not self.sorted_keys:
        return None
    h = self._hash(key)
    # 二分查找第一个 >= h 的位置
    import bisect
    idx = bisect.bisect_left(self.sorted_keys, h)
    if idx >= len(self.sorted_keys):
        idx = 0  # 绕回环的起点
    return self.ring[self.sorted_keys[idx]]

# ===== 测试 =====
ch = ConsistentHash(virtual_nodes=150)

# 添加3个节点
for node in ["Server-A", "Server-B", "Server-C"]:
ch.add_node(node)

# 分配10000个key
distribution = defaultdict(int)
key_mapping = {}  # 记录每个key的归属
for i in range(10000):
key = f"user_{i}"
node = ch.get_node(key)
distribution[node] += 1
key_mapping[key] = node

print(f"\n=== 3节点时的分布 ===")
for node, count in sorted(distribution.items()):
print(f"  {node}: {count} keys ({count/100:.1f}%)")

# 添加第4个节点
print()
ch.add_node("Server-D")

new_distribution = defaultdict(int)
migrated = 0
for i in range(10000):
key = f"user_{i}"
new_node = ch.get_node(key)
new_distribution[new_node] += 1
if new_node != key_mapping[key]:
    migrated += 1

print(f"\n=== 4节点时的分布 ===")
for node, count in sorted(new_distribution.items()):
print(f"  {node}: {count} keys ({count/100:.1f}%)")

print(f"\n迁移的key数: {migrated}/10000 ({migrated/100:.1f}%)")
print(f"理论最优迁移: {10000//4} (25%)")
print(f"普通取模迁移: ~7500 (75%)")
print(f"一致性哈希大幅减少了迁移量！")

十二、练习题

练习1：生日攻击计算

一个哈希函数输出64位。

(a) 值域大小是多少？

(b) 用生日攻击找碰撞大约需要多少次尝试？

(c) 如果每秒能算10亿次哈希，大约需要多长时间？

参考答案：

(a) 2^64 ≈ 1.84 × 10^19

(b) ≈ 2^32 ≈ 4.29 × 10^9（约43亿次）

(c) 4.29×10^9 / 10^9 ≈ 4.3秒。所以64位哈希在安全上毫无意义。

练习2：布隆过滤器参数设计

你要存储1亿个URL，目标误判率0.1%。

(a) 需要多大的bit数组？

(b) 最优哈希函数个数是多少？

(c) 如果误判率放宽到1%，能省多少空间？

参考答案：

(a) m = -10^8 × ln(0.001) / (ln2)^2 ≈ 1.44 × 10^9 bits ≈ 172MB

(b) k = (m/n) × ln2 = 14.4 × 0.693 ≈ 10

(c) p=0.01时 m ≈ 9.58×10^8 bits ≈ 114MB，省约34%

练习3：一致性哈希迁移计算

一个一致性哈希环有5个节点，均匀分布，共100万条缓存。

(a) 增加1个节点，理论上需要迁移多少条？

(b) 如果用普通取模（%5变%6），大约需要迁移多少条？

(c) 为什么虚拟节点能改善数据分布的均匀性？

参考答案：

(a) 约100万/6 ≈ 16.7万条（只有新节点负责的范围需要迁移）

(b) 普通取模约迁移100万×5/6 ≈ 83.3万条（只有1/6的key碰巧不变）

(c) 3个物理节点在环上只有3个点，间距可能很不均匀。150个虚拟节点在环上有450个点，根据大数定律分布更均匀。

练习4：密码哈希选择

你在设计一个用户登录系统。

(a) 为什么不能用SHA-256直接存密码？

(b) bcrypt cost=12 时每次哈希约400ms，这对登录体验有影响吗？对暴力破解呢？

(c) 什么场景下应该选Argon2而不是bcrypt？

参考答案：

(a) SHA-256太快，GPU每秒数十亿次，6位密码几秒就破。而且没有内置salt机制。

(b) 用户登录多等400ms几乎无感，但攻击者每秒只能尝试2.5次（vs SHA-256的数十亿次），暴力破解时间从秒级变成天文数字。

(c) 当防御GPU/ASIC攻击时选Argon2，因为它不仅慢还需要大量内存，GPU虽然核心多但每个核心分到的内存少。

练习5：HashMap扩容分析

Java HashMap 初始容量16，负载因子0.75。

(a) 第一次扩容发生在插入第几个元素时？扩容后容量多少？

(b) 如果你知道要存1000个元素，初始容量设多少合适？为什么？

(c) Redis渐进式rehash的优势是什么？代价是什么？

参考答案：

(a) 16×0.75=12，插入第13个元素时触发扩容，容量变为32。

(b) 1000/0.75=1333，取最近的2的幂=2048。避免运行时多次扩容（16→32→64→128→256→512→1024→2048，需要7次扩容）。

(c) 优势：不会出现长时间阻塞，扩容开销分摊到每次操作中。代价：扩容期间需要同时维护两张表，内存暂时翻倍；每次操作多了迁移的额外开销。

十三、本章小结

| 概念 | 核心公式/数字 | 典型应用 |
| 生日悖论 | n ≈ 1.177√N 时 P>50% | 碰撞概率评估 |
| 生日攻击 | 2^(n/2) 次找碰撞 | 哈希安全性评估 |
| 哈希表负载因子 | α=元素数/桶数 | HashMap设计 |
| 一致性哈希 | 增删节点只迁移1/N数据 | 分布式缓存 |
| 布隆过滤器 | 误判率≈(1-e^(-kn/m))^k | URL去重/缓存穿透 |
| HyperLogLog | 12KB估算亿级基数 | UV统计 |
| 密码哈希 | bcrypt/Argon2故意慢 | 密码存储 |

一句话总结：哈希是”用确定性的随机”来换取效率和安全。理解背后的数学，才能选对工具、设对参数。

下一节预告：数学重学/20-图论基础

---

上一章	目录	下一章
18-树与递归结构	数学重学路线图	20-描述统计与可视化