哈希算法
上次短码冲突的事故让我心有余悸。两个不同的长链接，居然生成了同一个短码。用户点击后跳到了别人的页面——这种 bug 发生一次就够要命了。
我花了一个晚上研究哈希算法。不是那种走马观花的浏览，而是真的把公式和例子一项项算清楚，搞清楚到底哪里出了问题。
先从最根本的问题开始：如何把一个任意长度的 URL，变成一个固定长度的短标识符？ 长链接可能几百上千个字符，但短码只有 6-8 个字符的空间。中间这个”压缩”的过程，怎么才能保证不丢信息、不出错？
最直觉的答案就是——哈希函数。
输入（任意长度） → 哈希函数 → 输出（固定长度）
"https://example.com/very/long/path" → MD5 → "b10a8db164e0754105b7a99be72e3fe5"
"https://example.com/short" → MD5 → "27b843d58f5a78936ab363b5e7b7f410"不管输入多长多短，输出的长度永远一样。这正是我需要的。
我之前的方案很简单：对 URL 算 MD5，截取前 6 位，搞定。
落地思路
- 我的实现是：对 URL 算 MD5，把 32 位十六进制的哈希值转成整数，对 62 的幂取模，再编成 6 位 Base62。
- 取模这一步等价于截断：只保留了哈希低位的一部分信息，高位被整段丢掉。
- 同一个 URL 每次算出来都一样，所以相同链接不会生成两个短码——这是 MD5 确定性带来的好处。
- 兜底是没有的：截断之后短码只由哈希的前几位决定，两个不同 URL 完全可能撞成同一个短码。
MD5 本身有几个好用的特性，这些特性让我一开始觉得它很靠谱：
- 确定性：同一个 URL，不管算多少次，结果都一样。这意味着相同的链接不会生成两个不同的短码。
- 雪崩效应：输入哪怕只差一个字符，输出也天差地别。上面那个例子，多了一个
/，哈希值从b10a8d变成了66f0cf，完全不相关。 - 不可逆：没法从哈希值反推出原始 URL。用户看到短码，猜不出原始链接长什么样。
- 速度快：微秒级就能算完。对于一个每秒可能处理上千个请求的短链接服务来说，这点很重要。
这些特性看起来完美。但问题不在 MD5 本身，而是出在我接下来的操作上——截断。
MD5 输出 32 个十六进制字符，也就是 128 位。32 个字符的”短链接”一点也不短——short.url/b10a8db164e0754105b7a99be72e3fe5，比我原来的 URL 还长。
所以我截取了前 6 位。这正是事故的根源。
截断之后的碰撞概率
我用生日悖论的公式算了一笔账。6 位十六进制，可能的组合数是 16^6 = 16,777,216，大约 1677 万。
落地思路
- 6 位十六进制的空间是 16^6 = 16,777,216，只有约 1677 万个坑。
- 把 10 万条 URL 代进生日悖论公式
1 - Π(1 - i/d)，冲突概率算出来是 95%。- 这个数字说明：不是空间快用满了才出事，而是在空间还很空的时候就已经开始大面积撞车。
- 换成 8 位十六进制（42.9 亿）或 6 位 Base62（568 亿）才能把概率压下去，但根本矛盾没变。
10 万条 URL，冲突概率就飙到了 95%。 难怪我出事了。这才几千条数据就开始撞车，我居然之前一直没注意到。
哈希碰撞并不是什么小概率黑天鹅，而是数学上必然会发生的事情。有限的空间（1677 万个坑），装越来越多的 URL，迟早撞车。这就像鸽笼里塞鸽子——笼子不够，必然有两只挤在一起。更让人不安的是，由于生日悖论，冲突不需要等到空间用完才出现，远在此之前就会大规模爆发。
我试了不同截取长度，整理了一张表：
| 截取长度 | 字符集 | 可能组合数 | 冲突概率（10 万条） |
|---|---|---|---|
| 6 位 | 16 进制 | 16^6 ≈ 1677 万 | 95% ⚠️ |
| 8 位 | 16 进制 | 16^8 ≈ 42.9 亿 | 0.12% |
| 6 位 | 62 进制 | 62^6 ≈ 568 亿 | 0.009% |
| 8 位 | 62 进制 | 62^8 ≈ 218 万亿 | 极低 |
6 位十六进制完全不够用。如果换成 62 进制，同样的 6 位，空间从 1677 万暴涨到 568 亿——但这需要先解决编码问题（下一节再说）。
常见哈希算法对比
我把能找到的哈希算法都过了一遍：
| 算法 | 输出长度 | 安全性 | 速度 | 适用场景 |
|---|---|---|---|---|
| MD5 | 128 位（32 字符） | 低（已破解） | 快 | 非安全场景 |
| SHA1 | 160 位（40 字符） | 中（已破解） | 快 | 非安全场景 |
| SHA256 | 256 位（64 字符） | 高 | 中 | 安全场景 |
| MurmurHash | 32-128 位 | 低 | 很快 | 哈希表、数据库 |
短链接不需要加密安全性，我不怕别人”破解”我的短码。我只需要：快速计算、低冲突率、输出长度合适。
所以 MD5 或 MurmurHash 理论上是不错的选择——前提是截取长度够用。
我接着尝试了 SHA256，想看看更强的哈希算法能不能解决问题。
落地思路
- 换成 SHA256 后哈希值从 32 个字符变成 64 个，截取同样位数时指纹空间更大，分布也更均匀。
- 但碰撞率只取决于截取后的空间：8 位就是 16^8 ≈ 42.9 亿种可能，和用哪个算法无关。
- 代价也要算：SHA256 的计算速度只有 MD5 的三分之一左右，每次创建都要多花一次哈希的时间。
- 结论是 SHA256 解决的是完整输出的碰撞抗性，不是截断之后的冲突问题。
SHA256 的输出是 64 个十六进制字符，比 MD5 的 32 个多了一倍。截取前 8 位的话，碰撞概率确实更低——因为即便截断，每次哈希都是在一个更大的”指纹空间”里取样。
但问题没变：不管哈希算法多强，截取之后的空间还是有限的。 8 位十六进制就是 16^8 ≈ 42.9 亿种可能，和算法是 MD5 还是 SHA256 无关。
而且 SHA256 的计算速度比 MD5 慢大约 3-5 倍。短链接服务是要扛高并发的，每个请求都要做一次哈希计算，这个开销不能忽视。
我在心里列了个账：
| 维度 | MD5 | SHA256 |
|---|---|---|
| 输出长度 | 32 字符 | 64 字符 |
| 碰撞抗性（完整输出） | 弱 | 强 |
| 截断后碰撞率 | 取决于截取长度 | 相同截取长度下几乎一样 |
| 计算速度 | ~600 MB/s | ~200 MB/s |
| 短码长度 | 截断后一样短 | 截断后一样短 |
结论让我有点沮丧：换更强的哈希算法，并不能从根本上解决截断碰撞的问题。 碰撞率取决于截取后的空间大小，而不是哈希算法本身。SHA256 确实比 MD5 更安全、更抗碰撞——但那是指完整输出。一旦截断，安全性优势就消失了。
我需要换一个完全不同的思路。
那天晚上我盯着屏幕发呆，突然意识到一个更深层次的问题。
哈希方案的冲突是概率问题，不是技术问题。 不管我用 MD5、SHA256 还是 MurmurHash，不管截取 6 位还是 8 位——只要 URL 足够多，冲突迟早会发生。这是数学规律，不是实现失误。
那有没有一种方案，永远不会冲突？
有。自增 ID。
落地思路
- 自增 ID 的唯一性不靠概率：1、2、3 天然互不相同，不需要任何冲突检测或重试。
- 哈希方案的冲突是概率问题：只要 URL 数量够多，冲突迟早会发生，换算法只是推迟它。
- 自增 ID 的代价有两个：短码长度随业务量增长，以及数字形态直接暴露业务规模。
- 所以选型不是「哈希 vs 自增」，而是「要不要让唯一性由概率来保证」。
自增 ID 简单粗暴：1、2、3……每个数字都是唯一的，永远不会撞车。就像排队取号——每个人拿到的号码一定不一样。不用算哈希，不用担心碰撞，不用搞什么加盐重试。
但它有一个致命的缺点：暴露业务量。 看到短码是 1000000，就知道你只有 100 万条链接。看到短码是 15，就知道你这个服务刚上线。竞争对手扫一眼就能推算出你的用户规模。这就像餐厅门口的取号机，看到前面排到 800 号，就知道今天生意不错。
而且纯数字的短码太长了。100 万是 7 位数，1 亿是 9 位数——一点都不”短”。
我把两种方案的优缺点摆在一起：
| 维度 | 哈希方案 | 自增 ID |
|---|---|---|
| 唯一性 | ❌ 有冲突风险 | ✅ 绝对唯一 |
| 短码长度 | ✅ 固定长度 | ❌ 随数量增长 |
| 业务量暴露 | ✅ 不暴露 | ❌ 直接暴露 |
| 分布式友好 | ✅ 各节点独立计算 | ❌ 需要协调 |
| 复杂度 | 中（需要冲突处理） | 低（但需要分布式 ID） |
两种方案各有各的坑。纯哈希会冲突，纯自增会暴露数据。我需要一个能兼顾两者优点的方案。
那天晚上快凌晨两点了，我终于想通了一件事——如果能用自增 ID 保证唯一性，再用一种高效的编码把数字”伪装”成看起来随机的字符串，不就两全其美了吗？
想了一晚上，我做了决定：用自增 ID 保证唯一性，用 Base62 编码让短码更短、更不可预测。
落地思路
- 决定拆成两半：唯一性交给自增 ID，紧凑性和「看起来随机」交给 Base62 编码。
- 编码后 100 万变成
4fcVwD这种 6 位字符串，比纯数字短，也看不出业务量。- 短码本身仍然要过数据库的唯一索引，那是最后一道防线，任何生成逻辑都不该绕过它。
- 兜底是去重：同一个长 URL 重复提交时返回已有短码，而不是再生成一个新的。
为什么选这个方案？
- 自增 ID 永远不会冲突——数学上绝对唯一，不用再担心碰撞
- Base62 编码让数字更短——1000000 变成
4fcVwD，6 个字符搞定 - 62 进制有 568 亿种组合——6 位足够用很久
- 看不出业务量——
4fcVwD比1000000难猜多了
这不是完美的方案——自增 ID 在分布式环境下需要额外处理——但至少它从根本上消除了哈希碰撞的噩梦。
做下决定的那一刻，我知道自己只是把问题往下推了一层。
Base62 只有 62 个字符（0-9, a-z, A-Z），为什么不用 64 个？为什么不用 36 个？为什么不用其他符号？
6 位 Base62 的空间是 568 亿，6 位 Base36 只有 21 亿，差了 27 倍。多出来的 26 个大写字母，让短码短了一大截。但多加 + 和 /（变成 Base64）呢？这两个字符在 URL 里有特殊含义，会引发编码问题。
背后的数学很讲究。 字符集的每一个选择，都在影响短码的长度、安全性和 URL 兼容性。
下一节，我需要把 Base62 的原理彻底搞清楚。
练习 1
为什么 MD5 适合短链接生成，但不适合密码存储？
解题思路：
这题要讲清同一个算法在不同场景下结论相反的原因，判据是需求：短链接要的是”快、确定、唯一”，密码存储要的是”慢、加盐、不可碰撞”。用需求去对照算法特性，而不是笼统说 MD5 好不好。
详细步骤：
MD5 适合短链接的原因：
- 快速计算：短链接需要实时生成，MD5 速度快
- 确定性：相同 URL 总是生成相同哈希，避免重复
- 安全性要求低：短链接不需要防破解，只需要唯一性
- 输出长度适中：128 位足够缩短后使用
MD5 不适合密码存储的原因：
- 已被破解：存在有效的碰撞攻击方法
- 计算太快：容易被暴力破解和彩虹表攻击
- 无盐值机制：相同密码产生相同哈希
- 专业攻击工具：存在大量 MD5 破解工具
密码存储应该使用 bcrypt、Argon2、PBKDF2 或 scrypt。这些算法故意设计得很慢，并支持盐值，能有效防止暴力破解。
最终答案：
MD5 适合短链接的原因有四点：计算快，短链接要实时生成；确定性好，相同 URL 总是生成相同哈希，可以用来去重；安全性要求低，短链接只需要唯一性、不需要防破解；输出长度 128 位足够取前缀使用。MD5 不适合密码存储的原因也正是这四点反过来：它已被破解，存在有效的碰撞攻击方法；计算太快，容易被暴力破解和彩虹表攻击；无盐值机制，相同密码产生相同哈希；市面上有大量现成的 MD5 破解工具。密码存储应该使用 bcrypt、Argon2、PBKDF2 或 scrypt，这些算法故意设计得很慢并支持盐值，能有效防止暴力破解。
练习 2
如果截取 MD5 哈希的前 6 位（16 进制），最多能表示多少个不同的短链接？什么时候冲突概率会超过 50%？
解题思路：
这题要用同一个方法（生日悖论）对比不同编码方案的碰撞天花板，结论才会显得可信：先算 16 进制的 6 位空间和 50% 阈值，再和 62 进制 6 位、8 位十六进制对比。
详细步骤：
最大组合数：
6 位十六进制，每位 16 种可能：
16^6 = 16 × 16 × 16 × 16 × 16 × 16 = 16,777,216 ≈ 1677 万50% 冲突概率的阈值（生日悖论估算）：
阈值 ≈ √(16^6 × ln2) ≈ √(16,777,216 × 0.693) ≈ √11,625,816 ≈ 3409也就是说，大约存 3400 条 URL 时，冲突概率就超过 50% 了。 这个数字比很多人想象的要小得多。
对比：
- 如果扩展到 8 位：16^8 ≈ 42.9 亿，50% 冲突阈值约 77,000 条
- 如果使用 62 进制 6 位：62^6 ≈ 568 亿，50% 冲突阈值约 280 万条
最终答案：
6 位十六进制每位有 16 种可能，组合数为 16 的 6 次方即 16,777,216，约 1677 万。按生日悖论估算 50% 冲突阈值约等于根号下 16 的 6 次方乘 ln2，约为 3409，也就是说大约存 3400 条 URL 时冲突概率就超过 50%——这个数字比很多人想象的要小得多。对比之下，如果扩展到 8 位十六进制，16 的 8 次方约 42.9 亿，50% 冲突阈值约 7.7 万条；如果使用 62 进制 6 位，62 的 6 次方约 568 亿，50% 冲突阈值约 280 万条。可见哈希空间每扩大一个数量级，可安全容纳的条数大约只提升到原来的 4 倍，而不是线性提升。
发现内容有问题？
告诉我们哪里需要改进。