算法:随机唯一字符串

Question

我需要生成满足以下要求的字符串:

1. 它应该是一个独特的字符串;
2. 字符串长度应为8个字符;
3. 它应该包含2位数字;
4. 所有符号(非数字字符)应为大写.

我会在生成后将它们存储在数据库中(它们将被分配给其他实体).

我的意图是做这样的事情:

1. 生成从0到9的2个随机值 - 它们将用于字符串中的数字;
2. 从0到25生成6个随机值并将它们添加到64个 - 它们将用作6个符号;
3. 将所有内容连接成一个字符串;
4. 检查数据库中是否已存在该字符串; 如果不重复.

我对该算法的关注是它不保证有限时间内的结果(如果数据库中已经有很多值).

问题:您能否就如何改进此算法提供更具确定性的建议？

谢谢.

Answer 1

1. 它应该是唯一的字符串;
2. 字符串长度应为8个字符;
3. 它应该包含2位数字;
4. 所有符号(非数字字符) - 应为大写.

假设:

• 要求#2和#3是准确的(恰好是8个字符,正好是2个数字),而不是最小值
• 要求#4中的"符号"是26个大写字母A到Z.
• 你想要一个均匀分布的随机字符串

那么你提出的方法有两个问题.一个是字母A - Z是ASCII 65 - 90,而不是64 - 89.另一个是它不会在可能的字符串空间内均匀分布数字.这可以通过执行以下操作来解决:

1. 生成0到7之间的两个不同的整数,并对它们进行排序.
2. 生成从0到9的2个随机数.
3. 从A到Z生成6个随机字母.
4. 在步骤#1中使用两个不同的整数作为位置,并将2个数字放在这些位置.
5. 将6个随机字母放在剩余的位置.

两个不同的整数((8*8 - 8个重复)/ 2个排序)有28种可能性,字母有26 ^6种可能性,数字有100种可能性,有效组合的总数为N _梳 = 864964172800 = 8.64 x 10 ¹¹.

编辑:如果你想避免数据库存储,但仍然保证字符串的唯一性并使它们具有加密安全性,你最好的选择是从0到N _最大的计数器加密随机双射<= N _梳到一个子集可能的输出字符串的空间.(Bijection意味着输出字符串和输入计数器之间存在一对一的对应关系.)

这可以通过Feistel网络实现,Feistel网络通常用于散列函数和对称密码术(包括AES).您可能想要选择N _max = 2 ³⁹这是2 <= N _梳的最大功率,并使用39位Feistel网络,使用您保密的常量密钥.然后,您将计数器插入Feistel网络,然后输出另一个39位数字X,然后将其转换为相应的字符串,如下所示:

1. 重复以下步骤6次:
2. 取X mod 26,生成大写字母,并设置X = X/26.
3. 取X mod 100生成两位数,然后设置X = X/100.
4. X现在将是介于0和17包容(2 ³⁹ /26 ⁶ /100 = 17.796 ...).将此数字映射到两个唯一的数字位置(可能最容易使用查找表,因为我们只讨论了28种可能性.如果你有更多,使用Floyd的算法生成唯一的排列,并使用mod + integer的变量基技术划分而不是生成随机数).
5. 按照上面的随机方法,但使用此算法生成的数字.

或者,使用40位数字,如果Feistel网络的输出> N _梳,则递增计数器并再试一次.这将覆盖整个字符串空间,代价是拒绝无效数字并且必须重新执行算法.(但是您不需要数据库来执行此操作.)

但除非你知道你在做什么,否则这不是要进入的.