Linux內(nèi)核中的hash與bucket簡單介紹

哈希表(Hashtable)又稱為“散列”，Hashtable是會(huì)根據(jù)索引鍵的哈希程序代碼組織成的索引鍵(Key)和值(Value)配對(duì)的集合。Hashtable 對(duì)象是由包含集合中元素的哈希桶(Bucket)所組成的。而Bucket是Hashtable內(nèi)元素的虛擬子群組，可以讓大部分集合中的搜尋和獲取工作更容易、更快速。

哈希函數(shù)(Hash Function)為根據(jù)索引鍵來返回?cái)?shù)值哈希程序代碼的算法。索引鍵(Key)是被存儲(chǔ)對(duì)象的某些屬性值(Value)。當(dāng)對(duì)象加入至 Hashtable時(shí)，它存儲(chǔ)在與對(duì)象哈希程序代碼相符的哈希程序代碼相關(guān)的Bucket中。當(dāng)在Hashtable內(nèi)搜尋值時(shí)，哈希程序代碼會(huì)為該值產(chǎn)生，并且會(huì)搜尋與該哈希程序代碼相關(guān)的Bucket。例如，student和teacher會(huì)放在不同的Bucket中，而dog和god會(huì)放在相同的 Bucket中。所以當(dāng)索引鍵是唯一從Hashtable獲取元素的性能時(shí)表現(xiàn)會(huì)較好。Hash的四大優(yōu)點(diǎn)如下所示。

· 事先不需要排序。

· 搜尋速度與數(shù)據(jù)多少無關(guān)。

· 數(shù)字簽名的密碼技術(shù)保密性(Security)高。

· 可做數(shù)據(jù)壓縮(Data Compression)，以節(jié)省空間。

Linux內(nèi)核里的哈希表應(yīng)用非常廣泛，PHP內(nèi)核里大部分語言特性也是基于哈希表實(shí)現(xiàn)的。為什么哈希表能這么神通廣大?哈希表能夠?qū)崿F(xiàn)高效的數(shù)據(jù)存儲(chǔ)和查找，而存儲(chǔ)和查找是編程中應(yīng)用最廣泛的兩個(gè)操作。

Linux內(nèi)核里的哈希表

讀過Linux內(nèi)核源碼的人可能都會(huì)發(fā)現(xiàn)，其中并沒有太多復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，作為基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的雙向鏈表(list)和基于list實(shí)現(xiàn)的hash表占據(jù)了絕大部分?jǐn)?shù)據(jù)結(jié)構(gòu)。內(nèi)核為什么會(huì)大量使用這兩種數(shù)據(jù)結(jié)構(gòu)呢?圍繞這個(gè)問題(主要是hash表)，我將以自己的理解揣摩一下其意圖。

首先，這兩種數(shù)據(jù)結(jié)構(gòu)都十分簡單，簡單包括理解起來簡單和使用起來簡單兩方面內(nèi)容。這也意味著代碼的可讀性和可維護(hù)性都比其他復(fù)雜的數(shù)據(jù)結(jié)構(gòu)要好，出現(xiàn)bug的風(fēng)險(xiǎn)也較低。從哲學(xué)上來講，這也符合K.I.S.S.條款。

其次，內(nèi)核是一個(gè)比較講究性能的軟件，為了程序設(shè)計(jì)和維護(hù)的簡單性而失掉性能，這究竟是不是算得不償失呢?我們是不是應(yīng)該將天平更加偏向于性能?已經(jīng)記不起是在哪里聽說過，很多商業(yè)的路由軟件都是基于二叉樹的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)路由項(xiàng)，以求得其路由查找的時(shí)間復(fù)雜度為log(n)，并且他批評(píng)Linux的路由項(xiàng)組織為hash表，致使性能不佳，不適合商業(yè)。確實(shí)有一定道理，可仔細(xì)分析，hash表的性能真的比二叉樹差么?二叉樹的插入和刪除某一項(xiàng)的時(shí)間復(fù)雜度都為log(n);hash表插入和刪除的時(shí)間復(fù)雜度最好為O(1)，最差為O(n)，如果選取的表項(xiàng)(m)足夠多，且hash函數(shù)足夠好的話，其時(shí)間復(fù)雜度為O(n/m)(當(dāng)m<=n時(shí))。當(dāng)m > n / log(n)的時(shí)候，hash表的平均表現(xiàn)就比二叉樹要好;且當(dāng)m>=n時(shí)，其時(shí)間復(fù)雜度趨近于O(1)。m的值可以做成可調(diào)整的，這也正顯示了內(nèi)核的可定制性。不過，不要盲目樂觀，這一切都是以一個(gè)足夠好的hash函數(shù)為前期的。

hash函數(shù)的優(yōu)劣

如何判定一個(gè)hash函數(shù)的好壞呢?

hash的中文意思是“散列”，可解釋為：分散排列。一個(gè)好的hash函數(shù)應(yīng)該做到對(duì)所有元素平均分散排列，盡量避免或者降低他們之間的沖突(Collision)。有必要再次提醒大家的是，hash函數(shù)的選擇必須慎重，如果不幸所有的元素之間都產(chǎn)生了沖突，那么hash表將退化為鏈表，其性能會(huì)大打折扣，時(shí)間復(fù)雜度迅速降為O(n)，絕對(duì)不要存在任何僥幸心理，因?yàn)槟鞘窍喈?dāng)危險(xiǎn)的。歷史上就出現(xiàn)過利用Linux內(nèi)核hash函數(shù)的漏洞，成功構(gòu)造出大量使hash表發(fā)生碰撞的元素，導(dǎo)致系統(tǒng)被DoS，所以目前內(nèi)核的大部分hash函數(shù)都有一個(gè)隨機(jī)數(shù)作為參數(shù)進(jìn)行摻雜，以使其最后的值不能或者是不易被預(yù)測。這又對(duì) hash函數(shù)提出了第二點(diǎn)安全方面的要求：hash函數(shù)最好是單向的，并且要用隨機(jī)數(shù)進(jìn)行摻雜。提到單向，你也許會(huì)想到單向散列函數(shù)md4和md5，很不幸地告訴你，他們是不適合的，因?yàn)閔ash函數(shù)需要有相當(dāng)好的性能。

一籌莫展了吧?誰叫你又想閉門造車了!還是看看前輩們是如何做的，充分發(fā)揚(yáng)拿來主義的精神，我又稱這種做法為“不戰(zhàn)而屈人之兵”，這難道不是兵家之上上策么?Linux內(nèi)核里面用的jhash是一個(gè)久經(jīng)考驗(yàn)，并被實(shí)踐證明經(jīng)得起考驗(yàn)的hash函數(shù)，可以CPMS(Copy Paste Modify Save)之。Jhash的作者Bob Jenkins在其網(wǎng)站上還公布了諸如針對(duì)能預(yù)知的數(shù)據(jù)進(jìn)行hash的hash函數(shù)--完美(perfect)hash函數(shù)等一系列其他hash函數(shù)，看客們可以選擇之，如果有興趣繼續(xù)鉆研，也可以踏在他們的肩膀上。

什么是bucket

bucket的英文解釋：

Hash table lookup operations are often O(n/m) (where n is the number of objects in the table and m is the number of buckets), which is close to O(1), especially when the hash function has spread the hashed objects evenly through the hash table, and there are more hash buckets than objects to be stored.

可以這樣理解：

一個(gè)HASH的結(jié)果所對(duì)應(yīng)的地址可存放兩個(gè)BUCKET。可解決HASH沖突。

· 要存數(shù)據(jù)時(shí)，第一次HASH到這里，在第一個(gè)BUCKET存放一個(gè)數(shù)據(jù)。

· 要存數(shù)據(jù)時(shí)，當(dāng)?shù)诙我蚰承┰騂ASH到這里時(shí)，在第二個(gè)BUCKET存放另一個(gè)數(shù)據(jù)。

一個(gè)由5個(gè)buckets組成的哈希表，里面有7個(gè)元素：

linux的hash函數(shù)hash_long等，用了golden ratio來計(jì)算。因?yàn)橥?bits)的數(shù)量需要由hash函數(shù)和對(duì)沖突的期望來決定，那么對(duì)于hash_long這樣的hash函數(shù)，我們?cè)趺创_定桶的數(shù)量呢?

一般情況下都是自己根據(jù)數(shù)據(jù)特性來考慮使用的 hash 算法，不是千篇一律咬死一個(gè)不放。

比如存放 IP 地址的 hash table，用一個(gè) 65536 的桶就很好，把 IP 的后 16bit 作為 key。這種方法絕對(duì)比 hash_long、jhash 等函數(shù)的碰撞率低。

其實(shí)就是這個(gè)界和性能的折中。我可以取我問題空間的最大值。這樣肯定能保證鍵值分散。但是這樣會(huì)浪費(fèi)很多空間。然而取得太小，又影響查找效率。感覺還是要在試驗(yàn)中進(jìn)行測試。而且個(gè)人覺得，hash比其他搜索的數(shù)據(jù)結(jié)構(gòu)靈活的地方就是它的可定制性。可以根據(jù)具體情況調(diào)整，以達(dá)到最優(yōu)的效果。