一、背景
本篇文章將先從對哈希表的基本介紹開始，然後分析Linux內核（3.10.0版）中的list.h文件中的哈希表。
二、簡述哈希表
根據設定的哈希函數H(key)和處理衝突的方法將一組關鍵字映像到一個有限的連續的地址集上，並以關鍵字在地址集中的“像”作為記錄在表中的存儲位置，這種表便稱為哈希表。
上面這一段是從一本教材中摘抄出來的對哈希表的一段描述。
大家對數組的概念想必都不陌生，眾所周知，數組通過數組號就可以找到對應的存儲的數據。但數組的缺點也很明顯，不便於增刪數據。
大家對雙向鏈表的概念也一定不陌生，雙向鏈表比起數組，增刪方便，但是查找數據就需要遍歷整個鏈表，很費時費力。
如果可以有一個鏈表，既增添方便，也可以直接進行數據的訪問而不必不斷比較那就太好了。哈希表就是有類似這樣的能力。
當然，我這樣的說法並不嚴謹。但便於理解。
三、哈希函數的構造
可以想象，如果一個索引號對應著不止一個數據，那這時候就會有矛盾產生。到底對應著哪個數據呢？我們有必要構造哈希函數來使一組關鍵字的哈希地址均勻分佈在整個地址區間中，從而減少衝突。
常用構造哈希函數的方法有：（1）直接定址法 （2）數字分析法 （3）平方取中法 （4）摺疊法 （5）除留餘數法 （6）隨機數法
具體的可以查閱相關資料。
四、處理衝突的方法
常用的處理衝突的方法有：（1）開放定址法 （2）再哈希法 （3）鏈地址法 （4）建立一個公共溢出區
具體的可以查閱相關資料。
五、list.h文件的哈希表的構造與實現分析
在linux kernel 3.10.0版本中，list.h位於include/linux目錄下。
我們先來看一看list.h中哈希表的構造：
可以看到，linux內核處理衝突的方法是鏈地址法。思想是：將所有關鍵字為同義詞的結點鏈接在同一個鏈表中。若選定的哈希表長度為m，則可將哈希表定義為一個由m個頭指針組成的指針數組。就如上圖所示。
在linux內核中定義哈希表頭結點與結點的代碼位於types.h文件中。
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};
對源碼分析如下：
1、初始化哈希表頭結點
第一條宏定義只初始化頭結點
第三條宏定義使用指針初始化頭結點，可在運行時進行初始化
2、初始化哈希表結點、檢測結點是否未被哈希、檢測哈希表是否為空
3、刪除哈希結點
我在這裡分析一下實現函數（第一個函數）：
S1:next是一個指向結構體struct hlist_node的指針，在這裡給它賦了一個初值n->next。這樣，next就指向n的下一個結點。
S2:pprev是一個二級指針，指向指向結構體struct hlist_node指針的指針，在這裡給它賦了一個初值n->pprev。這樣，pprev就指向上一個結點的next指針。
S3:將n下一個結點的地址賦給n上一個結點的next指針。這樣，n上一個結點的next指針就不指向n了，而是指向n的下一個結點。
S4:如果n下一個結點為空，則結束。n下一個結點不為空，則將n下一個結點的pprev指向n上一個結點的next指針。
到此就結束了結點的刪除操作。
第二個調用函數執行完刪除操作後將分別指向了LIST_POISON與LIST_POISON2。以保證不在鏈表中的結點項不能被訪問。
第三個調用函數先判斷該結點是否被哈希，接著刪除完後還要對該結點進行初始化。
第二和第三個調用函數在對n結點進行刪除後的處理是不同的，前者是將n設置為了不可用，後者是對n進行了初始化。
4、添加哈希結點
（1）第一個函數將n結點添加在頭結點h之後
（2）第二個函數將n結點添加在結點next之前，所以next結點一定不可以為NULL
（3）第三個函數將next結點插入到n結點之後
（4）第四個函數十分奇怪，它將自己的ppev指針指向自己的next指針，實現了虛假添加操作，這樣的結點會被hlist_unhashed判為已hash。所以也可以對它調用hlist_del函數。
5、移動鏈表
此函數將本來以old為頭結點的鏈表移動成為以new為頭結點的鏈表。
6、鏈表結構體的入口
這兩個宏定義由某鏈表的頭結點獲得該結構體的首地址。
其中第二個宏定義先對ptr進行判斷，如果ptr是空指針，則返回NULL，如果其不是空指針才對其進行操作。
7、訪問哈希鏈表
這裡核心在於使用了container_of函數，在哈希鏈表中訪問我們需要的數據項。
第二個函數的操作更為安全，因為會在訪問之前對ptr指針進行是否為空的判斷。
8、遍歷哈希鏈表
這兩個宏定義對哈希鏈表進行遍歷。第二個比第一個更安全一些。因為第二個在遍歷時可以對pos進行刪除操作。
使用第一個宏定義時則不可以刪除pos，因為若在遍歷時執行刪除pos，會使pos->next無效而出錯。
9、用鏈表外指針遍歷哈希鏈表
我們可以看到，第一個函數是從鏈表頭開始進行遍歷。
第二個函數是從當前結點的下一個結點開始進行遍歷。
第三個函數是從當前結點開始進行遍歷。
而第四個函數可以在遍歷過程中對當前結點進行刪除操作，因為在對結點進行處理之前，結點的下一個指針信息已經被存儲。
閱讀更多 有理想的代碼dog 的文章
