10

当用户在我的系统中添加新项目时，我想为该项目生成一个唯一的非递增伪随机 7 位代码。创建的项目数将仅数以千计（<10,000）。

因为它必须是唯一的并且没有两个项目具有相同的信息，所以我可以使用哈希，但它需要是他们可以与其他人共享的代码 - 因此是 7 位数字。

我最初的想法只是循环生成一个随机数，检查它是否尚未使用，如果是，请冲洗并重复。考虑到碰撞的可能性很小，我认为这是一个合理的解决方案。

对这个问题的回答建议生成所有未使用数字的列表并将它们改组。我可能可以在数据库中保留这样的列表，但我们正在谈论 10,000,000 条相对不常见的条目。

有没有人有更好的方法？

4

11 回答 11

15

选择一个 7 位素数A和一个大素数B，然后

int nth_unique_7_digit_code(int n) {
    return (n * B) % A;
}

由此生成的所有唯一代码的计数将是A。

如果你想更“安全”，做pow(some_prime_number, n) % A，即

static int current_code = B;
int get_next_unique_code() {
   current_code = (B * current_code) % A;
   return current_code;
}
于 2010-02-11T15:15:51.487 回答
5

您可以使用递增的 ID，然后在某个固定键上对其进行异或。

const int XORCode = 12345;

private int Encode(int id)
{
    return id^XORCode;
}

private int Decode(int code)
{
    return code^XORCode;
}
于 2010-02-11T15:10:51.237 回答
4

老实说，如果您只想生成几千个 7 位代码，而将有 1000 万个不同的代码可用，我认为只生成一个随机代码并检查碰撞就足够了。

在最坏的情况下，第一次碰撞发生碰撞的可能性大约是千分之一，而仅仅生成一个新的 7 位代码并再次检查碰撞的计算量将远小于保持一个字典或类似的解决方案。

使用 GUID 而不是 harryovers 建议的 7 位代码当然也可以，但当然 GUID 对于您的用户来说会稍微难以记住。

于 2010-02-11T15:08:44.327 回答
2

我建议使用 guid 而不是 7 位代码，因为它会更加独特，而且您不必担心生成它们，因为 .NET 会为您执行此操作。

于 2010-02-11T15:05:42.827 回答
2

“唯一” ID 的所有解决方案都必须在某个地方有一个数据库：一个包含已使用 ID 的数据库，或者一个包含空闲 ID 的数据库。正如您所注意到的，具有免费 ID 的数据库会非常大，因此人们通常会使用“使用过的 ID”数据库并检查冲突。

也就是说，一些数据库提供了一个“随机 ID”生成器/序列，它已经以随机顺序返回了一个范围内的 ID。

这通过使用一个随机数生成器来工作，该生成器可以创建一个范围内的所有数字而不会重复自身以及您可以将其状态保存在某处的功能。所以你要做的就是运行一次生成器，使用 ID 并保存新的状态。对于下一次运行，您加载状态并将生成器重置为最后一个状态以获取下一个随机 ID。

于 2010-02-11T15:09:13.463 回答
2

我假设你会有一张生成的表格。在这种情况下，我认为选择随机数并根据数据库检查它们没有问题，但我不会单独这样做。生成它们很便宜，相对而言，执行数据库查询是昂贵的。我会一次生成 100 或 1,000 个，然后询问数据库其中存在哪些。打赌你大部分时间都不需要做两次。

于 2010-02-11T15:13:25.343 回答
2

您有 <10.000 个项目，因此您只需要 4 位数字即可为所有项目存储一个唯一编号。由于您有 7 位数字，因此您还有 3 位数字。

如果将 4 位的唯一序列号与 3 位的随机数结合起来，您将是唯一且随机的。您生成的每个新 ID 都会增加序列号。

您可以按任何顺序附加它们，或混合它们。

seq = abcd, rnd = ABC

您可以创建以下 ID：

  • abcdABC
  • ABCabcd
  • abbccd

如果您只使用一种混合算法，您将拥有唯一的数字，看起来是随机的。

于 2010-02-11T15:48:22.950 回答
1

我会尝试使用 LFSR（线性反馈移位寄存器）代码非常简单，您可以在任何地方找到示例，即维基百科，即使它不是加密安全的，它看起来也很随机。此外，由于它主要使用移位操作，因此实施将非常快。

于 2010-02-11T15:50:53.373 回答
0

数据库中只有数千个项目，您最初的想法似乎是合理的。在数万个项目的排序（索引）列表中检查值的存在只需要一些数据获取和比较。

预先生成列表听起来不是一个好主意，因为您将存储超出必要的数量，或者您将不得不处理它们用完的问题。

于 2010-02-11T15:11:52.633 回答
0

命中的概率非常低。
例如 - 您有 10^4 个用户和 10^7 个可能的 ID。
您连续 10 次选择使用 ID 的概率现在是 10^-30。
这种机会低于任何人一生中的一次。

于 2010-02-11T15:19:05.987 回答
0

好吧，您可以要求用户选择他们自己的 7 位数字，并根据现有数字的数量（您会在它们用完时存储）进行验证，但我怀疑您会过滤很多 1234567、7654321 , 9999999, 7777777 类型的响应，可能需要一些正则表达式来实现过滤，此外，您必须警告用户不要使用此类序列，以免产生糟糕的、重复的用户输入体验。

于 2010-02-11T16:02:24.793 回答