python - 添加随机字节如何*增加*重复项？

Question

这是一个 Python 函数，用于为 UUID 生成我自己的特定类型(关于为什么我不能使用 uuid.uuid1() 说来话长):

def uuid():
    sec = hex(int(time()))[2:]
    usec = hex(datetime.now().microsecond)[2:]
    rand = hex(choice(range(256)))[2:]

    return upper(sec + usec + rand)
    # 534AD79CDF1D27

现在，让我们让它运行很长一段时间，看看我们是否发现任何重复项:

UUIDs   Duplicates
100000  2
200000  8
300000  8
400000  8
500000  8
600000  9
700000  9
800000  9
900000  9
1000000     10
1100000     14
1200000     14
1300000     14
1400000     17
1500000     17
1600000     18
1700000     21
1800000     24
1900000     24
2000000     27

是的!事实上将近 30 个重复...现在，这是一个末尾没有随机字节的新函数:

def uuid():
    sec = hex(int(time()))[2:]
    usec = hex(datetime.now().microsecond)[2:]

    return upper(sec + usec)
    #534ADA2AC4A41

让我们看看现在有多少重复项:

UUIDs   Duplicates
100000  0
200000  0
300000  0
400000  0
500000  0
600000  0
700000  0
800000  0
900000  0
1000000     0
1100000     0
1200000     0
1300000     0
1400000     0
1500000     0
1600000     0
1700000     0
1800000     0
1900000     0
2000000     0

好吧，你会看那个吗？没有一个重复的!此外，如果您对我如何确定重复项数量感到好奇，请查看以下代码:

len([x for x, y in Counter(ids).items() if y > 1])

现在，回到实际问题:如何添加一个随机生成的字节增加重复项的数量？

Answer 1

问题是您使用的 hex() 没有零填充。 hex(int(time())) 基本上总是 8 个半字节长，因为它递增得非常慢，所以第一部分是恒定长度。这里的 Nybble 指的是一个十六进制数字。

但是，hex(datetime.now().microsecond) 不是常量长度。它将在 1 nybble(最多 9 us)到 5 nybbles(999999 us)之间变化。如果没有“随机字节”，这不是问题，因为您可以通过截断秒来唯一地获得微秒值。

但是，您的“随机字节”也是在没有任何填充的情况下生成的!因此，您最终可以生成 1 nybble 随机字节或 2 nybble 随机字节。因此，您最终可能会造成更多冲突，因为您可以使用例如生成相同的 uuid一个 3-nybble usec 和一个 2-nybble rand，就像一个 4-nybble usec 和一个 1-nybble rand。因此，例如，这两个是碰撞:

usec = 0xabc
rand = 0xde

和

usec = 0xabcd
rand = 0xe

要解决此问题，请填充所有字符串。使用 format 很容易做到这一点:

usec = format(datetime.now().microsecond, '05x') # hexify `microsecond` with 5 fixed hex digits