8 字符随机代码

Question

我已经回答了一些类似问题的答案，但找不到我想要的东西。

有没有一种更有效的方法来生成 8 个字符的唯一 ID（基数 36 (0-9A-Z)），而不是生成唯一 ID 并查询数据库以查看它是否已存在并重复，直到获得尚未存在的唯一 ID。用过的？

我发现的其他解决方案使用时间，但这可能太容易猜测，并且在分布式系统中可能效果不佳。将这些 ID 视为促销代码。

Answer 1

一种选择是反过来做：每当需要时在数据库中生成大量它们，然后在需要时从数据库中获取单个，或者为您的特定进程保留一大堆它们（即在数据库中将它们标记为“可能使用”）然后从内存中将它们分配出去。

Answer 2

我质疑你的“低效”方法实际上是低效的。考虑一下：

• 有 36^8 == 2,821,109,907,456（2.8 万亿）种可能的 ID。
• 如果您有 N 个现有 ID，则随机生成的新 ID 发生冲突的几率约为 2.8 万亿分之 N。
• 除非 N 达到数千亿，否则“生成一个唯一 ID 并查询数据库以查看它是否已存在”算法几乎总是会在一个周期内终止。

通过仔细的设计，您应该能够在一个数据库请求中生成一个有保证的唯一 ID，几乎在任何时候......除非您有大量的现有 ID。 （如果这样做，只需在 ID 中添加另外几个字符，问题就会再次消失。）

如果您愿意，可以通过批量生成 ID 将数据库操作的平均数量减少到每个 ID 一次以下，但它们是潜在的复杂性，特别是当您需要记录实际使用的 ID 数量时。

但是，如果您最多有 150,000 个 ID（我假设是在很长一段时间内生成的），那么批量创建 ID 就不值得了……除非您正在进行批量上传操作。

Answer 3

不幸的是，8基36位数字有点小。只有 200 万个可能的 ID，因此如果您随机生成 140 万个，则发生碰撞的可能性大约为一半。

您可以使用具有较大周期的 PRNG，并通过某种双射将其当前状态映射到您的 ID 空间。 41 位 LFSR 并非无法破解，但如果您要保护的东西不是那么有价值，则可能还不错。通过为不同的节点提供不同的位置来启动循环，您可以进行一定程度的分发，而无需始终访问数据库。

当然，任何此类确定性方法的问题在于，一旦被破坏，它就完全被破坏了，您将无法再信任任何 ID。因此，从数据库中分发数字可能是一种可行的方法，并通过以一千个或其他方式分发它们来进行分发。

如果您有更大的 ID 空间，那么您可以使用更安全的技术，例如 ID 可以包含用于识别源的内容、该源的递增序列号以及使用源唯一密钥的 HMAC。

Answer 4

如果只有一个 ID 源（即：您不需要协调不同机器上的多个独立源），您可以执行以下操作：

• 计算一个数字可能具有的最大位数，以便它不会不超过 0-9A-Z 8 个符号字符串中包含的信息。这将是 floor(log2(36^8)) = 41 位。

• 让计数器（41 位）从零开始

• 对于每个 ID 请求返回 transform(counter++)

transform 函数必须是双射的，并且可以是以下操作的任意长序列（当计算模2^41时，它们本身都是双射的）：

• 具有固定值的异
• 或左旋转或者通过固定值
• 对位进行重新排序通过固定映射（上面旋转的概括）
• 添加或减去固定值

当您完成后，您只需要另一个函数encode(number)将数字转换为 base36。

Answer 5

我曾经使用 C++ 解决了一个类似的问题，涉及较少数量的可能 ID，但考虑一些方法来扩展它可能会很有用。基本上，我为所有可能的 ID 创建了一个大位图，然后通过测试其正确的位来查找某个 ID 是否正在使用。

为了最大限度地减少 RAM 需求，我将位图存储在原始二进制文件中，并使用随机访问文件 I/O 来查找包含我需要检查和/或设置的相应位的字节。

更大的 ID 空间将需要 328 GB 的位图，这可能是不可能的。另一方面，已使用 ID 的 Python 集 可能是可以接受的，具体取决于您认为最终可能实际使用的 ID 数量。其他替代方案可能是某种稀疏文件或稀疏矩阵技术，例如稀疏文件 ="http://docs.scipy.org/doc/scipy/reference/sparse.html" rel="nofollow">scipy.sparse。

希望这有帮助。

Answer 6

下面是一些用于生成随机、base36 ID 的 python 代码。

import random

def base36encode(number, alphabet='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'):
    '''
    Convert positive integer to a base36 string.

    Source: http://en.wikipedia.org/wiki/Base_36#Python_Conversion_Code
    '''
    if not isinstance(number, (int, long)):
        raise TypeError('number must be an integer')

    # Special case for zero
    if number == 0:
        return '0'

    base36 = ''

    sign   = ""
    if number < 0:
        sign  ='-'
        number=-number

    while number != 0:
        number, i = divmod(number, len(alphabet))
        base36 = alphabet[i] + base36

    return sign + base36

def generateID(length=8):
    '''Generates a base36 ID.'''

    random.seed()
    id = base36encode(random.randint(0, (36**length)-1))

    # append 0s to ensure desired length
    while len(id) < length:
        id = '0' + id

    return id

def generateMultipleIDs(n):
    '''Generate n number of unique, base36 IDs.'''

    output = set()

    while len(output) < n:
        output.add(generateID())

    return output

Answer 7

我做了类似生成激活码的操作：一次性使用的 8 个字母的小写字符串。它们旨在生成后短时间内使用（通常在几分钟内，但可能不会长达一周），但必须是唯一的。当它们被使用后，它们就会从数据库中删除。

我只是生成一个值并查看它是否在数据库中使用。目前这种方法有效，因为数据库中没有大量未使用的代码，但即使已经为您提供了代码，仍然不容易猜测。

至于生成代码：

def _generate_code(self, length):
    random.seed()
    candidates = string.lowercase[:26]
    result = ""
    for i in range(length):
        result += random.choice(candidates)
    return result

Answer 8

它需要加密安全吗？

如果不是，则 pc(n) = a + bn（其中 b 相对于 36^8 是质数）即可。使用字节数组。

foo(int n, byte[] a, byte[] b) {
  byte[] r = new byte[8];
  int carry=0;
  for(int i = 0; i<8;i++) {
    int x = carry + a[i] + n*b[i];
    r[i] = x % 36;
    carry = x / 36;      
  }
}