算法：随机唯一字符串

Question

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

1. 它应该是一个唯一的字符串；
2. 字符串长度应为8个字符；
3. 它应该包含2个数字；
4. 所有符号（非数字字符）应为大写。

在生成后，我将把它们存储在数据库中（它们将被分配给其他实体）。

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

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

我对该算法的担忧是，它不能保证在有很多值的数据库中以有限的时间内得出结果。

问题：您能否请提供建议，以改进此算法以更具确定性？

谢谢。

- Budda

---

为什么需要随机性？为什么不能使用顺序字符串？ - Anon.

这很难同时保持高斯分布。 - orlp

@nightcracker：你指的是均匀分布，而不是高斯分布。 - Jason S

我展示了大约240亿个可能的组合。由于生日悖论，你将在大约其平方根处开始遇到碰撞问题，即约为150,000。 - David Thornley

即使您用尽了地址空间的一半，平均只需要重试1.5次就能找到唯一的ID。我认为，只要您能保证不会耗尽超过90％的地址空间，那么除了随机生成和测试ID之外，做任何其他事情都不值得额外的复杂性。话虽如此，使用递增ID或适当的UUID将更简单、更健壮。 - Nick Johnson

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个随机字母放在剩余的位置。

对于两个不同的整数，有28种可能性（(8*8-8)/2），字母有26⁶种可能性，数字有100种可能性，有效组合的总数为N_comb=864964172800=8.64 x 10¹¹。

---

编辑：如果您想避免使用数据库进行存储，但仍然保证字符串的唯一性和密码安全性，则最好使用从0到N_max <= N_comb之间的计数器的密码随机双射映射到可能输出字符串的空间子集。(双射意味着输出字符串与输入计数器之间存在一一对应关系。)

这可以通过Feistel网络实现，它们通常用于哈希函数和对称加密(包括AES)中。您可能希望选择N_max=2³⁹，这是最大的2的幂，小于或等于N_comb，并使用一个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的39次方/26的6次方/100 = 17.796...）。将此数字映射到两个唯一的数字位置（可能最容易使用查找表，因为我们只讨论28种可能性。如果有更多，请使用Floyd算法生成唯一排列，并使用模数+整数除法的可变基技术而不是生成随机数）。
5. 按照上面的随机方法，但使用此算法生成的数字。

或者，使用40位数字，如果您的Feistel网络输出> N_comb，则增加计数器并重试。这样可以覆盖整个字符串空间，但会拒绝无效的数字并必须重新执行算法。（但您不需要数据库来执行此操作。）

但是，除非你知道自己在做什么，否则不要涉足其中。

- Jason S

---

你假设他能够在字符串中分配数字，但他已经说明该字符串需要以两个数字开头，后面跟着6个“符号”。 - Kirk Broadhurst

@Kirk：不，他没有这么说。他说他的字符串需要包含两个数字，并且他的意图是将两个数字和6个符号相连。并没有清楚地描述这是因为这两个数字需要首先出现，还是它们可以出现在任何位置，但他把它们放在了第一位，因为这样做很容易。 - Jason S

（就此而言，他并没有明确表示连接是数字后跟字母，还是字母后跟数字，或者其他什么情况。） - Jason S

抱歉，我改正一下，可能是我看错了或者只是做出了假设。 - Kirk Broadhurst

Answer 2

这些是用户密码吗？如果是，你需要考虑以下几点：

1. 必须避免使用0/O和I/1，它们很容易被误认为是同一个字符。
2. 必须避免过多连续字母，可能会拼出粗鄙的单词。

至于第二点，你可以使用LLNLLNLL作为密码模式（L表示字母，N表示数字），以避免这个问题。

如果你需要从25亿个密码中获取100万个密码，那么你肯定会在数据库中遇到冲突，因此你需要优雅地处理这些冲突。但是，如果你的随机数生成器足够强大，简单重试就足够了。

- TonyK

---

请注意，如果您花太多时间尝试避免粗鲁的话语，不要像这样结束：http://thedailywtf.com/Articles/The-Automated-Curse-Generator.aspx - biziclop

密码通常不必唯一。 “抱歉，已存在使用该密码的用户” :) - Nikita Rybak

登录 - Budda

@Budda：所以你必须小心你生成的内容。 - TonyK

Answer 3

我认为你的ID数量在数万个范围内是安全的，即使超过这个数量，你也很可能没问题。

如果你想要一些确定性，你可以在一定次数的失败后强制更改密码。比如说，在50次失败后，你可以随机选择一个密码，并将其中一部分加1，直到找到一个可用的密码。

不过我敢打赌，在你的有生之年里，你永远不会看到这个额外功能被启用 :)

- Blindy

---

多少钱？Budda认为需要一百万个字符串，从250万个集合中选择。这不是一个很大的安全保障！ - TonyK

好吧，我开始写的时候那不是这样的 :) - Blindy

佛陀写的是：“10^2*25^6 = 2 441 406 250，几乎是2.5M”。这里有两个错误：（i）应该是26^6；（ii）2 441 406 250几乎是25亿。所以我撤回我的评论 :-) - TonyK

是的，我犯了错误，应该是十亿。 - Budda

Answer 4

首先，您的需求列表并未说明字符串必须是随机的，因此您可以考虑使用数据库索引等其他方法。

如果“随机”是一个要求，您可以进行一些改进。

1. 将字符串作为数字存储在数据库中。不确定这样做能够提高多少性能。
2. 根本不存储已使用的字符串。您可以采用上述“索引”方法，但以看似随机的方式将整数转换为字符串（例如，采用位移操作）。没有太多研究，没有人会注意到模式。

例如，如果我们有序列1、2、3、4、...并且使用循环二进制右移1位，它将变成4、1、5、2、...（假设我们只有3位）它不一定是一个位移，它可以是排列或任何其他“随机化”。

- Nikita Rybak

Answer 5

以另一种方式进行：生成一个大的随机数，然后将其拆分以获取单个字符。

 long bigrandom = ...;
 int firstDigit = bigRandom % 10;
 int secondDigit = ( bigrandom / 10 ) % 10;

等等。

然后，你只需要在数据库中存储随机数而不是字符串。由于字符串和数字之间存在一对一的关系，因此这并没有什么区别。

然而，当你尝试插入一个新值时，如果它已经在数据库中，你可以很容易地找到比最初生成的数字大的最小未分配数字，并使用那个数字代替你生成的数字。

通过这种方法，你可以保证相对快速地找到一个可用的代码，即使大多数代码已经被分配。

- biziclop

Answer 6

你的方法存在问题，显然在你的记录较少时，很少发生冲突。但是随着你的记录数量增加，发生冲突的可能性会增加，直到出现冲突的概率超过50%。最终你将在获得有效结果之前遭受多次冲突的打击。每一次都需要进行表扫描来确定代码是否有效，整个过程变得混乱不堪。 最简单的解决方案是预先计算你的代码。

从第一个代码00AAAA开始递增生成00AAAB、00AAAC...99ZZZZ并以随机顺序插入表中。当你需要一个新代码时，从表中检索未使用的顶部记录（然后标记为已使用）。正如上面所指出的那样，这不是一个庞大的表，只有几百万条记录。

• 你不需要为每个用户计算任何随机数字和字符串。
• 你不需要检查是否已经使用了任何东西，只要获取下一个可用的即可。
• 没有发生冲突的多重可能性。

如果你需要更多的“代码”，只需生成更多的“随机”字符串并附加到表中即可。

- Kirk Broadhurst

Answer 7

我在你的需求中没有看到任何要求字符串必须是随机的。你可以像下面的伪代码一样做：

for letters in ( 'AAAAAA' .. 'ZZZZZZ' ) {
  for numbers in ( 00 .. 99 ) {
    string = letters + numbers
  }
}

这将创建一个唯一的字符串，长度为八个字符，其中包含两个数字和六个大写字母。

如果您需要随机生成的字符串，则需要保留某种记录以跟踪先前生成的字符串，因此您需要访问数据库（或将它们全部保存在内存中，或将它们写入文本文件）并检查该列表。

- CanSpice