這里的文章是飛鴿傳書談哈希表之數學原理轉載的，作者：niniwzw 15:08 2010-5-6

?

.NET程序員，大多數時候是不需要數學的。因為，有了.NET, 數據結構和算法的重要性被弱化了，操作系統相關的東西被強化了。程序員只要求管理好代碼，而不是設計好算法。

計算機，我只學會了技術，所以很多問題我都感覺似是而非，感覺實在學習一個API，而不是在學一門科學。

最近要實現一個哈希表，我查找了很多哈希函數，高下難分。而且，網上有很多人做了實驗，但是，數據很居然是矛盾的。于是我在想，有沒有一種理想的最優函數，這樣的函數的效率是多少。我的函數，只要接近于這個值就可以了。這樣的理想函數的分析，就必須理解計算機的科學部分，這個是計算機科學永恒的部分。

首先，是一個很簡單的也是很實用的問題：

“給一個url 做一個hash 值，通過這個hash 值，查找這個url 是否已經在數據庫中存在了，我相信很多人都做過這個問題，很多人采用把一個url 轉換成一個無符號的int 類型，然后通過這個int 類型進行查找。現在的問題是，如果我的網站有1000萬個url，會有多少個url 是發生哈希沖突呢，也就是說，url鏈接不一樣，但是映射成了相同的哈希值。”有多少沖突，讀完這篇文章你也就會算了。

?

我今天講的只是哈希表中的一種類型：鏈地址哈希表。這種哈希表是最常用的哈希表，PHP數組的內部實現，就是采用這樣的哈希表。估計.net 的字典類，也是通過這樣的方法。

鏈地址法相當的簡單：就是先分配一個大數組，數組的元素是一個鏈表，然后，把key 映射到每個數組的鏈表上，如果有重復，那么就加到鏈表的后面去。不懂的可以去翻翻數據結構的書。

這個數組的長度為m，所以會有m個鏈表，現在的問題是，我有n個key，并且假設 n < m 。問：

沒有元素的鏈表有多少個

只有一個元素的鏈表有多少個

有兩個元素的鏈表有多少個

.....

這個問題雖然不是很復雜，但是，還是要稍微的轉換一下，動一點點的腦筋。

看問題本身，好像是一個組合學的問題，就是有m個位置,n個元素往里面放。從這個角度可以做，但是，比較麻煩。考慮這樣一個問題, 任意一個元素，在某個位置不出現，出現一次，出現兩次... 出現n 次的概率。你會發現，這個其實就是上面的鏈表元素個數的問題。這里，假設元素都是一樣的，位置也都是一樣的。

這就是一個binary 分布的問題。不懂的可以看概率論的書本。

這樣，鏈表有k 個元素的概率分布函數如下：

p = 1 / m

f[k] = (C[n,k]? * p^k * (1-p)^n-k );

現在我假設 m = 2^14, n = 10000

可以求出概率分布如下：

?

可以看出，大概54%的鏈表是空的，大概33%的鏈表有一個元素,10%左右的鏈表有兩個元素。如果，你的哈希函數寫的好，基本上，要接近上面的數字。如果超過了這個數字，哈希函數也會有問題。這個我已經通過實驗證明了這一點。可能在接下來的章節中介紹我實現的哈希表。

當然，設計哈希表，最重要的是要求其平均查找長度最小。

所有一個元素的鏈表包含的元素數目為 m * f[1] * 1, 查找這些元素的次數為： m * f[1] * 1 * 1

兩個元素的鏈表包含的元素數目為? m * f[2] * 2，查找這些元素的次數為： m * f[2] * 2 * 2

這樣平均查找長度就是：（這里的平均，實際上不是平均，而是考慮最壞的查找情況，比如鏈表長度為2，平均是1.5次，最壞是2次）

求:

?

如果，看到這個式子，還不會求和的話，那么你趕快回去看看概率論了。

求出的結果是：

L = 1 + （n-1）/ m

是不是非常簡單。

如果n 足夠大，比如上萬了，那么1就可以忽略了

L = 1 + n / m

這個公式表明，平均查找長度只和 n / m 的比例有關。如果 m > n 那么，理想情況下，不會出現平均查找長度大于2的情況。而，對于100萬的數據的平衡二叉樹，那么需要20次的查詢，性能是10倍。當然，哈希表非常的的浪費內存。

再來看看我們剛開始提出的問題，轉換一下就是：m = 2^32 n = 10,000,000.要求重復的數目，只要求出不重復的數目就可以了。就是求f[1] 就可以了，當然，如果你有數學計算軟件，這個計算比較耗時，但是肯定能夠算出來。

還有一個比較簡單的方法，可以簡單的估計大概的數目，那就是平均查找長度。這里估計的時候，有一個假設，就是，在一次查找時，只有兩種情況，一種是查找一次，一種是查找兩次找到。二項分布在m,n相差比較大的時候，隨著k的上升，概率下降會非常的快，一般重復3次的就很少了，上面的假設是合理的。這樣的話，出現重復的概率就是 n/m 了（可以很簡單的推導出來），0.0023，也就是10000個鏈接里面，就會有23個重復。如果要求比較高的話，基本上，不能采用這樣的哈希方法。當然，如果是100萬的話，那10000個鏈接，只有2個重復，基本上是合理的。不過，最好只有10萬。這樣沖突概率就相當的低了。

接下來的文章，我可能會寫哈希表的實現的一些技巧，如何管理內存，如何分配哈希表的長度（根據不同的需求）。
飛鴿傳書：http://www.freeeim.com/

總結

以上是生活随笔為你收集整理的飞鸽传书谈哈希表之数学原理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。