前言：
1.基本概念：
散列表（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。
2. 常用的構造散列函數的方法
散列函數能使對一個數據序列的訪問過程更加迅速有效，通過散列函數，數據元素將被更快地定位。散列表的常用構造方法有：
(1)直接定址法
(2)數字分析法
(3)平方取中法
(4)折疊法
(5)隨機數法
(6)除留余數法
3、處理沖突的方法
散列表函數設計好的情況下，可以減少沖突，但是無法完全避免沖突。常見有沖突處理方法有：
(1)開放定址法
(2)再散列法
(3)鏈地址法(拉鏈法)
(4)建立一個公共溢出區
4. 散列表查找性能分析
散列表的查找過程基本上和造表過程相同。一些關鍵碼可通過散列函數轉換的地址直接找到，另一些關鍵碼在散列函數得到的地址上產生了沖突，需要按處理沖突的方法進行查找。在介紹的三種處理沖突的方法中，產生沖突後的查找仍然是給定值與關鍵碼進行比較的過程。所以，對散列表查找效率的量度，依然用平均查找長度來衡量。
查找過程中，關鍵碼的比較次數，取決於產生沖突的多少，產生的沖突少，查找效率就高，產生的沖突多，查找效率就低。因此，影響產生沖突多少的因素，也就是影響查找效率的因素。影響產生沖突多少有以下三個因素：
1. 散列函數是否均勻；
2. 處理沖突的方法；
3. 散列表的裝填因子。
散列表的裝填因子定義為：α= 填入表中的元素個數 / 散列表的長度。
α是散列表裝滿程度的標志因子。由於表長是定值，α與“填入表中的元素個數”成正比，所以，α越大，填入表中的元素較多，產生沖突的可能性就越大；α越小，填入表中的元素較少，產生沖突的可能性就越小。實際上，散列表的平均查找長度是裝填因子α的函數，只是不同處理沖突的方法有不同的函數。
一.Linux內核哈希表數據結構
hash最重要的是選擇適當的hash函數，從而平均的分配關鍵字在桶中的位置，從而優化查找 插入和刪除所用的時間。然而任何hash函數都會出現沖突問題。內核采用的解決哈希沖突的方法是：拉鏈法拉鏈法解決沖突的做法是：將所有關鍵字為同義詞的結點鏈接在同一個鏈表中。若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針（struct hlist_head name）組成的指針數組T[0..m-1]。凡是散列地址為i的結點，均插入到以T[i]為頭指針的鏈表中。T中各分量的初值均應為空指針。在拉鏈法中，裝填因子α(裝填的元素個數/數組長度)可以大於 1，但一般均取α≤1。當然，用拉鏈法解決hash沖突也是有缺點的，指針需要額外的空間。
1. 其代碼位於include/linux/list.h中，3.0內核中將其數據結構定義放在了include/linux/types.h中
哈希表的數據結構定義：
如圖：
struct hlist_head{
struct hlist_node *first;
}
struct hlist_node {
struct hlist_node *next,**pprev;
}
1>hlist_head表示哈希表的頭結點。哈希表中每一個entry(list_entry)所對應的都是一個鏈表（hlist）.hlist_head結構體只有一個域，即first。First指針指向該hlist鏈表的第一個結點。
2>hlist_node結構體有兩個域，next和pprev。
(1)next指向下個hlist_node結點，倘若改結點是鏈表的最後一個節點，next則指向NULL
(2)pprev是一個二級指針，它指向前一個節點的next指針。
2.Linux 中的hlist(哈希表)和list是不相同的，在list中每個結點都是一樣的，不管頭結點還是其它結點，使用同一個結構體表示，但是在hlist中，頭結點使用的是struct hlist_head來表示的，而對於其它結點使用的是strcuct hlist_node這個數據結果來表示的。還有list是雙向循環鏈表，而hlist不是雙向循環鏈表。因為hlist頭結點中沒有prev變量。為什麼要這樣設計呢？
散列表的目的是為了方便快速的查找，所以散列表通常是一個比較大的數組，否則“沖突”的概率會非常大，這樣就失去了散列表的意義。如何來做到既能維護一張大表，又能不占用過多的內存呢?此時只能對於哈希表的每個entry(表頭結點)它的結構體中只能存放一個指針。這樣做的話可以節省一半的指針空間，尤其是在hash bucket很大的情況下。（如果有兩個指針域將占用8個字節空間）
3.hlist的結點有兩個指針，但是pprev是指針的指針，它指向的是前一個結點的next指針，為什麼要采用pprev，二不采用一級指針？
由於hlist不是一個完整的循環鏈表，在list中，表頭和結點是同一個數據結構，直接用prev是ok的。在hlist中，表頭中沒有prev，只有一個first。
1>為了能統一地修改表頭的first指針，即表頭的first指針必須修改指向新插入的結點，hlist就設計了pprev。list結點的pprev不再是指向前一個結點的指針，而是指向前一個節點（可能是表頭）中的next(對於表頭則是first)指針,從而在表頭插入的操作中可以通過一致的node->pprev訪問和修改前結點的next（或first）指針。
2>還解決了數據結構不一致，hlist_node巧妙的將pprev指向上一個節點的next指針的地址，由於hlist_head和hlist_node指向的下一個節點的指針類型相同，就解決了通用性。
