在哪里可以找到 xxhash64 和 md5 碰撞概率统计数据？

Question

我没有找到有关 xxhash64 冲突百分比的任何信息。

我将把它用于缓存系统（生成需要唯一的哈希键，大约数亿个）。现在我使用 md5，但我不需要加密属性。

所以我需要一些信息来决定这对我的任务来说是否是一个好的决定。最好的情况 - 比较 md5 和 xxHash64 之间的冲突次数。

Answer 1

你可以利用生日问题来计算一下自己。

一般来说，给出哈希函数概率的数学表达式是：

p(k) = 1 - exp(-k(k-1)/2N, k（哈希数）随机生成的值，其中每个值都是小于 N（可能的哈希数）的非负整数：

N = 2^（位数），例如 md5 为 2^128，或 32 位哈希为 2^32

如果你使用md5

将产生一个 128 位哈希值，通过应用此公式，您将得到这个“S”图。例如，该图说明，为了获得 50% (0.5) 的碰撞概率，您至少需要 21 000 000 万亿个哈希值或 21 500 亿个哈希值！！！如果我们使用少于 10 亿个哈希值，则冲突的概率可以忽略不计。

如果您使用数亿个散列密钥，则使用 md5 时发生冲突的概率为 0%。

如果你使用xxhash64，

假设 xxhash64 产生 64 位哈希。你会得到这个图表。

根据这张图可以看出，如果碰撞百分比为50%，则至少需要50亿次哈希。50 亿个哈希中的两个可以有 1/2 的奇数拥有相同的哈希！如果您有大约 120 亿个哈希值，则哈希值冲突的可能性为 100%。

如果您使用数亿个散列密钥，则使用 xxhash64 时发生冲突的概率为 0.033%。

此链接解释了为什么 md5 或快速哈希方法不安全。