用于唯一随机生成ID的良好算法

Question

我需要生成一个随机ID,字母数字,6个字符,作为短链接服务的ID.

目前,我生成一个随机的6个字符的代码,在数据库中查找它是否以前使用过,如果有,请重复此过程.我需要它对所有36 ^ 6种组合都是独一无二的.随着系统的发展,其性能越差.

是否有已知的良好方法可以最小化命中数据库,在全局范围内保留状态,并且查找时间不会超过100毫秒？

感谢任何帮助

Answer 1

使用序列号,这样您就不必在数据库中搜索密钥是否已存在.您只需跟踪到目前为止分配的最大数量.

要使此序列ID为字母数字,请将其转换为base 36.

如果你不喜欢分配的第一个ID看起来像000000,000001... 00000z,000010...,你可以使用数学技巧:内部保留顺序数字ID,但是对于外部表示对于用户可见,将它(mod 36 ^ 6)乘以小于36 ^ 6-1的大素数 - 1679979167将是一个不错的选择 - 在转换为基数36之前.这将使您的ID对用户显得随机,即使他们真的不是.

这是一个带输出的python示例:

def baseN(num,b,numerals="0123456789abcdefghijklmnopqrstuvwxyz"):
    return ((num == 0) and numerals[0]) or (baseN(num // b, b, numerals).lstrip(numerals[0]) + numerals[num % b])

for internalID in range(1,200):
    mangled = (internalID*1679979167)%(36**6)
    print internalID, mangled, baseN(mangled,36)

(baseN代码是来自这里的 jellyfishtree )

1 1679979167 rs7s7z
2 1183175998 jkfkfy
3 686372829 bcncnx
4 189569660 34v4vw
5 1869548827 ux2x3v
6 1372745658 mpapbu
7 875942489 ehihjt
8 379139320 69q9rs
9 2059118487 y1y1zr
10 1562315318 pu5u7q
11 1065512149 hmdmfp
12 568708980 9eleno

Answer 2

这个问题有一个众所周知的解决方案:

http://en.wikipedia.org/wiki/Linear_congruential_generator

只需用你的LCG生成下一个随机数,然后将其转换为base 36并写入相应的伪随机数字.

祝好运!