你整理文件时，发现两份文件各自算出了一串摘要，长度一样，字符也完全一样。可以直接删掉其中一份吗？
先别让“数字指纹”这个比喻替我们作决定。指纹听起来像唯一身份，摘要却是按规则计算出来的短编号。要判断同编号是否说明同内容，得先问：可能的内容有多少种，编号又有多少种？
上一章用乘法数清了二元开关的状态。本章继续用计数，不过目的变了：不再列出所有选择，而是证明某种区分必定做不到。我们会发现，碰撞可以无可避免，具体碰撞却未必已经知道；工程系统也可以在承认碰撞的前提下，正确地保存和查找数据。
先约定怎样给内容编号
把当前讨论的不同输入组成集合 A，把允许使用的编号组成集合 B。规定一套规则 h，让 A 中每个输入恰好得到 B 中一个编号，写作 h：A → B。这叫作从 A 到 B 的映射，也叫函数；h(x) 表示输入 x 得到的输出。这里先讨论两个集合都有限的情况。
“恰好一个”很重要。一个输入不能一会儿得到甲号、一会儿得到乙号。实际算法如果带有参数，我们就固定同一算法和同一组参数再比较。对于文件，本章把内容理解为完整的字节序列，文件名和存放路径不算在内。
如果两个不同输入 x、y 得到同一编号，即 x ≠ y，而 h(x)=h(y)，就发生了一次碰撞。同一文件算两次得到相同摘要，不叫碰撞，因为这里缺少“输入不同”这个条件。
这里数的是不同内容，而不是磁盘上有几个副本。同一段内容被复制十次，可能出现十个文件，却仍只有一种输入。若要用对象数量证明不同内容碰撞，必须先保证被数进去的输入彼此不同；否则十个副本共用一个摘要，完全符合预期。
把编号想成盒子的标签，每个输入沿着规则进入一个盒子。碰撞就是某个盒子里装进了至少两个不同输入。盒子的名称、颜色和摆放次序都不会改变这个事实。
五个对象，四个编号
假设有五个不同对象，却只允许使用 00、01、10、11 四种编号。怎样分配才能让每个对象独享一个编号？
试着让前四个对象各用一个，第五个就没有新编号了。换一种顺序也没有帮助。为了把这个直觉说完整，我们用一次反证：先假设可以不发生碰撞，再看它会带来什么结果。
如果没有碰撞，每个编号至多分给一个对象。四个编号合起来至多容纳四个对象。但我们要求五个对象全部获得编号，矛盾。因此，没有碰撞的假设不成立，至少两个对象必定同号。
还有一个前提藏在“全部获得编号”里。如果允许拒绝第五个对象，或者给它一个约定之外的新编号，当然可以绕开眼前的冲突，但任务也随之改变了。我们的论证针对的是：每个候选都要处理，而且输出始终落在同一组有限编号中。
将“四”和“五”换成 n 和 n+1，证明一字不差地成立：n 个盒子，每盒至多装一个，合起来至多装 n 个，装不下 n+1 个。这就是鸽巢原理。对象更多时，从中先取 n+1 个，也已经足以推出碰撞。
MIT《Mathematics for Computer Science》第14.8节把它表述为有限集合之间的映射结论：输入集合的元素数大于输出集合的元素数时，必有两个不同输入映到同一输出。应用时，要说清楚对象、盒子，以及分配规则，不能只看到两个大小不同的数字就套用。
固定长度到底提供多少编号
现在把四个编号推广到 b 位二进制摘要。b 是正整数；每位只能是 0 或 1。按上一章的乘法计数，长度恰为 b 的二进制串共有 2^b 种。
因此，b 位摘要至多提供 2^b 种输出。有的算法未必用得到全部输出，但这只会减少可用编号，不会增加容量。
输入需要多大，才足以证明碰撞？不必讨论所有可能长度。只考虑长度恰为 b+1 的全部二进制串，就有 2^(b+1) 种输入。只要算法接受这些输入并都输出 b 位摘要，就有：
2^(b+1) = 2 × 2^b > 2^b
输入比编号多，鸽巢原理立即适用。这里两个集合都是有限的，已经完成了证明。
如果文件接口只接受整字节输入，可以改取固定的L字节，使8L＞b。只要算法接受这一长度的全部文件，就有2^(8L)＞2^b种不同内容，仍然必有碰撞。
例如，输出只有两位时，编号最多四种；三位输入却有 000、001、010、011、100、101、110、111 八种。无论计算过程多复杂，都无法把这八种输入分到四个编号中，同时保持彼此不同。
事实上，不必凑齐那一整组输入；只要拿到 2^b+1 个彼此不同且被算法接受的输入，也必有碰撞。这个数量给出了一条保证重复的界限，不表示在它之前绝不会重复。余下多少空编号，与某两个对象是否已经同号，是两件事。
这也解释了为什么“把算法写得更巧”不能消除容量限制。算法可以改变哪些输入同号，却不能凭空创造第五种两位二进制串。增加输出位数可以增加容量；在新的容量之上，同一个计数问题仍然存在。
亲手算一次碰撞
为了看清编号怎样丢掉区别，我们用一个很小的规则：h(x)=x mod 4。这里 x 是非负整数，mod 4 表示除以 4 后取余数，所以输出只能是 0、1、2、3。
把 1、5、9 分别写成：
1 = 4×0+1，5 = 4×1+1，9 = 4×2+1
三个数的商不同，余数却都是 1。因此 h(1)=h(5)=h(9)=1。这个规则保留了余数，舍去了“包含多少个完整的四”。看见输出 1，我们已经无法仅凭它判断原来是哪个数。
再算 h(6)=2。因为 1 和 2 是不同输出，可以确定输入 1 与输入 6 不同。为什么这一步成立？如果两个输入相同，在固定规则下就应得到同一输出；输出不同，便排除了输入相同的可能。
联系第02章的条件方向，可以把结论压成两行：
输出不同 → 输入不同
输出相同 ↛ 输入相同
符号 ↛ 表示“不能据此推出”。第二行不是说同号输入一定不同，而是说它们可能相同，也可能不同，现有信息不足以判断。第一行同样要求使用同一个确定规则，不能拿两个算法的结果直接套用。
证明存在，还没有回答哪些问题
图1中只有甲、乙共用 00，丙、丁、戊各自独占一个编号。五个对象到四个编号已经有碰撞，却不能据此说“丙一定有另一个同号对象”。“至少有一对”与“每一个都有伙伴”，是不同强度的陈述。
存在也没有自动变成容易寻找。上面的余数规则很简单，我们能直接写出 1 和 5；对于另一个规则，鸽巢原理仍可证明有碰撞，却没有告诉我们应该尝试哪些输入，更没有给出寻找所需的时间。
这一区分也适用于技术名称。用于分桶的一般散列规则，与密码学散列函数的设计要求不能混为一谈。NIST 对碰撞抵抗性的定义关心的是找到碰撞在计算上是否可行。仅凭本章的存在证明，既不能评价某个具体算法安全，也不能宣称它已经被破解。
同样，我们还没有回答“抽取多少对象通常会碰撞”或“撞上的机会有多大”。这些问句增加了选择对象的方式，属于之后的概率问题。不要把本章的必然性证明读成随机实验的预测。
编号有限，并不意味着小范围内必有碰撞
标题里的“必定”，有明确前提：不同候选输入多于可用编号。若只允许输入 0、1、2、3，仍采用除以 4 取余，它们的输出依次是 0、1、2、3，就没有碰撞。
在约定的输入范围内，不同输入总得到不同输出，这样的映射叫作单射。如果有限候选数不超过编号容量，可以给每个候选分配不同编号，构造一个单射。
但“可以构造”不是“任意规则都行”。只允许输入 1、5、9 时，三个候选少于四个编号，余数规则却仍把它们全送到 1。容量够用说明没有被数量逼入死角，实际规则是否保留区别，还得检查。
还可以试着改造那五个对象的任务：在原来编号后面加一位，就有八种编号可选，可以给五个对象各分一个。这样做确实解决了这组对象的区分问题，但用的是更大的输出集合。若有人仍把它说成“四个编号装下五个不同身份”，便把新增的一位从账本里漏掉了。检查容量时，凡是用来区分对象的额外标记，都应算进输出。
因此，一个系统声称编号唯一时，要先问它对哪一组对象承诺唯一。对一个已知的小集合逐个分配号码，与把所有允许内容压成同样长度的摘要，承担的任务可能很不一样。
允许同桶，仍然能够正确查找
现在做一个小字典：用整数作为 key，也就是查询时提供的键；每个键旁边保存一条记录。我们把键按除以 4 的余数分到四个桶，但保留完整的键，不只保存桶号。
假设 1 号桶内依次有键 1、5、9。查找键 9 时，先算 h(9)=1，到 1 号桶；再检查原始键：1 不等于 9，5 不等于 9，直到遇到 9，才取出对应记录。假如查询的是 13，虽然同样进入 1 号桶，但逐个检查后没有相等的键，就应回答“没找到”。
散列值在这个设计里负责缩小候选范围，原始键的相等判断负责确认身份。真实实现可以采用不同的存放和查找办法，不能把图中的逐个检查当成所有字典的内部结构。Rust 的 HashMap 官方文档同时要求键支持相等判断和散列，并要求相等的键有相等的散列值；这个方向与我们刚才的逻辑一致。
回到文件去重：如果要求严格按字节内容判断，可以把摘要相同的文件列为候选，再核对完整内容；仅凭相同摘要就合并，是额外采用的一项判断规则。是否接受这种规则，要看系统要求和具体设计，不能把它冒充为“同摘要必定同文件”的数学定理，也不能假定每个现成工具都逐字节复核。
有人会想到再核对文件长度。这可以继续排除候选，却不能自动补成证明：前面用于计数的输入本来就具有同样长度；对整字节文件，也已选定同一个L字节长度。即使它们的摘要和长度都相同，仍可能是不同内容。每增加一个核对条件，都应问它究竟排除了哪些情况，而不是把检查项的数量当作正确性的保证。
有限编号的价值因此仍然很实在。它可以帮我们组织对象、排除不可能相同的候选；而每当我们想让它独自证明身份，就需要重新检查，它保留下来的区别是否足够。
顺手试一下
题目1：三位编号够不够
一个系统要给九种不同状态分配恰好三位二进制编号，每种状态都必须得到一个编号。能否保证不同状态绝不同号？若只剩七种状态，是否任何分配规则都不会碰撞？
**提示：**先数编号，再区分“存在一种好分配”和“所有分配都好”。
**参考答案：**三位二进制共有 2³=8 种编号。九种状态多于八种编号，若每个编号最多分给一种状态，至多容纳八种，与九种矛盾，所以必有碰撞。七种状态时，可以依次使用 000 到 110 这七个不同编号，因而存在无碰撞分配；也可以把两种状态都分给 000，因此不能保证任何规则都无碰撞。
题目2：同桶后该返回什么
沿用图3的小字典，1号桶保存键 1、5、9，记录分别是“甲”“乙”“丙”。查询键 13 时，一个程序只比较桶号便返回“甲”。它错在哪里？如果两个文件的摘要不同，又可以得出什么结论？
**提示：**把“桶号相等”和“原始键相等”分别列为判断条件。
**参考答案：**h(13)=1 只能说明应查1号桶，不能推出 13=1。逐个比较后，13 与 1、5、9 都不相等，应回答未找到。对于两个文件，若摘要由同一确定算法、同一参数、完整且未变化的内容正确算出，摘要不同就能推出字节内容不同；相同内容不可能在这些条件下产生不同输出。
来源与延伸阅读
- MIT《Mathematics for Computer Science》，第14.8节，印刷页572—574：鸽巢原理的有限映射表述与适用对象
- Rust 标准库 HashMap 文档：散列与键相等判断的约定；本章分桶图为独立教学模型
- NIST CSRC 术语表 Collision resistance：区分碰撞存在与寻找碰撞的计算要求
作者：Jiancheng Wang · 数学之美（独立原创）