问哈希-冲突:多哈希的机会增长

EN

取决于你到底是什么意思。

如果哈希由于重散列而发生变化，则是的，如果没有，则不会。

如果对象没有更改，并且您重新散列它，它将保持相同的哈希。因此，例如，字符串teststring的teststring哈希将始终是D67C5CBF5B01C9F91932E3B8DEF5E5F8。

但是，如果对象发生了更改，并因此而重新散列，您将得到一个新的哈希。

现在，如果您重新散列一个已更改的对象，则可能会有更高的碰撞机会。

例如，您有一个非常简单的对象，它只包含一个整数值，还有一个非常简单的散列算法，它只接受这个值并对其执行modulo 20。对于本例来说，这是一种故意错误的散列算法。

现在假设有两个包含随机数的对象。这两个值的哈希冲突的可能性是1/20，因为哈希算法中有20个桶。

如果您现在重新哈希，您再次有机会发生1/20碰撞，或者19/20机会不发生冲突。

因此，在n重哈希之后不发生碰撞的机会是(19/20)^(n+1)。因此，在第一次重哈希之后(因此，您有了原始值，并在其更改后重新哈希其中一个值)，您就有了一个不发生冲突的90.25%机会。在第二次重哈希之后，您将陷入没有任何冲突的85.76%机会。在100次重哈希之后，您将只剩下一个0.59%的机会，即不会发生碰撞。

这完全取决于每次重新哈希之前值是否更改为新值。

另一种证明这一点的方法是：

• 哈希算法为您提供了有限数量的桶(=不同的可能散列)
• 您可以使用无穷多个不同的值来填充散列算法。
• 每个值都需要映射到一个桶。
• 如果有无限多的值映射到有限数量的桶中，那么在某个时候就会发生冲突。