散列冲突：随着多次散列而增长的机会

Question

散列对象多次散列冲突的可能性增加了吗？

意思是说，hash(hash(object))的碰撞率高于hash(object)？

Answer 1

取决于你的意思。

如果由于重新散列造成散列发生变化，那么是的，如果没有，那么没有。

如果对象没有改变，而你重新哈哈哈哈，它会保持相同的散列。例如，字符串teststring的md5散列将始终为D67C5CBF5B01C9F91932E3B8DEF5E5F8。

但是，如果对象发生变化并因此重新哈希，您将得到一个新的哈希值。

现在，如果您重新刷新发生更改的对象，则碰撞可能性会更高。

举个例子，你有一个非常简单的对象，它只包含一个整数值和一个非常简单的散列算法，它只需要这个值，并对它做一个modulo 20。这只是针对这个例子的一个故意的散列算法。

现在说你有两个包含随机数的对象。这两个值的哈希碰撞的机会是1/20，因为哈希算法中有20个存储桶。

如果您现在重新组合，您将再次有机会碰撞或碰撞的几率为19/20。

因此n rehashes之后没有碰撞的机会是(19/20)^(n+1)。所以在第一次重新散列之后（所以你有你的原始值，并且在它改变之后重新刷新其中的一个值），你有没有碰撞的90.25%机会。在第二次重新刷新之后，你有可能不会碰到任何碰撞的85.76%。经过100次重新编译后，你只有一个不会碰撞的机会。

这完全取决于在每次重新散列之前，这些值会变为新值。

另一种方式来证明是这样的：

• 散列算法给你的桶数量有限（=不同的可能哈希值）
• 你可以用不同的值
无限量喂你的哈希算法
• 每个值都需要映射到存储桶
• 如果您将无限量的值映射到有限数量的存储桶，则某些时候会出现冲突。