代码之家 › 专栏 › 技术社区 › Andrew Cheong

如果生成器(例如,Java版本的UUID)未知,UUID的哪一个数字最不可能发生冲突?

hash-collision uuid java

1

Andrew Cheong · 技术社区 · 6 年前

假设我们有一组现有的UUID(比如,数百万,尽管这并不重要),它们可能是由不同的客户机生成的,因此我们不知道生成任何UUID的算法。但是我们可以假设它们是流行的实现。

是否有一组8位或更多的数字(不一定是连续的,但理想情况下是连续的)发生碰撞的可能性更小或更大?

例如,我看到了 uuid() MySQL中的函数,当在同一语句中使用两次时,会生成2个完全相同的UUID,除了第5到第8个数字:

0dec7a69-ded8-11e8-813e-42010a80044f
0decc891-ded8-11e8-813e-42010a80044f
    ^^^^

一般来说,答案是什么?

该应用程序将公开一个更紧凑的ID,供客户通过电话复制、粘贴或通信。不幸的是,我们注定要在后端使用UUID,并且不愿意在ID的长版本和短版本之间创建映射,这是可以理解的,但是我们可以继续使用截断的UUID,它偶尔会碰撞并返回超过1个结果。

2 回复 | 直到 6 年前

1

2

Basil Bourque 6 年前

建议:前8位

1c59f6a6-21e6-481d-80ee-af3c54ac400a
^^^^^^^^

所有的生成器实现都是 required to use the same algorithms 对于一个给定的版本,所以要担心后者而不是前者。

UUID version 1 &安培; version 2 对于一个给定的源,通常按从大到小的熵排列。因此,前8位数字最不可能发生碰撞。

UUID version 4 和 version 3 & 5 除了为 version 和 variant . 所以前8位数字和其他数字一样好。

2

Erwin Bolwidt 6 年前

有一种方法可以工作,不管UUID规范有什么警告。由于UUID本身是全局唯一的,因此使用至少具有相同位大小的适当算法生成的安全哈希将具有相同的属性。除了安全散列将通过散列值而不是特定位置具有熵之外。

例如,您可以执行以下操作:

MessageDigest digest = MessageDigest.getInstance("SHA-256");
byte[] hash = digest.digest(uuid.toString().getBytes(StandardCharsets.UTF_8));

然后根据需要从散列中取出尽可能多的位,并将它们转换回字符串。

不过,这是一个单向函数;要快速高效地将其映射回UUID,需要保留一个映射表。(当然,您可以通过再次对UUID执行单向哈希来检查UUID是否与较短的代码匹配)

但是,如果要从UUID中取出一个不连续的部分,则会出现相同的问题。