Python 中的短唯一十六进制字符串

Question

我需要在 Python 3 中生成满足以下要求的唯一十六进制字符串：

它应该包含 6 个字符
它不应该只包含数字。必须至少有一个字符。
这些生成的字符串应该是随机的。它们不应以任何顺序排列。
应该有最小的冲突概率

我考虑过uuid4()。但问题是它生成的字符串包含太多字符，并且生成的字符串的任何子字符串在某些时候都可以包含所有数字（即没有字符）。

还有其他方法可以满足这个条件吗？提前致谢！

编辑

我们可以使用例如 SHA-1 的哈希来满足上述要求吗？

Answer 1

注意：更新了十六进制唯一字符串的答案。早些时候我假设为字母数字字符串。

您可以使用 uuid 和 random 库创建您自己的独特函数

>>> import uuid
>>> import random
# Step 1: Slice uuid with 5 i.e. new_id = str(uuid.uuid4())[:5] 
# Step 2: Convert string to list of char i.e. new_id = list(new_id)
>>> uniqueval = list(str(uuid.uuid4())[:5])
# uniqueval = ['f', '4', '4', '4', '5']

# Step 3: Generate random number between 0-4 to insert new char i.e.
#         random.randint(0, 4)
# Step 4: Get random char between a-f (for Hexadecimal char) i.e.
#         chr(random.randint(ord('a'), ord('f')))
# Step 5: Insert random char to random index
>>> uniqueval.insert(random.randint(0, 4), chr(random.randint(ord('a'), ord('f'))))
# uniqueval = ['f', '4', '4', '4', 'f', '5']

# Step 6: Join the list
>>> uniqueval = ''.join(uniqueval)
# uniqueval = 'f444f5'

Answer 2

这是一种从所有允许的字符串中均匀采样的简单方法。统一采样使冲突尽可能少，而不是保留先前密钥的日志或使用基于计数器的哈希（见下文）。

import random
digits = '0123456789'
letters = 'abcdef'
all_chars = digits + letters
length = 6

while True:

   val = ''.join(random.choice(all_chars) for i in range(length))

   # The following line might be faster if you only want hex digits.
   # It makes a long int with 24 random bits, converts it to hex,
   # drops '0x' from the start and 'L' from the end, then pads
   # with zeros up to six places if needed
   # val = hex(random.getrandbits(4*length))[2:-1].zfill(length)

   # test whether it contains at least one letter
   if not val.isdigit():
       break

# now val is a suitable string
print val
# 5d1d81

或者，这里有一种更复杂的方法，它也统一采样，但不使用任何开放式循环：

import random, bisect
digits = '0123456789'
letters = 'abcdef'
all_chars = digits + letters
length = 6

# find how many valid strings there are with their first letter in position i
pos_weights = [10**i * 6 * 16**(length-1-i) for i in range(length)]
pos_c_weights = [sum(pos_weights[0:i+1]) for i in range(length)]

# choose a random slot among all the allowed strings
r = random.randint(0, pos_c_weights[-1])

# find the position for the first letter in the string
first_letter = bisect.bisect_left(pos_c_weights, r)

# generate a random string matching this pattern
val = ''.join(
    [random.choice(digits) for i in range(first_letter)]
    + [random.choice(letters)]
    + [random.choice(all_chars) for i in range(first_letter + 1, length)]
)

# now val is a suitable string
print val
# 4a99f0

最后，这里有一个更复杂的方法，它使用随机数 r 直接索引到整个允许值范围，即将 0-15,777,216 范围内的任何数字转换为合适的十六进制字符串。这可以用来完全避免冲突（在下面详细讨论）。

import random, bisect
digits = '0123456789'
letters = 'abcdef'
all_chars = digits + letters
length = 6

# find how many valid strings there are with their first letter in position i
pos_weights = [10**i * 6 * 16**(length-1-i) for i in range(length)]
pos_c_weights = [sum(pos_weights[0:i+1]) for i in range(length + 1)]

# choose a random slot among all the allowed strings
r = random.randint(0, pos_c_weights[-1])

# find the position for the first letter in the string
first_letter = bisect.bisect_left(pos_c_weights, r) - 1

# choose the corresponding string from among all that fit this pattern
offset = r - pos_c_weights[first_letter]
val = ''
# convert the offset to a collection of indexes within the allowed strings 
# the space of allowed strings has dimensions
# 10 x 10 x ... (for digits) x 6 (for first letter) x 16 x 16 x ... (for later chars)
# so we can index across it by dividing into appropriate-sized slices
for i in range(length):
    if i < first_letter:
        offset, v = divmod(offset, 10)
        val += digits[v]
    elif i == first_letter:
        offset, v = divmod(offset, 6)
        val += letters[v]
    else:
        offset, v = divmod(offset, 16)
        val += all_chars[v]

# now val is a suitable string
print val
# eb3493

均匀采样

我在上面提到过，这个样本 均匀地 跨越所有允许的字符串。这里的其他一些答案完全随机选择 5 个字符，然后在随机位置强制将一个字母放入字符串中。这种方法会产生比随机得到的更多的包含多个字母的字符串。例如，如果为前 5 个插槽选择了字母，则该方法总是生成 6 个字母的字符串；然而，在这种情况下，第六个选择实际上应该只有 6/16 的机会是字母。仅当前 5 个槽位是数字时，才能通过将字母强制放入第六个槽位来解决这些方法。在这种情况下，所有 5 位字符串将自动转换为 5 位数字加 1 个字母，从而产生过多的 5 位字符串。使用均匀采样，如果前 5 个字符是数字，应该有 10/16 的机会完全拒绝该字符串。

这里有一些例子可以说明这些抽样问题。假设你有一个更简单的问题：你想要一个由两个二进制数字组成的字符串，规则是其中至少一个必须是 1。如果你以相同的概率产生 01、10 或 11，那么冲突将是最罕见的。您可以通过为每个插槽选择随机位，然后丢弃 00（类似于我上面的方法）来做到这一点。

但假设您改为遵循此规则：做出两个随机的二元选择。第一个选择将按原样在字符串中使用。第二个选择将决定额外插入 1 的位置。这类似于此处其他答案使用的方法。那么您将得到以下可能的结果，其中前两列代表两个二元选择：

0 0 -> 10
0 1 -> 01
1 0 -> 11
1 1 -> 11

这种方法有 0.5 的机会产生 11，或者 0.25 产生 01 或 10，因此它会增加 11 个结果之间发生冲突的风险。

您可以尝试如下改进：随机选择三个二进制选项。第一个选择将按原样在字符串中使用。如果第一个选择是 0，则第二个选择将转换为 1；否则它将按原样添加到字符串中。第三个选择将决定第二个选择插入的位置。那么你有以下可能的结果：

0 0 0 -> 10 (second choice converted to 1)
0 0 1 -> 01 (second choice converted to 1)
0 1 0 -> 10
0 1 1 -> 01
1 0 0 -> 10
1 0 1 -> 01
1 1 0 -> 11
1 1 1 -> 11

这为 01 或 10 提供了 0.375 的机会，为 11 提供了 0.25 的机会。因此这将略微增加重复 10 或 01 值之间发生冲突的风险。

减少冲突

如果您愿意使用所有字母而不是仅使用 'a' 到 'f'（十六进制数字），您可以按照注释中的说明更改 letters 的定义。这将提供更多样的字符串和更少的冲突机会。如果您生成了 1,000 个允许所有大写和小写字母的字符串，则生成任何重复项的几率只有 0.0009%，而仅使用十六进制字符串的几率为 3%。（这实际上也将消除循环中的两次传递。）

如果您真的想避免字符串之间的冲突，您可以将之前生成的所有值存储在 set 中，并在退出循环之前进行检查。如果您要生成少于大约 500 万个密钥，这会很好。除此之外，您需要相当多的 RAM 来保存旧密钥，并且可能需要运行几次循环才能找到未使用的密钥。

如果您需要生成比这更多的密钥，您可以加密一个计数器，如 Generating non-repeating random numbers in Python 中所述。计数器及其加密版本都是 0 到 15,777,216 范围内的整数。计数器将从 0 开始计数，加密版本看起来像一个随机数。然后您将使用上面的第三个代码示例将加密版本转换为十六进制。如果这样做，您应该在开始时生成一个随机加密密钥，并在每次计数器超过最大值时更改加密密钥，以避免再次产生相同的序列。

Answer 3

以下方法的工作原理如下，首先随机选择一个字母以确保规则 2，然后 select 从所有可用字符列表中随机选择 4 个条目。打乱结果列表。最后在除 0 之外的所有条目列表中添加一个值，以确保字符串有 6 个字符。

import random

all = "0123456789abcdef"
result = [random.choice('abcdef')] + [random.choice(all) for _ in range(4)]
random.shuffle(result)
result.insert(0, random.choice(all[1:]))
print(''.join(result))

给你这样的东西：

3b7a4e

这种方法避免了重复检查结果以确保其满足规则。

Answer 4

这个函数returns第n个字符串符合你的要求，所以你可以简单地生成唯一的整数并使用这个函数转换它们。

def inttohex(number, digits):
    # there must be at least one character:
    fullhex = 16**(digits - 1)*6
    assert number < fullhex
    partialnumber, remainder = divmod(number, digits*6)
    charposition, charindex = divmod(remainder, digits)
    char = ['a', 'b', 'c', 'd', 'e', 'f'][charposition]
    hexconversion = list("{0:0{1}x}".format(partialnumber, digits-1))
    hexconversion.insert(charposition, char)

    return ''.join(hexconversion)

现在您可以使用例如

获得特定的

import random

digits = 6
inttohex(random.randint(0, 6*16**(digits-1)), digits)

你不可能同时拥有最大的随机性和最小的冲突概率。我建议跟踪您分发了哪些号码，或者您是否以某种方式循环遍历所有号码，使用随机排序的列表。

Python 中的短唯一十六进制字符串

Short Unique Hexadecimal String in Python

python

uuid

python-3.x

均匀采样

减少冲突