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

Question

6

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

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

因此，我需要一些信息，以决定这对我的任务是否是一个好决策。在最好的情况下-比较md5和xxHash64之间碰撞数量的差异。

- arkhamvm

xxhash64是一种快速算法，它是一个64位哈希函数。 - Michael GEDION

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Michael GEDION · Accepted Answer

你可以使用生日问题来计算。

通常，给出哈希函数概率的数学表达式是： 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千万亿次哈希！！！如果我们使用少于10亿个哈希，碰撞的概率可以忽略不计。

如果您使用亿万个哈希键，使用md5的冲突概率为0％。

如果您使用xxhash64，

假设xxhash64生成64位哈希。您将得到此图表。

根据这张图片，您可以看到，如果冲突百分比为50％，则需要至少5十亿个哈希。其中两个哈希的机会是1/2，有相同的哈希值！如果您有大约120亿个哈希，则哈希碰撞的几率为100％。

如果您使用亿万个哈希键，使用xxhash64的冲突概率为0.033％。

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