爲什麼複合數字在分割哈希時不好？

這是我第一個關於stackflow的問題。如你所知，我是學習算法和數據結構的新手。爲什麼複合數字在分割哈希時不好？

當使用劃分方法來創建散列函數（即h（k）= k mod m）時，建議（例如通過CLRS）使用不等於2的冪數的質數作爲除數米有人可以向我解釋爲什麼選擇m是複合號碼是不好的？

2012-02-26 user1234310

[爲什麼要使用哈希函數使用素數模數？]（http://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime-number-modulus） – interjay 2012-02-26 20:30:31

考慮如果m是偶數並且所有k值均勻的情況。然後，哈希值也都是均勻的。

例如，考慮的情況下M = 6散列甚至值：

Input values: 0, 2, 4, 6, 8, 10, 12, 14, 16, ... 
Hash values: 0, 2, 4, 0, 2, 4, 0, 2, 4, ...

如果使用這些散列值作爲索引到表中，則表中的一半將是未使用的。另一方面，如果m是素數，即使輸入值都有一個公共因子，你也會得到散列值的均勻分佈。

考慮相同的輸入值，但是具有m = 7：

Input values: 0, 2, 4, 6, 8, 10, 12, 14, 16, ... 
Hash values: 0, 2, 4, 6, 1, 3, 5, 0, 2, ...

儘管輸入值是所有偶數，哈希值仍然均勻分佈在[0..6]。因此，總而言之，如果m是素數，那麼即使所有輸入值都可以被一個常見的素數因子（除m之外）整除，你仍然可以得到散列值的均勻分佈。

來源

2012-02-26 21:01:12

你稱之爲輸入值實際上是一個糟糕的哈希函數的結果，在較低的位中熵不足。「問題」也可以通過選擇更好的散列函數來解決。 – wildplasser 2012-02-26 22:20:16

在OP的問題中，這些**是**輸入值**。 OP寫道：「當使用劃分方法創建散列函數（即h（k）= k mod m），[...]」時。當我說**輸入值**時，我指的是您輸入* h（k）*的* k *的值，計算* k mod m *。 – 2012-02-26 22:31:14

雖然你是正確的，但問題依然存在：**輸入值**不均勻分佈。（在這個例子中：它們都是）。如果他們被允許不均勻分佈，他們也可能都是表格大小的倍數。解決這類問題的另一種方法是在執行模數之前將它們全部乘以奇數（相對素數）。這將允許表格大小爲*任何*號碼，包括兩個冪。 – wildplasser 2012-02-26 22:56:26

如果你知道散列函數，那麼你總是可以生成一組完美的輸入數據，這將使得散列函數表現得很糟糕。沒有「通用最佳」散列函數。但總是有一組最好的輸入數據和一組最差的輸入數據。

好的哈希函數有望大集合X的任意子集映射到一個較小的輸出設定Y，與碰撞的該組Y.

其必然結果是最小的和公平的分配，也沒有預測散列函數的方法將是好的，而不需要知道該函數將被認爲是「好的」的數據集。

關於使用質數而不是組合數字的建議，沒有關於哈希值的知識，並不比要求87654321是哈希的最佳模數更好。

如果要散列素數或斐波那契數，那麼有關使用質數模數或複合模數或2的冪的建議是無關緊要的。

如果要散列複合數字成對的共素數，則輸入集合中每個元素的複合模數共素是「良好」選擇的候選項。大於輸入集中所有元素的最大因子的質數是另一個「好」選擇。

如果您的輸入集是一個間隔內的整數稀疏集，並且數字之間的間隔具有高斯分佈，那麼模數的「最佳」選擇是一個數字，用於最小化gcd（模數，輸入數據）！= 1。選擇質數作爲模數時，這很可能發生。

這是建議使用素數的原因。

來源

2013-08-09 20:28:18 Pierre

爲什麼複合數字在分割哈希時不好？

回答

相關問題