Google URL缩短器如何生成没有冲突的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.很容易确保该表中不存在新生成的URL.扩展有点棘手(它们肯定有多个服务器,因此每个服务器都需要分配一堆值,以便向用户提供).如果它们达到了生成916,132,832个URL的程度,那么它们只会添加另一个字符.