關于哈希表，在核心裡設計兩個很重要的資料結構:
哈希連結清單節點：
點選(此處)折疊或打開
/*Kernel Version : 3.4.x [include/linux/types.h]*/
struct hlist_node {
struct hlist_node *next, **pprev;
};
可以看到哈希節點和核心普通雙向連結清單的節點唯一的差別就在于，前向節點pprev是個兩級指針，至于為什麼這樣設計而不采用struct list_head{}來作為哈希連結清單的節點，我們後面會詳細介紹。另外一個重要的資料結構是，哈希連結清單的表頭。
哈希連結清單表頭：
struct hlist_head {
struct hlist_node *first;
因為哈希連結清單并不需要<b>雙向循環</b>的技能，它一般适用于單向散列的場景。是以，為了減少開銷，并沒有用struct hlist_node{}來代表哈希表頭，而是重新設計struct hlist_head{}這個資料結構。此時，一個哈希表頭就隻需要4Byte了，相比于struct hlist_node{}來說，存儲空間已經減少了一半。這樣一來，在需要大量用到哈希連結清單的場景，其存儲空間的節約是非常明顯的，特别是在嵌入式裝置領域。
接下來，我們來重點回答一下哈希節點裡那個兩級指針的問題。先講個小插曲，記得本人當年剛參加工作時，導師給安排了一個活兒，那時候年輕氣盛、血氣方剛，沒一會兒功夫，三下五除二就搞定了。然後拿着自己的“傑作”去師傅看，師傅瞄了一眼說，你這函數簡直是一坨shi(和喬老爺當年罵另外一個程式員的用詞、語氣差不多)，誰讓你函數入參傳個三級指針進去的？這段代碼TM能維護麼？誰看得懂？完了之後感覺自己還受了莫大的委屈一樣，不過誰的人生沒有那麼點波瀾壯闊的過往呢，就像有句名言說的：程式寫出來是給人看的，順帶能在機器上運作。OK，那這個故事跟我們要介紹的哈希節點的關系在哪兒呢？沒錯，就是struct hlist_node{}裡那個前向的兩級指針的存在意義。
關于兩級指針的目的與意義，讓我們采用反證法來看看，如果struct
hlist_node{}被設計成如下一級指針的樣子，會發生什麼：
struct hlist_node *next, *pprev;
假如我們現在已經有一個哈希連結清單了myhlist(先别管這個連結清單是怎麼來的)，連結清單裡有4個節點node1~node4：
然後就有以下兩個問題跟着冒出來：
1)、在往哈希鍊myhlist裡插入node1時必須這麼寫：
mylist.first = node1;
node1->pprev=( struct hlist_node*)&mylist;
除此之外，在插入node2~node4以及後續其他節點時(假如按順序插入的話)，寫法如下（X>=2）：
node[X]->next = node[X+1];
node[X]->pprev = node[X-1];
簡而言之啥意思呢？往哈希連結清單裡插入元素時，如果在表頭的第一個位置上插入元素，和插入在哈希連結清單的其他位置上的代碼處理邏輯是不一樣的。因為哈希表頭是list_head類型，而其他節點都是list_node類型。
2)、同樣，如果删除節點時，對于非首節點，以node2為例：
node2->pprev->next = node2->next;
node2->next->pprev = node2->pprev;
如果要删除首節點node1呢，則寫法如下：
((struct hlist_head*)(node1->pprev))->first = node1->next;
node1->next->pprev = ( struct hlist_node*)&mylist; 或者 node1->next->pprev = node1->pprev;
很明顯，核心開發者們怎麼會容許這樣的代碼存在，而且還要充分考慮效率的問題。那麼，當hlist_node.pprev被設計成兩級指針後有啥好處？
還是以删除節點為例，如果要删除首節點，因為node1->pprev裡儲存的是myhlist的位址，而myhlist.first永遠都指向哈希連結清單的第一個節點，我們要間接改變表頭裡的hlist_node類型的first指針的值，能想到的最直接的辦法當然是二級指針，這是兩級指針的宿命所決定的，為了間接改變一級指針所指的記憶體位址的場景。這樣一來，node節點裡的pprev其實指向的是其前一個節點裡的第一個指針元素的位址。對于hlist_head來說，它裡面隻有一個指針元素，就是first指針；而對于hlist_node來說，第一個指針元素就是next。具體如下所示：
是以，記住，當我們在代碼中看到類似與*(hlist_node->pprev)這樣的代碼時，我們心裡應該清楚，此時正在哈希表裡操作目前節點前一個節點裡的第一個指針元素所指向的記憶體位址，隻是以間接的方式實作罷了。那麼回到删除哈希連結清單節點的場景，當删除首節點時，此時情況就變成了：
*(node1->pprev) = node1->next;
node1->next->pprev = node1->pprev;
删除非首節點的情況也一樣：
*(node2->pprev) = node2->next;
這樣一來，我們對hlist_node裡的諒解指針pprev的存在價值與意義應該很明白了，以後不至于再被眼花缭亂的取位址操作符給弄暈了。OK，扯了這麼多，讓我們看看核心是如何實作删除哈希連結清單裡的節點的__hlist_del()：
大家自行将上述函數裡的入參n換成node2，最終和我們上面推斷的結果是一緻的：
在标準的哈希連結清單裡，因為最後一個節點的next=NULL，是以在執行第二句有效代碼前首先要對目前節點的next值進行判斷才行。
核心提供了hlist_add_head()，用于實作向哈希連結清單裡插入節點：
hlist_add_head(struct hlist_node *n, struct hlist_head *h)
其中n表示待插入的節點，h表示哈希連結清單表頭。在剛初始化完哈希表myhlist的情況下，依次調用四次hlist_add_head()，每次調用後myhlist哈希表的情況如下：
(備注：雙箭頭表示兩級指針，單箭頭表示一級指針)
理論上說，核心應該再提供一個對稱的方法hlist_add_tail()才算完美，用于将哈希連結清單操作成如下的樣子：
還有hlist_add_behind()和hlist_add_before()，在3.17版本之前hlist_add_behind()的名字還是hlist_add_after()，不過作用都一樣。兩個函數原型分别如下：
hlist_add_before(struct hlist_node *n,struct hlist_node *next);
hlist_add_behind(struct hlist_node *n,struct hlist_node *prev);
其中n是待插入的節點，next或者prev都是n的相對位置參考節點，其作用分别是：
hlist_add_before()：在next節點的<b>前面</b>插入n節點；
hlist_add_behind()：在prev節點的<b>後面</b>插入n節點；
接下來，讓我們…..
1)、在node4節點的<b>前面</b>插入node3：
注意hlist_add_before()有個限制條件，那就是next!=NULL。
2)、在node1的節點<b>後面</b>插入node5：
同樣的限制條件也适用于hlist_add_behind()，即prev!=NULL。
未完，待續...