21

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

目前，我生成一个随机的6字符代码，在db中查找它是否曾经使用过，如果有，则重复该过程。我需要它对于所有 36^6 组合都是唯一的。随着系统的增长，它的性能越差。

是否有已知的好方法可以最大限度地减少对数据库的访问，全局保留状态，并且查找时间不会超过 100 毫秒？

感谢任何帮助

4

2 回答 2

22

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

要使此顺序 ID 为字母数字，请将其转换为基数 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
于 2013-10-06T00:17:29.760 回答
10

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

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

只需使用您的 LCG 生成下一个随机数，然后将其转换为基数 36 并写入相应的伪随机字符串。

祝你好运！

于 2013-10-06T00:30:20.757 回答