在一個32位散列與兩個16位散列之間是否存在衝突率差異？

Question

我正在研究散列碰撞會成爲問題的系統。本質上有一個引用哈希表+樹結構中的項目的系統。然而，所討論的系統首先將包含結構中路徑的文本文件編譯爲包含哈希值的二進制文件。這是出於性能原因而完成的。但是由於這種衝突非常糟糕，因爲結構不能存儲具有相同散列值的2個項目;要求物品的零件沒有足夠的信息來知道它需要哪一個。

我最初的想法是使用2種不同算法的2次哈希算法，或者2次使用相同算法的2次哈希算法會更有抵抗性。對於不同的散列算法，具有相同散列的兩個項目將不太可能。

我希望能夠保留哈希值32位的空間原因，所以我想我可以切換到使用兩個16位算法，而不是一個32位算法。但是這不會增加可能的哈希值範圍...

我知道切換到兩個32位散列會更耐衝突，但我想知道是否切換到2個16位散列至少有一些獲得一個單一的32位散列？我不是最數學的人，所以我甚至不知道如何開始檢查，而不是謠傳力它的其他答案...

系統上的一些背景資料：

項獲得通過名字人類，它們不是隨機的字符串，並且通常由沒有空格的單詞，字母和數字組成。它是一個嵌套的散列結構，所以如果你有類似{a => {b => {c =>'blah'}}}，你可以通過得到a/b/c的值來得到值'blah'，編譯後的請求將是立即序列中的3個散列值，a，b和c的hashe值。

當給定等級發生碰撞時，只有一個問題。頂層和下層物品之間的碰撞很好。你可以有{a => {a => {...}}}，幾乎可以保證在不同級別上的衝突（不是問題）。

在實踐中，任何給定的等級都可能有小於100的散列值，並且沒有一個會在同一等級上重複。我下載了CPAN Perl模塊的全部列表，將所有的命名空間/模塊拆分爲唯一的單詞，並最終對每一個搜索衝突進行了散列處理，我遇到了0次碰撞。這意味着算法對於CPAN名稱空間列表中的每個唯一字都有不同的散列值（或者我做錯了）。這對我來說似乎很好，但它仍然縈繞在我的大腦中。

Answer 1

如果你有2個16位散列，產生不相關的值，那麼你剛剛寫了一個32位散列算法。這不會比任何其他32位散列算法更好或更差。

如果您擔心碰撞，請確保您使用的散列算法能夠很好地散列數據（有些寫法只是快速計算，這不是您想要的），並且增加了你的散列的大小，直到你感到舒服。

這提出了碰撞概率的問題。事實證明，如果您的收藏中包含n件物品，則會有可能發生碰撞的物件對n * (n-1)/2。如果您使用k位散列，則單個對碰撞的機率爲2-k。如果你有很多東西，那麼不同對碰撞的機率幾乎是不相關的。這正是Poisson distribution描述的情況。

因此，您將看到的碰撞次數應大致遵循泊松分佈λ = n * (n-1) * 2-k-1。由此可見，沒有散列衝突的概率約爲e-λ。有32位和100項，一個級別的碰撞機率約爲1.1525百萬。如果你這樣做了足夠多的時間，並且有足夠多的不同數據，那麼最終那百萬次的機會就會加起來。

但請注意，您有許多正常大小的水平和一些大的水平，大的水平會對碰撞風險產生不成比例的影響。這是因爲你添加到集合中的每一件事都可能與前面的事情相沖突 - 更多的事情等於更高的碰撞風險。因此，例如，具有1000個數據項目的單個級別在10,000次失敗中具有大約1次機會 - 這與100個數據項目的100個級別具有相同的風險。

如果哈希算法沒有正常工作，您的碰撞風險將會迅速上升。如何迅速取決於失敗的性質。使用這些事實和你的應用程序的用法，你應該能夠決定你是否適應32位哈希的風險，或者你是否應該向更大的方向發展。