上周三下午,一个读接口的 P99 从 40 毫秒涨到了 900 毫秒。缓存是团队自己写的一个简单哈希表,固定 1000 个桶,链地址法,装进去的键大约 1200 个。值班的同学第一反应是「桶太少了,扩一下」。
开发同学不同意,理由是:1200 个键撒进 1000 个桶,撞一两个很正常,可怎么会把接口拖慢二十倍?于是把每个桶的链长打出来看。结果最长的一条链挂了 6 个键,全部 1200 个键里,有 500 多个不是自己桶里的第一个元素。也就是说,冲突不是零星发生,而是接近一半的键都在排队。
这件事的答案在离散数学的第一课里:1000 个桶装 1200 个键,冲突不是「可能发生」,而是「一定发生」。这条规律叫鸽巢原理。它只保证重复存在,不告诉你在哪个桶;它能给一个很弱的下界,真正估算规模还得靠期望。这篇从这次排查出发,讲清鸽巢原理、生日悖论、哈希冲突的估算,以及加法原理、乘法原理和容斥。
鸽巢原理:只保证有,不告诉你在哪
鸽巢原理(pigeonhole principle)也叫抽屉原理,标准表述只有一句:把 n+1 个物品放进 n 个抽屉,至少有一个抽屉里放了两个或更多物品。
证明用反证法,一行就够。假设每个抽屉最多放一个,那么 n 个抽屉最多装 n 个物品,和「有 n+1 个物品」矛盾。所以假设不成立,必然有抽屉超载。注意这个证明没有指出是哪个抽屉,它只是排除了「所有抽屉都不超载」这一种情况。
这一点非常重要,因为它决定了鸽巢原理的用途。它是存在性定理:告诉你「一定有两个人生日相同」,但不告诉你哪两个人。真要把这一对找出来,还是得建表、排序或者两两比较,该花的 O(n) 时间和额外空间一分都省不掉。它最大的价值是在分析阶段直接排除一类可能性,让你不用去猜。
最常见的例子是生日:一年最多 366 天,所以 367 个人里必然有两个人同一天生日。同理,13 个人里必然有两个人同一个月出生,因为月份只有 12 个。
常见的误用是把「n 不大于 m」当成「不会冲突」。鸽巢只保证 n 大于 m 时必有冲突,没说 n 小于等于 m 时一定没有;n 接近 m 的平方根时冲突就已常见,下一节会算。
加强形式:至少一个抽屉有 ceil(n/m) 个
把 n+1 和 n 换成一班的数量,可以得到更好用的形式:把 n 个物品放进 m 个抽屉,至少有一个抽屉里装了 ceil(n/m) 个或更多物品,其中 ceil 是向上取整。
证明还是反证。如果每个抽屉最多装 ceil(n/m) - 1 个,那么 m 个抽屉总共最多装 m × (ceil(n/m) - 1) 个。它严格小于 n,因为 ceil(n/m) - 1 小于等于 n/m,矛盾。
拿开头那组数验证:1200 个键、1000 个桶,ceil(1200/1000) = 2,所以至少有一个桶装了 2 个键。这个下界弱得可笑,实测最长链是 6,冲突键有 500 多个。但它至少把「不会冲突」这个念头彻底掐死了。
再看一个日常例子。100 个文件分到 9 个目录,平均每个目录 11.1 个,ceil(100/9) = 12,所以不管怎么分,至少有一个目录装了 12 个文件。13 个人分到 12 个月份,ceil(13/12) = 2,所以至少两个人同月。这两个例子用的是同一个公式,只是数字不同。
注意方向:它说的是「最大的抽屉至少有多少」,不是「每个抽屉都有这么多」。要保证每个抽屉至少 k 个,需要 n ≥ m × k,那只是平均数的推论。
生日悖论:碰撞比直觉早得多
生日悖论(birthday paradox)说的是:一个房间里只要有 23 个人,存在两个人同一天生日的概率就超过一半。它叫悖论,不是因为逻辑矛盾,而是因为结论和直觉差得太远。多数人会觉得 23 个人、365 天,怎么也得凑到上百人才像话。
直觉错在一个地方:我们下意识算的是「有没有人和我同生日」,这个概率大约只有 23/365,约 6%。但题目问的是「任意两个人同生日」,23 个人能配出 C(23, 2) = 253 对,每一对都有约 1/365 的概率撞上。253 对里只要有一对撞上就够了,所以概率远高于 6%。
精确算法是先算「所有人都不相同」的概率,再用 1 减去它。第一个人随便选,第二个要避开第一个,概率是 364/365,第三个要避开前两个,概率是 363/365,一直乘到第 n 个。这个连乘不依赖模拟,跑一次就是精确值。
def birthday(n, days=365):
p = 1.0
for i in range(n):
p *= (days - i) / days
return 1 - p
for n in (10, 23, 32, 50, 70):
print(n, round(birthday(n), 6))
在本机 Python 3.15 上跑,输出是:
10 0.116948
23 0.507297
32 0.753348
50 0.970374
70 0.99916
23 个人时概率是 0.507297,刚过一半;到 50 个人已经是 0.970374;70 个人是 0.99916,几乎必然。增长这么陡,是因为配对数是按人数的平方增长的,而每一对撞上的概率是固定的。
有一个很好用的近似公式:当 n 不太大时,概率大约是 1 - e^(-n(n-1)/(2×365))。代入 n=23,指数部分是 253/365 = 0.693151,1 - e^(-0.693151) 约等于 0.500002,和精确值几乎一样。这个近似也解释了为什么阈值是 23:要让概率过半,需要 n(n-1)/2 接近 365 乘以 ln 2,也就是 253 左右。
生日悖论不只适用于生日。任何「从 m 种可能里随机取,看有没有重复」的场景都服从同一规律:取样数量接近 sqrt(m) 时,重复概率已过半。64 位哈希有 2^64 种取值,平方根约 43 亿;键数到十亿量级时,纯随机碰撞的概率已不可忽略。
哈希冲突:为什么躲不掉
哈希表(hash table)的工作分两步。第一步把键送进哈希函数,得到一个整数;第二步用这个整数对桶数取模,决定放进哪个桶。冲突因此在两个位置产生:不同的键算出同一个哈希值,这叫哈希碰撞;不同的哈希值取模后落到同一个桶,这叫桶冲突。前者取决于哈希函数,后者取决于桶数。
鸽巢原理直接管第二层:键数超过桶数,必然有桶装两个以上。这和哈希函数写得好不好没有关系,哪怕哈希函数完美均匀,只要桶比键少,就一定有冲突。所以「我们的哈希函数很均匀,不会冲突」这句话在逻辑上就不成立,均匀只影响冲突分得平不平,不影响冲突有没有。
即使键数没超过桶数,生日效应仍然在。假设桶数是一百万,键数是几千,冲突对数的期望是 C(n,2)/m,几千的平方除以一百万,已经是个不小的数。哈希表的设计从来不是「避免冲突」,而是「让冲突可控」:链地址法把冲突的键串成链表,开放寻址法在冲突时往后找空位。
装载因子(load factor)是键数除以桶数,通常记作 α。它是哈希表性能最直接的指标。α 越大,桶越挤,链越长,查询从接近常数退化成线性扫描。主流实现会设一个阈值:Java 的 HashMap 默认 0.75,超过就扩容到两倍;Python 的 dict 在装载到大约三分之二时扩容。你看到「装载率过 0.7 之后查询明显变慢」,不是实现有 bug,是设计上就预料到的事。
还有一层容易忽略的成本:扩容本身要重新计算所有键的位置。桶数从 m 变成 2m,原来的哈希值对 2m 取模,几乎每个键都要搬家。一次性做完就是 O(n) 的停顿,几百万键的缓存会卡住几百毫秒。工程上的解法是渐进式 rehash,每次操作顺手搬几个桶,把一次大停顿摊成很多次小开销。
期望冲突数:从「至少一对」到「大概多少对」
鸽巢原理给的下界只有一对,实际冲突却是几百对,中间差了三个数量级。要把这个差距补上,需要用期望来估算。对每一对键定义指示变量,落在同一个桶记 1,否则记 0;每对同桶的概率是 1/m,所以冲突对数的期望就是对数乘以概率。
from math import comb
n, m = 1200, 1000
print(round(comb(n, 2) / m, 1))
print(round(n - m * (1 - (1 - 1 / m) ** n), 3))
输出是:
719.4
501.013
第一行 719.4 是「同桶键对」的期望数,也就是 C(1200,2)/1000 = 719400/1000。第二行 501.013 是「不是桶里第一个元素」的键的期望数,这个指标更贴近实际观察到的冲突代价,因为链上除了头节点,每个节点都要多一次比较。实测跑三次随机分布,得到的数字是:
import random
def stats(n, m, seed):
rng = random.Random(seed)
buckets = [0] * m
for _ in range(n):
buckets[rng.randrange(m)] += 1
used = sum(1 for b in buckets if b)
return max(buckets), n - used, used
for seed in (1, 2, 3):
print(seed, stats(1200, 1000, seed))
1 (5, 479, 721)
2 (6, 518, 682)
3 (6, 517, 683)
三个种子下,冲突键数分别是 479、518、517,和期望 501 很接近;最长桶是 5 到 6,而鸽巢只保证 2。三个数字和期望吻合,也说明只看鸽巢下界会严重低估规模。
从这个式子还能读出一个重要结论:冲突对数和对数成正比,也就是和 n × α 成正比。键数翻倍,冲突对数大致翻倍;桶数翻倍,冲突对数大致减半。所以扩容能缓解冲突,但不能消除;键继续增加,冲突继续长。
加法原理与乘法原理:两种最基本的数法
鸽巢和生日解决的是「有没有重复」,接下来的问题是「一共有多少种」。计数(counting)看着像小学奥数,实际是离散数学的主干,因为复杂度分析、概率计算、组合枚举都建立在它上面。最基本的两条规则是加法原理和乘法原理。
加法原理(sum rule)说的是:如果完成一件事有若干类互斥的做法,第 1 类有 n1 种,第 2 类有 n2 种,以此类推,那么总做法数就是各类相加。从北京去上海,高铁 12 班、飞机 8 班、夜班大巴 3 班,假设这些班次没有一班被重复统计,一共就是 23 种走法。
它的前提是「互斥」,也就是同一件事不能同时属于两类。这个前提经常被人跳过,然后算出错误答案。比如统计「用过 Python 或用过 SQL 的用户」,如果直接用「用过 Python 的人数」加「用过 SQL 的人数」,两样都用过的人就会被算两次,总数偏大。修法就是后面要讲的容斥。
乘法原理(product rule)说的是:如果完成一件事要分成若干步,第 1 步有 n1 种选择,第 2 步有 n2 种,每一步都必须做,那么总做法数是各步相乘。用户名规定为 2 个字母加 3 位数字,每位都可以独立选择,可用的组合就是 26 × 26 × 10 × 10 × 10。
print(26 ** 2 * 10 ** 3)
print(3 * 4 * 2)
676000
24
第二行 24 是一个灰度发布的实际例子:3 个平台、4 个地区、2 个版本,每个用户按三层各自独立地落一个桶,总共 24 个桶。这种多层因子相乘在实验平台里很常见,成立的前提是每层选择互不影响。
判断该用加还是乘,只问一句话:这件事是「分成几类,做其中一类就够」,还是「分成几步,每一步都要做」。前者相加,后者相乘。两句都套不上的,多半是分类不互斥或者步骤不独立,得先把结构理清楚再算。
容斥入门:把重复算的减回去
容斥原理(inclusion-exclusion)解决的就是分类不互斥的情况。两个集合的版本只有一行:|A ∪ B| = |A| + |B| - |A ∩ B|。先把两个集合的大小加起来,再减去交集,因为交集里的元素在上一步被算了两次。
举个具体数字。1000 名活跃用户里,620 人用过 Python,480 人用过 SQL,300 人两样都用过。直接相加得到 1100,超过了总人数 1000,显然不合理。减去交集 300,得到 800,这才是「至少用过一种」的人数;再用 1000 减 800,得到 200 人两样都没用过。
total = 1000
py, sql = 620, 480
both = 300
union = py + sql - both
print(union, total - union)
800 200
为什么不能简单相加?把 A 和 B 摊开,交集被覆盖两层,其他部分只有一层;要得到并集大小,就得削掉多出来的一层。这不是技巧,是加法前提被破坏后的修补。
三个集合的公式会长一些:|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|。规律是奇数个集合的交加,偶数个集合的交减。三个集合时,三重交集先加三次再减三次,正好抵消,要再加回一次。下一篇会拿具体数字把它算一遍。
容斥和加法原理的关系,可以这样理解:加法原理要求分类互斥,容斥是把不互斥的分类改造成互斥的分类。工程上遇到「统计口径对不上」,先别急着怀疑数据,先看是不是有两类东西被重复计数了。
一张现象对照表
下面这些现象在缓存、统计和实验平台里都出现过,原因大多能回到鸽巢和计数上。
| 现象 | 真实原因 | 第一步查什么 |
|---|---|---|
| 装载率过 0.7 后查询明显变慢 | 桶数固定,冲突对数按 n 的平方除以 m 增长,链变长 | 打印桶长分布和最长链,算出当前的键数与桶数之比 |
| 1000 个桶放 1200 个键,被当成 bug 排查 | 鸽巢原理,键数超过桶数时冲突必然发生,与哈希函数质量无关 | 确认桶数和键数,算一下 ceil(n/m) |
| 去重后数量比预期多 | 相等判断口径不统一,或哈希与相等没有基于同一组字段 | 抽样打印重复项的 repr 和类型,看差在哪 |
| 两个分组的人数加起来超过总数 | 分类不互斥,交集被加了两遍 | 确认两组是否可能重叠,重叠部分是否需要减掉 |
| 23 人同生日的概率被估成 6% | 按「和某个人同生日」算,实际问的是任意两人 | 改用连乘算「全不相同」的概率,再取补 |
| 扩容之后接口仍然慢 | 一次性 rehash 造成停顿,或扩容期间双表并存、迁移开销摊在请求上 | 看扩容是阻塞式还是渐进式,迁移期间有没有锁竞争 |
| 布隆过滤器说「存在」,实际查不到 | 假阳性是它的设计特性,不是数据错误 | 检查位数组长度和哈希个数,按目标误判率重新配置 |
边界与代价
第一,鸽巢只保证存在,不保证容易找到。它不会告诉你哪两个键撞了,也不会给你一个找出它们的算法。真要定位冲突,还是得建索引或者排序比较,成本一样要付。
第二,生日悖论假设分布均匀且独立。真实数据很少满足:生日在月份上有聚集,ID 常带固定前缀。分布越不均匀,冲突来得越早,概率比公式更高;反之可能更低。要拿真实分布重算,不能直接套 365。
第三,分类必须互斥且穷尽:漏掉一类会算少,两类重叠会算多。容斥能修重叠,修不了遗漏,遗漏只能重新梳理分类维度。
第四,期望不是保证。期望 500 个冲突键,单次实测可能在 450 到 550 之间波动,极端情况下会更多。容量规划要留余量,不能拿期望值当上限用。对延迟敏感的服务,还要考虑最坏情况下的长链。
第五,哈希的随机性可以被对抗。如果键由外部用户提供,攻击者可以构造一批哈希值相同的键,把所有元素挤进同一个桶,把常数查询退化成线性扫描。语言运行时通常会加随机种子缓解,但不是所有环境都默认开启。
第六,容斥的项数随集合数量指数增长。两个集合 3 项,三个集合 7 项,十个集合就是 1023 项。集合一多,容斥就只适合做理论推导,实际计算要换动态规划或者按位枚举。
小结与练习
主线压成三句:鸽巢只保证「一定有重复」,不负责找出来;加强形式给出下界,生日悖论说明这个下界离实际有多远;计数方面,加法管互斥分类,乘法管独立分步,容斥修补不互斥的分类。
回到开头那次排查:1200 个键放进 1000 个桶,鸽巢保证至少有一个桶装 2 个,期望算出来是 500 个键要排队,实测 479 到 518。三个数字分别对应「有没有」「至少多少」「大概多少」,正好是这一节的三层工具。
当天可以自己验证的练习:
- 用文中的连乘法算 10、23、32、50、70 人同生日的概率,和文中五个小数逐位对照;再把 23 换成 22,看概率是否掉到一半以下。
- 构造 13 个人的出生月份,让 12 个月份都出现,验证第 13 个人必然和其中某人同月;再构造 12 个人,看能不能做到人人不同月。
- 跑 1200 个键、1000 个桶的随机落桶十次,记录最长链和冲突键数,和
C(1200,2)/1000 = 719.4这个期望对照,看波动有多大。 - 把容斥例子里「两样都会」的 300 改成 400,重算并集和都不会的人数;再想一下,如果这个数超过 480,说明数据哪里有问题。
- 算一个 2 个字母加 3 位数字的用户名空间,再估算 100 万用户时重名的期望对数,提示:用
C(1000000,2)/676000。
这一篇停在「一定存在重复」,没回答「一共有多少种可能」。从「有没有」到「有多少」,需要组合公式:从 n 个里取 k 个,有序与无序怎么算,重复元素怎么去重,多个条件怎么容斥。这是下一篇的内容。