hash - Google URL Shortener 如何在没有冲突的情况下生成 5 位哈希

Question

Google URL 缩短器如何生成 唯一五个字符的散列没有 碰撞。似乎肯定会有冲突，不同的 url 生成相同的哈希。

stackoverflow.com => http://goo.gl/LQysz

同样有趣的是，相同的 URL 每次生成完全不同的哈希:

stackoverflow.com => http://goo.gl/Dl7sz

所以，做一些数学计算，使用小写字符、大写字符和数字，组合总数为 62^5 = 916,132,832显然，碰撞必然会发生。

谷歌是如何做到这一点的？

Answer 1

他们有一个数据库，可以跟踪所有以前生成的 URL 和每个映射到的较长 URL。易于确保该表中不存在新生成的 URL。横向扩展有点棘手(它们肯定有多个服务器，因此每个服务器都需要分配一桶值，从中可以将其分发给用户)。如果他们达到生成 916,132,832 个 URL 的地步，他们只会添加另一个字符。