「散列函數的分佈」是什麼意思？

在閱讀關於Object.GetHashCode方法的MSDN文檔時，我遇到了類似於散列函數應該在散列表中提供隨機或有用分佈的短語。這個分佈對散列函數或散列表意味着什麼？「散列函數的分佈」是什麼意思？

來源

2012-04-06 surajnaik

http://en.wikipedia.org/wiki/Hash_table – 2012-04-06 06:12:37

粗略地說：散列值應該「在沒有明顯圖案的情況下在其域內隨機散佈」（例如，當以可視方式查看時，最小結塊和最大散佈）。許多哈希實現將重新哈希散列，以減少在放入桶中時出現「出現」的可能性。 – 2012-04-06 06:15:31

爲了「平衡」散列表，散列函數產生一個32位整數。假設你的表有一百個「桶」，並且你根據散列函數的底部兩個十進制數字將表中的項放入一個桶中。

現在假設散列函數總是產生的數字甚至是偶數百的數字。每個項目將要進入同一個桶，並且哈希表將不平衡。這將是一個糟糕的散列函數。

好的哈希算法產生一個大致均勻分佈無論你有多少個水桶有和無論你如何從哈希提取桶數。

來源

2012-04-06 06:18:22

爲了使散列表的功能最大化，散列值應該儘可能唯一以防止衝突。例如，讓我們考慮一個非常天真的散列函數：假設您的對象是名和姓，並且您的散列值可以選擇首字母。所以Ginger Rodgers的哈希值是GR，而Fred Astaire的哈希值是FA。到目前爲止這麼好，但是當弗蘭克艾倫配上FA的哈希值時會發生什麼？現在你在Fred Astaire和Frank Allen之間發生衝突，並且散列表實現必須將其作爲特殊情況處理，這會降低效率。

最好的散列函數需要輸入空間（Fred Astaire），併產生一個隨機值（理想情況下）是輸入空間唯一的。只要散列的大小小於數據的大小，就沒有辦法完全避免衝突，但應該通過仔細選擇散列算法來最小化它們。

正如Eric所指出的那樣，爲了平衡散列表，散列算法必須非常快速，所以你必須在速度和碰撞之間取得平衡。您可以學習像SHA-1（http://en.wikipedia.org/wiki/SHA-1）這樣的加密哈希算法來理解生成唯一哈希的複雜性，但是用於平衡哈希表的哈希算法需要儘可能快。

來源

2012-04-06 06:20:34

直到最後一段，你都做得很好。加密散列函數的要求和散列函數對平衡散列表的要求是非常非常不同的，你不應該混淆這兩者。你不應該使用像SHA1這樣的算法來進行散列表平衡;請記住，散列表平衡算法的要點是*它是性能優化*，所以不要使用*慢且複雜的散列算法！ – 2012-04-06 06:40:50

好點，埃裏克。我只是想指出一個散列算法，它在避免衝突方面做得非常好。我會相應地更新我的答案。 – 2012-04-06 06:42:35

有人可能會選擇通過返回32位整數來散列32位整數。非常適合散列表平衡，對於加密散列很糟糕。爲了理解散列表平衡散列函數，我建議不要研究加密散列算法。 – Brian 2012-04-09 15:36:55

「散列函數的分佈」是什麼意思？

回答

相關問題