代码之家 › 专栏 › 技术社区 › Sean McSomething

将数字序列转换为随机查找的ID?

random

Sean McSomething · 技术社区 · 15 年前

我正在开发一个应用程序,我需要在其中生成唯一的、非顺序的ID。我有一个限制条件,那就是它们必须由3位数字和2个字母组成(只有大约600K的ID)。考虑到我的ID池相对较小,我考虑简单地生成所有可能的ID,对它们进行洗牌并将它们放入数据库。因为在内部,我将有一个简单的、连续的、可使用的ID,很容易一次提取出一个ID,请确保我没有任何重复。

这似乎不是一个非常令人满意的解决方案。有没有人有比这种“抽奖”方法更有趣的方法从有限的池中生成唯一的ID?

5 回复 | 直到 11 年前

Timm 15 年前

这可以通过许多不同的方法来完成,这取决于您试图优化的内容(速度、内存使用等)。

ID模式=DDD C 1 C〔0〕

选项1(基本上类似于散列,类似于Zak):
1生成一个介于0和可能性数(676K)之间的随机数。
2-将数字转换为组合

    ddd = random / (26^2)
    c[0] = random % (26)
    c[1] = (random / 26) % 26

3-查询数据库是否存在ID并递增,直到找到空闲ID为止。

选项2(线性反馈移位寄存器,参见 wikipedia ):
1-随机数范围内的种子(0676K)。(请参阅下面为什么不能用“0”播种)
2-通过将以下内容应用于当前ID号,生成后续的随机数

    num = (num >> 1) ^ (-(num & 1u) & 0x90000u);

3-跳过大于范围的ID(即0xA50A0+)
4-将数字转换为ID格式(如上所述)
*您将需要保存最后生成的用于ID的编号,但不需要查询数据库来查看是否使用了该编号。由于LFSR的工作方式,此解决方案将枚举除[000 AA]之外的所有可能的ID。

[编辑]由于您的范围实际上大于您需要的范围,您可以在转换为ID之前减去1返回[000 aa]并使您的有效范围为(0,0xa50a0]

Zak 15 年前

您可以生成一个符合该标准的随机ID,执行一个db select来查看它是否已经存在,然后将它插入到一个db中,以注意它已经被“使用”。在这个方案的前25%的生命周期中(或大约150k个条目),生成新的随机ID应该比较快。不过,在这之后,它将花费越来越长的时间,您也可以预先填写表格来寻找免费ID。

Don Werve 15 年前

使用有限群。基本上,取一个32或64位的整数,找到一个与整数的最大值互质的大数字;称这个数字m。然后,对于所有整数n,n*m将得到一个唯一的数字,该数字有很多位数。

这样做的好处是,您不需要预先填充数据库,也不需要运行单独的select查询——您可以在一个insert语句中通过 n 只是一个自动增量,并有一个单独的ID列,默认为n*m。

James Black 15 年前

根据您所定义的顺序,您可以在字母上选择一个特定的起始点,例如“a a”,然后循环使用三个数字,因此: 01AA 02AA 00 3AA

一旦你到达ZZ,然后增加数字部分。

rjmunro 11 年前

可以使用模块化算法生成ID。选择一个与676000互质的数字作为种子。 id 是表的标准递增ID。然后您需要以下伪代码:

uidNo = (id * seed) % 676000
digits = uidNo / 676
char1 = uidNo % 26
char2 = (uidNo / 26) % 26
uidCode = str(digits) + chr(char1+65) + chr(char2+65)

如果一个用户有多个连续发出的ID,他们可以猜测算法和种子,并按顺序生成所有ID。这可能意味着算法对于您的用例来说不够安全。