散列衝突：隨着多次散列而增長的機會

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次重新編譯後，你只有一個不會碰撞的機會。

這完全取決於在每次重新散列之前，這些值會變爲新值。

另一種方式來證明是這樣的：

• 散列算法給你的桶數量有限（=不同的可能哈希值）
• 你可以用不同的值
無限量餵你的哈希算法
• 每個值都需要映射到存儲桶
• 如果您將無限量的值映射到有限數量的存儲桶，則某些時候會出現衝突。