algorithm - 如何快速判断两组校验和是否相等，与单个校验和相同的 "strength"

Question

假设您有两组无序的校验和，一组大小为 N，一组大小为 M。根据比较它们的算法，您甚至可能不知道大小，但可以比较 N != M 以快速中止，如果您做。

用于校验和的散列函数有一定的碰撞几率，作为外行，我愚蠢地将其称为“强度”。有没有办法获取两组校验和，全部由相同的哈希函数制成，并快速比较它们(因此比较元素到元素是正确的)两组之间的基本碰撞机会与两个单独的校验和之间的碰撞机会相同？

例如，一种方法是通过对集合中的所有校验和进行异或来计算“集合校验和”。这个新的单一散列用于与其他集合的散列进行比较，这意味着不再需要存储大小。特别是因为它可以通过与集合的校验和进行异或来修改以添加/删除元素校验和，而无需重新计算整个事情。但是，与所有原始校验和的强力比较相比，这是否会降低校验和的“强度”？有没有一种方法可以合并集合的校验和，既不会降低“强度”(同样多？)，但仍然比直接比较集合元素的校验和更简单？

Answer 1

在我最初的评论之后，我开始思考它背后的数学原理。这是我想出的。我不是专家，所以请随时进行更正。注意:这一切都假设您的哈希函数是均匀分布的，因为它应该是。

基本上，校验和中的位数越多，发生冲突的可能性就越低。文件越多越高。

首先，让我们计算一对文件异或后发生冲突的几率。我们将首先处理小数字，因此假设我们的校验和为 4 位 (0-15)，我们将其称为 n。

有了两个和，总位数 2n(8)，所以总共有 2^(2n)(256) 种可能性。然而，我们只对碰撞感兴趣。要碰撞 XOR，您需要翻转两个和中的相同位。只有 2^n(16) 种方法可以做到这一点，因为我们使用的是 n 位。

因此，碰撞的总体概率为 16/256，即 (2^n)/(2^(2n))，或简称为 1/(n^2)。这意味着非碰撞的概率是1 - (1/(n^2))。因此，对于我们的示例 n，这意味着它只有 15/16 安全，即 93.75%。当然，对于更大的校验和，它更好。即使对于微不足道的 n=16，您也可以获得 99.998%

当然，这是针对单一比较的。由于您将它们全部滚动在一起，因此您正在进行 f-1 比较，其中 f 是文件数。要以这种方式获得碰撞的总几率，您可以使用我们在第一步中获得的几率的 f-1 次方。

因此，对于 10 个具有 4 位校验和的文件，我们得到非常糟糕的结果:

(15/16) ^ 9 = 55.92% chance of non-collision

即使我们增加了文件数量，这也会随着我们增加位而迅速变得更好。

对于 10 个具有 8 位校验和的文件:

(255/256) ^ 9 = 96.54%

对于 16 位的 100/1000 个文件:

(65536/65536) ^ 99 = 99.85%

(65536/65536) ^ 999 = 98.49%

如您所见，我们仍在使用较小的校验和。如果您使用 >= 32 位的任何东西，当我尝试对其进行数学运算时，我的计算器会出现浮点舍入错误。

长话短说:

其中 n 是校验和位数，f 是每组中的文件数:

nonCollisionChance = ( ((2^n)-1) / (2^n) ) ^ (f-1)
collisionChance = 1 - ( ((2^n)-1) / (2^n) ) ^ (f-1)

您将一堆校验和异或在一起的方法可能很好。