哈希冲突
上次短码冲突的事故让我心有余悸。两个完全不同的长链接，经过 MD5 哈希 + 截取 + Base62 编码，居然生成了同一个短码。用户点击后跳到了别人的页面——这种 bug 发生一次就够要命了。
我当时的第一反应是：换一个更好的哈希算法，或者把截取长度从 6 位加到 8 位，应该就没事了吧？
但直觉告诉我，这个问题没那么简单。我需要把哈希冲突这件事从头到尾搞清楚。万一将来服务需要做分布式部署，多台机器同时生成短码，冲突问题只会更复杂。
我打开浏览器，开始搜索。很快，一个令人不安的数学结论出现在我眼前。
我查到了一个叫生日悖论的数学结论，它让我意识到自己之前对冲突概率的估计错得离谱。
经典问题：一个房间里需要多少人，才有 50% 的概率出现两人生日相同？
直觉告诉我们，一年 365 天，怎么也得 180 个人以上吧？
答案是 23 人。
23 个人，只有 365 个可能值中的 23 个，就有 50% 的概率撞车。这完全违背直觉，但数学不会说谎。原理是这样的：
第 1 个人的生日不冲突概率： 365/365 = 100%
第 2 个人与前面不冲突概率： 364/365 ≈ 99.7%
第 3 个人与前面不冲突概率： 363/365 ≈ 99.5%
...
第 23 个人与前面不冲突概率： 343/365 ≈ 94.0%
23 个人全部不冲突的概率：
365/365 × 364/365 × 363/365 × ... × 343/365 ≈ 49.3%
至少有一对冲突的概率 = 1 - 49.3% = 50.7% ✅每一个新加入的人，都要和之前所有人比对的不是一对，而是一对一对地产生新的配对。23 个人两两配对有 23×22/2 = 253 对——远比想象中多。这就是冲突概率飙升的根源。
把同样的逻辑搬到短链接上：6 位 Base62 有 62^6 ≈ 568 亿种可能，看起来巨大无比。但如果用生日悖论的公式，50% 冲突阈值大约是 √(568亿 × ln2) ≈ 198 万。
也就是说——只需要存入不到 200 万条 URL，就有 50% 的概率出现冲突。568 亿的空间，才用了万分之零点三。
我不信邪，做了一次流程化整理算了一遍：
落地思路
- 算的是「n 条记录落进 d 个坑，至少撞一次」的概率，公式是
1 - Π(1 - i/d)，也就是生日悖论。- 取 d = 62^6 ≈ 568 亿，把 n 代进去就能得到每个量级对应的冲突概率。
- 概率随条数增长得很快：10 万条还是万分之一量级，1000 万条就逼近 0.1%，1 亿条到了 8%。
- 关键是这个概率和用什么哈希算法无关——MD5、SHA256、MurmurHash 截断后都是同一个 d。
数据清楚地告诉我：
- 10 万条：基本不会冲突，概率 0.000009%
- 100 万条：仍然很低，但已经开始出现非零概率
- 1000 万条：接近 0.1%，每一千次操作就有一次冲突
- 1 亿条：8%，几乎可以确定会发生
我的服务如果做大了，几百万条 URL 是完全有可能的。到那时冲突就不是”小概率事件”，而是”一定会发生的事故”。
更关键的是——这只是哈希方案的冲突概率。它和用什么哈希算法（MD5、SHA256、MurmurHash）无关，只取决于截取后的空间大小。
搞清楚问题的严重程度后，我系统地研究了所有可能的应对方案。
方案 A：增加短码长度
最直接的做法——从 6 位扩展到 7 位、8 位。
落地思路
- 做法很简单：把截取长度从 6 位加到 7 位、8 位，空间从 568 亿涨到 3.5 万亿。
- 代价是短码变长：原来
short.url/abc123是 6 位，加到 8 位就是short.url/abc12345。- 更要命的是它只推迟问题：8 位 Base62 的 50% 冲突阈值在 1.7 亿条量级，照样会撞。
- 所以它可以作为缓解手段，但不能当作唯一防线，数据库那边的唯一约束还得留着。
简单有效，但代价也很明显：短码变长了。从 short.url/abc123 变成 short.url/abc12345——虽然只多了两位，但作为”短链接”，每一厘米都很珍贵。而且它只是推迟了问题，并没有从根本上消除冲突。
方案 B：使用更好的哈希算法
MD5 的碰撞抗性确实不行。换 MurmurHash 呢？它是专门为哈希表设计的非加密哈希，分布更均匀，速度也更快。
落地思路
- 换成 MurmurHash 这类非加密哈希，确实能让分布更均匀、速度也更快。
- 但均匀不等于唯一：截取 6 位 Base62 只保留约 35.8 位信息，空间就那么大，冲突概率由截取长度决定。
- 所以判断一个哈希方案好不好，要看的是「截取后的空间」，不是「哈希本身有多强」。
- 兜底仍然是数据库唯一索引：分布再均匀的哈希也不能保证不重复，最终防线要留在存储层。
但问题在于——截断之后，任何哈希算法的优势都会被抹平。 截取 6 位 Base62，只保留了约 35.8 位的信息量。不管你用的是什么神级哈希，35.8 位就是 35.8 位，空间就那么大，冲突概率由截取长度决定，和算法无关。
更好的哈希只能让分布更均匀，但均匀分布不等于不冲突。均匀分布下的生日悖论冲突概率依然存在。
方案 C：自增 ID + Base62
这是我最终选择的路。
落地思路
- 做法是让自增 ID 代替哈希：ID 天然唯一，Base62 编码后 100 万是
4c92、1 亿是6LAzd。- 不需要任何冲突检测，也不需要加盐重试——短码生成这一步彻底没有失败分支。
- 短码长度取决于业务量而不是固定值：数量少的时候更短，数量涨上去自然会变长。
- 兜底是唯一索引仍要留着：万一将来把生成器换成别的（比如雪花 ID），那道防线还得在。
自增 ID 的核心优势是数学上绝对唯一——1、2、3……每个数字天然不同，不需要任何冲突检测。配合 Base62 编码后，100 万变成 4c92（4 位），1 亿变成 6LAzd（5 位），都比我之前用哈希截断的 6 位还短。
但它有两个弱点：
- 暴露业务量：短码是
4c92，反编码就知道你只有几万条链接。竞争对手一眼就能推算出你的规模。 - 单点瓶颈：分布式环境下，多台机器争抢同一个计数器是个麻烦事。
第一个问题我可以接受——Base62 编码后的短码看起来像随机字符串，外行人不会去反推。第二个问题……将来再说。
方案 D：分布式 ID（Snowflake）
如果将来服务做大，需要多台服务器同时生成短码，自增 ID 的单点问题就得解决。Twitter 的 Snowflake 方案是一个经典的答案。
┌──────────────────────────────────────────────────┐
│ 1 bit │ 41 bits │ 10 bits │ 12 bits │
│ 符号位 │ 时间戳 │ 机器 ID │ 序列号 │
│ (固定0) │ (毫秒级精度) │ (1024台) │ (4096/毫秒)│
└──────────────────────────────────────────────────┘每台机器有自己的 ID，时间戳保证全局有序，序列号保证同一毫秒内不重复。这样每台机器可以独立生成 ID，不需要中央协调，也不会冲突。
落地思路
- Snowflake 用「时间戳 + 机器 ID + 序列号」拼出一个 64 位整数，天然带机器维度，多台机器互不冲突。
- 转成 Base62 后大约 11 个字符，比 6 位长不少——唯一性换来的代价是短码变长。
- 它的价值在分布式：不需要中央协调，也不需要每次生成都走一次网络。
- 兜底是时钟回拨：时间戳一旦倒退就可能发出重复 ID，这一套必须自己处理。
Snowflake 生成的 ID 是 64 位整数，转成 Base62 后大约 11 个字符——比 6 位长了不少。但它在分布式环境下保证唯一性，这是自增 ID 做不到的。
方案对比
我把四种方案放在一起对比：
| 方案 | 冲突风险 | 短码长度 | 分布式支持 | 复杂度 |
|---|---|---|---|---|
| A. 增加长度 | 降低但仍有风险 | 变长 | ✅ 各节点独立 | 低 |
| B. 更好的哈希 | 取决于截取长度 | 不变 | ✅ 各节点独立 | 低 |
| C. 自增 ID | ✅ 绝对无冲突 | 随数量增长 | ❌ 单点瓶颈 | 低 |
| D. Snowflake | ✅ 绝对无冲突 | 固定较长 | ✅ 天然支持 | 中 |
没有银弹。每一种方案都在不同维度上做了取舍。
综合考虑，我选了自增 ID + Base62，原因很简单：
落地思路
- 选自增 ID + Base62，是因为唯一性由数学保证，不需要在业务层写任何冲突处理逻辑。
- 落库时短码走唯一索引，让数据库成为最后一道防线——即使生成逻辑出问题，也不会写出两条同短码的记录。
- 将来要做分布式，就把 ID 来源换成 Snowflake 或号段模式，短码生成这一层不用改。
- 兜底是去重查询仍然保留：同一个长 URL 重复创建时返回已有短码，而不是新建一条。
为什么是这个方案？三个理由：
- 简单可靠：自增 ID 天然唯一，不需要任何冲突检测或重试逻辑。流程越少，出错点越少。
- 足够短：Base62 编码后，前 568 亿条链接都在 6 位以内。我的服务不可能短时间内用完。
- 可演进：将来需要分布式，可以直接切换到 Snowflake 或数据库号段模式，短码生成逻辑不变。
我把哈希方案和自增 ID 的核心区别总结了一下：
| 维度 | 哈希方案 | 自增 ID + Base62 |
|---|---|---|
| 唯一性保证 | ❌ 概率性的，需要兜底 | ✅ 确定性的，数学保证 |
| 冲突处理 | 加盐重试 + 唯一索引 | 不需要 |
| 短码外观 | 看似随机 | 递增但 Base62 后不明显 |
| 分布式支持 | 各节点独立计算 | 需要协调（Snowflake 等） |
经过哈希算法的调研、Base62 编码的实现、冲突问题的深入分析，短码生成的逻辑终于尘埃落定。自增 ID + Base62，简单、可靠、够用。
但一个完整的问题一直悬在我心头：这些短码和长 URL 的映射关系，存在哪里？
我目前用的是 Python 字典——程序一重启，所有数据全没了。生产环境需要真正的数据库。但选什么数据库？SQLite？MySQL？Redis？每种选择的性能、可靠性和复杂度都完全不同。
更关键的是：如果短链接服务要做跳转，每次访问都要查一次数据库。SQLite 真的扛得住每秒几千次的查询吗？
练习 1
6 位 Base62 有 568 亿种组合，看起来很大。请用生日悖论公式计算：存入多少条 URL 时，冲突概率会超过 50%？
解题思路：
这题要传达的核心反直觉是：哈希冲突不是”空间快满了”才出现，而是在极早期就以很高概率出现。生日悖论的 50% 阈值公式把这件事量化出来，用占空间的比例对比就能看出威力。
详细步骤：
生日悖论的 50% 冲突阈值近似公式：
n ≈ √(2 × d × ln2)其中 d = 62^6 = 56,800,235,584
n ≈ √(2 × 56,800,235,584 × 0.693)
≈ √78,728,006,599
≈ 2,805,854大约 280 万条 URL 时，冲突概率就超过 50%。
这意味着 568 亿的空间才用了万分之零点五，就已经有一半的概率撞车了。这就是生日悖论的威力——冲突不是发生在空间快用完的时候，而是在极早期就出现了。
如果扩展到 7 位 Base62（约 3.5 万亿），50% 阈值约为 2200 万。8 位则约为 1.7 亿。
最终答案：
生日悖论的 50% 冲突阈值近似公式是 n 约等于根号下 2 乘 d 乘 ln2，其中 d 是哈希空间大小。取 d 等于 62 的 6 次方即 56,800,235,584，算得 n 约 2,805,854，也就是大约 280 万条 URL 时冲突概率就超过 50%。这意味着 568 亿的空间才用到万分之零点五，就已经有了一半的概率撞车——冲突不是发生在空间快用完的时候，而是在极早期就出现了，这就是生日悖论的威力。换成 7 位 Base62（约 3.5 万亿）时 50% 阈值约为 2200 万条，8 位则约为 1.7 亿条。
练习 2
设计一个完整的冲突处理流程：假设你坚持使用哈希方案（而非自增 ID），如何在生产环境中应对冲突？
解题思路：
冲突处理不能只靠”撞了就重试”这一招，要有层次：先在应用层预防（查重），再让数据库兜底（唯一索引），冲突了就有限重试并换盐，最后回落到一个必定可用的方案。每一层都要能独立救场。
详细步骤：
哈希方案的核心思路是：预防 → 检测 → 重试 → 兜底。
落地思路
- 顺序是「预防 → 检测 → 重试 → 兜底」：先查重、再靠唯一索引挡、冲突了重试、还不行才回落。
- 重试要换盐：同一个 URL 加同一个盐算出同一个哈希，必须换盐才会得到不同的截取值。
- 重试次数要设上限（比如 5 次），超过就说明这不是偶发冲突，而是哈希方案本身不适用。
- 兜底是回落到自增 ID：前面所有哈希路径都失败时，用自增 ID 一定能生成一个可用短码。
关键设计点：
- 去重查询：先查数据库，相同 URL 直接返回已有短码
- 数据库唯一索引：
short_code列必须建唯一索引，这是最后一道防线 - 有限重试：最多 5 次，避免极端情况下无限循环
- 兜底方案：哈希重试全失败，回退到自增 ID，保证一定能生成
这套流程保证了：正常情况下走哈希路径（快速），异常情况下有兜底（可靠）。
最终答案：
哈希方案的核心思路是”预防 → 检测 → 重试 → 兜底”。顺序是：先查重，相同 URL 直接返回已有短码；再靠数据库 short_code 列的唯一索引挡下，这是最后一道防线；冲突了就重试，但每次必须换盐，因为同一个 URL 加同一个盐会算出同一个哈希，不换盐拿到的还是同一个值；重试次数要设上限（比如 5 次），超过就说明这不是偶发冲突而是哈希方案本身不适用；兜底是回落到自增 ID，前面所有哈希路径都失败时用自增 ID 一定能生成可用短码。这样正常情况下走哈希路径（快），异常情况下有兜底（可靠）。
发现内容有问题？
告诉我们哪里需要改进。