使用模塊化散列函數比較數字？

Question

我想使用散列表比較b個數字中的b個數字，以確定哪些數字相同。如果我使用模塊散列函數，我應該使用h（a）= a mod（b）還是h（a）= a mod（b-1）？我不知道如何確定這些是否合適。

Answer 1

所以，你必須在範圍0 ... b^b - 1（例如10號範圍0 ... 9999999999）b號碼。

如果你想保證該散列函數是免衝突的，你不能使用mod。如果你使用例如a mod 10，則31和56465421都得到1的散列並且發生衝突，並且這發生在10000000000以下的每個mod。

所以你只能減少散列衝突的概率。有機會避免碰撞的最小mod值爲b（但最有可能的是，那麼碰到碰撞）。沒有做適當的概率計算，我會去mod b*b之類的東西，有效地採取兩個尾隨數字。