php - 在哪里可以找到 xxhash64 和 md5 碰撞概率统计信息？

Question

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

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

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

Answer 1

您可以使用 birthday problem 自行计算.

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

p(k) = 1 - exp(-k(k-1)/2N, k (number of hashes) randomly generated values, where each value is a non-negative integer less than N (number of possible hashes):

N = 2^(number of bit), example for md5 it is 2^128, or 2^32 for 32 bit-hash

如果你使用 md5

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

如果你使用亿个散列键，使用 md5 的冲突概率是 0%。

如果您使用 xxhash64，

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

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

如果您使用数亿个散列键，使用 xxhash64 的冲突概率为 0.033%。

这个 link解释了为什么 md5 或快速哈希方法不安全。