散列碼計算

Question

我正要通過的哈希碼的概念，並遇到了線multiplying by primes will not tend to shift information away from lower end - as would multiplying by a power of 2

我沒有得到這條線，任何人都可以幫我這個。

謝謝。

Answer 1

該建議針對基於多個字段的計算散列碼給出。它基於這樣的觀察，即在0和32之間乘以2的冪相當於將剩下的數字移位相應的位數，從而將該數字的右側「歸零」。

考慮一種情況，當您需要構造十個字段的哈希碼，並將各個字段的哈希碼乘以32.這相當於將哈希碼向左移動五位。如果你這樣做，結束散列碼將不依賴於前三個字段的散列碼，因爲它們的散列碼的值將從結果散列碼中移出。

這種行爲是不可取的，因爲與最後七個字段是相同的項目將具有相同的哈希代碼，即使第一三個字段可能會不同。這很糟糕，因爲它增加了散列衝突的可能性。相反，如果乘以大於2的素數，則有關每個字段的散列值的某些信息會影響最終結果，從而形成更好的散列函數。

Answer 2

在散列碼的許多用途中，只有散列碼最不重要的部分發生變化。換句話說，3和5之間的差異很重要，但是3000和5000也可能是相同的數字。

原因是哈希碼用於根據哈希碼的值對「桶」進行粗略的「排序」。這允許像散列表這樣的結構僅在存儲桶內搜索特定值，而不是搜索表中的每個元素。

問題是，有超過40億個可能的哈希碼，但通常會有數量更少的桶來放入值。

想象一下，您將一個場景散列爲10個桶。哈希碼0-9可以全部進入單獨的桶中，​​但是然後10需要進入與0相同的桶，11與1相同，等等。如果你有像1，145，42，5830這樣的hashcode，那麼所有的工作都很好，因爲每個值都可以放入不同的桶中。像1,131,593021,63421那樣的數值，他們都會進入同一個水桶，因爲他們以相同的數字結束，這就是我們所看到的，因爲我們只有10個水桶。所以它只會改變我們hashcode中最不重要的部分。