爲什麼Knuth，CLRS哈希函數不足

Question

很容易證明，給定一些具有未知分佈的密鑰集，我們不能構造一個將這些密鑰作爲輸入的函數輸出均勻分佈的值的函數。

因此，我們着眼於未知分佈的通用散列函數。

Knuth建議利用無理數字的非重複數字 - 最值得注意的是黃金比例 - 以便將鍵均勻分佈在表格範圍內。

CLRS建議您簡單地將鑰匙mod作爲一個大的素數，再次將鍵大致均勻分佈在表格範圍內，並分解重複模式。

在這兩種情況下，目標似乎是均勻分配密鑰。但是，在研究諸如Murmur2，SeaHash等解決方案時，他們似乎在確保「蝴蝶狀」效果方面付出了相當大的努力：給定一個鍵，更改任何1位都有很好的機會改變每一個位在散列。

爲什麼這種行爲是可取的？在TAOCP和CLRS中提出的解決方案的缺點是什麼？

如果期望的行爲是分解輸入鍵集合中的任何模式，那麼這裏隱含的假設是，顯示模式類型的鍵集合更可能是瘋狂的？這是否合理？

對不起，如果我不精確。

編輯：不需要具有加密強度。目的是儘量減少碰撞。

Answer 1

我不是100％確定這一點，但這可能是不同作者在不同情境下所做出的不同假設的人工產物。

Knuth在TAoCP中的工作是在任何其他書籍或散列函數開發之前完成的。當時，Knuth在某種意義上開創瞭如何分析和思考不同的算法和數據結構。當時，「使用某種方案將物品分配給水桶」的想法是衆所周知的，但沒有人認真考慮過如何最好地選擇該方案。他的方法在數學上簡單而優雅，並且在當代（20世紀70年代）的硬件上運行得很快。總的主題是「如果你打算根據某種功能進行分配，這裏有一個非常好用和簡單的使用方法，並且有一個很好的理論背後的原因」。

Knuth的第一篇分析數據結構或算法IIRC的論文是在散列表上。他在假設散列碼是一致隨機的假設下做了分析，並表明在這些假設下散列表性能良好。正如你所提到的，很明顯，如果你選擇任何固定散列函數，你將會退化輸入情況。一羣人開始思考如何處理這個問題，許多人嘗試從可用散列函數池中隨機選擇散列函數。在二十世紀七十年代後期，Wegman發表了一篇名爲Universal Classes of Hash Functions的論文，其中概述了一個正式的數學定義，它將一系列散列函數作爲一個很好的散列函數來選擇。本文包含一個證明，即通用散列函數族具有較低的期望碰撞次數，這使得它們適用於鏈式散列表。

CLRS的第一版於1990年出版，並納入了Knuth對線性探測的分析（假設真正隨機的散列碼）和對使用通用散列的鏈式散列表的分析。換句話說，它承認你在選擇哈希函數時必須小心（沒有一個固定函數總是可以工作，所以看看通用哈希函數），但是在假設你有一個「足夠好」的哈希函數的情況下也做了一些數學計算。 （後來的理論發展包括里程碑式的論文「Why Simple Hash Functions Work，」解釋了爲什麼弱哈希函數與輸入分佈中的一小部分熵結合在一起，實際上就像真正的隨機函數一樣，而後來的一些工作表明，獨立的散列函數是你在線性探測表中獲得非常好的性能所需要的。）

所有上述工作都在理論學習中，其目標是建立良好的數學框架來分析數據結構並制定具體的爲實現良好的分配和效率而在實踐中提出方法建議。

然後是真實世界，在那裏從業者並不總是得到數學，數學經常落後於從業者正在做的事情。

如果你看看哈希函數的大部分工作，許多哈希函數假定你正在處理的數據可以很容易地以有意義的方式分解爲整數單元。但真實的數據並不總是以這種方式分解。或者您可能擁有像C++，Java，Python等語言，其中每個對象都有一個「a」散列碼，它與其相關的散列碼，而不是理論家們推薦的具有可用散列函數系列的理由。 （1）瘋狂快速評估，（2）可以在同一程序或多個機器的不同運行中工作，以及（3） ）在實踐中「足夠好」，人們不會抱怨。這就是你獲得像MurmurHash之類的散列函數的地方 - 它們真的很好地滿足了這個需求。假設你沒有針對敵對選擇的輸入工作，這些散列函數都很好。

有趣的是，我們現在看到Knuth的 乘法散列函數的復甦。允許您將不同散列函數組合在一起的庫（如Boost的hash_combine）使用該技術給出確定性但散佈良好的散列碼，給定多個現有散列作爲輸入。

總結：

• 很多的這些差異是歷史。 Knuth爲如何分析哈希函數奠定了理論基礎，並考慮了您擁有單一哈希函數的情況。後來關於通用哈希的研究給出了使用哈希函數類的不同視角和框架。

• 理論與實踐之間始終存在差距。對於非對抗情況，像MurmurHash這樣的非隨機哈希碼很簡單，快速並且運行良好。與單個整數值相比，它們也適用於可變長度輸入。