Nginx實現的hash表和常見的hash表大體一致，細節有區別，所以，要了解ngx_hash_t最好對hash表的基礎概念進行一下梳理。

從查詢的角度來看，數組根據索引值的查詢速度很快快。
原因在于數組內元素的位置是基于數組起始位置的絕對位置，而且數組的存儲空間是連續的，可以根據下標直接操作指針跳轉。

雖然數組的查詢速度很快，但是數組的索引值必須是數值，這就很討厭了。
因為很多情況下，索引值并不是數字，而是字符串什么的。比如用名字來索引一個人。

解決這個問題的一個很容易的辦法就是給每個人安排一個學號（先不考慮重名的情況），那么，在實際存儲時，按照學號為索引值的數組來存儲對應的信息；在查詢時，只需要知道名字，就可以得到名字對應的學號，根據學號可以直接從數組中取出信息。

這個解決方法中有兩個主要部分：

建立從名字到學號的對應關系；

建立以學號為索引值的數組；

從名字到學號的對應關系可以抽象成從字符串到數值的對應關系，這種對應關系，在數學上表示就是f(k)。其中k表示一個字符串（索引關鍵字），函數f表示從字符串到數值的對應關系，f(k)表示k經過f映射得到的值。

只要有了f(k)，那么將f(k)作為數組的下標即可獲取k所對應的信息。
即

k------>f(k)------->info[f(k)]

其中，從k到f(k)的映射函數稱為哈希函數，數組info[]稱為哈希（hash）表。

理想是豐滿的，現實是骨感的。hash表在建立時最關鍵之處在于找到合適的哈希函數，使得：

k與f(k)之間是一一映射的。即，保證給定對于k存在唯一的f(k)與之對應，同時對于f(k)存在唯一的k與之對應。

f(k)的集合是連續的。即，對于數組info[]而言，不存在數組項為空的情況，可以更加充分利用資源。

可惜，滿足上述條件的哈希函數非常困難。
現在使用的各種哈希函數基本上只能保證較小概率出現兩個不同的k其f(k)相同的情況。
基本不能保證f(k)的集合是連續的。

因為f(k)的集合不是連續的，所以哈希表也被稱為散列表，哈希函數也被稱為散列函數。
而出現兩個k值對應的f(k)相同的情況，稱為哈希沖突。

解決哈希沖突常見的辦法
出現散列情況表示可能浪費一點資源，這是可以接受的。但是出現沖突表示會發生信息覆蓋，這是錯誤，不能接受。所以，必須解決哈希沖突。

解決哈希沖突的常見的方法有：
1) 開放地址法；2）再哈希法；3）鏈地址法；

具體內容請自行google，這里就不去挖老墳了。

從上述的分析可知，建立哈希表有兩個主要環節：

1）建立哈希函數；
2）建立哈希表（都是窟窿的數組）

其中，為了解決哈希沖突（假設采用鏈地址法），所建立的哈希表（數組）里的元素可能是一個鏈表或者一個數組。也就是說，哈希表是一個二維的結構。
同時，對于索引關鍵字，要求哈希函數獲得的哈希值控制在一定范圍內。

因此，哈希表大概長成這個樣子：

其中hashtable表示哈希表，key表示索引值，比如上述例子中某個學生的名字，node_t表示哈希表中存儲的信息，同時也可以看到node_t是鏈表的一個節點，用于解決哈希沖突。

假設key的值是字符串"xiaoming"，根據某個哈希函數，得出的值為6，那么"xiaoming"的信息就可以從hashtable[6]鏈表中取得，這樣再去遍歷hashtable[6]這個鏈表，找到key等于"xiaoming"的鏈表節點，其val就是要查找的值。

從上述分析，可知，hash表是一種拿空間換取時間的數據結構。
關于hash表的各種實現方法及算法的算法復雜度，請自行google。

需要指出的是，Nginx中自造的哈希表屬于內部使用的數據結構，因此，并不是一個通用的哈希表。此外，為了提高效率，作者做了相當多的優化，這些優化使得Nginx中的哈希表與常規的哈希表長得不一樣。

例如，Nginx的哈希表一經初始化就不可更改，既不能增加元素，也不能刪除元素。
這樣做主要是因為Nginx的哈希表用于解決類似于http模塊中域名匹配的問題，這些域名在配置文件中配置，一旦讀取配置文件，這些信息是不可修改的，因此，沒有增刪的需求。

另外，由于Nginx哈希表的這種只讀特點，使得可以在性能上有很大的可優化空間。
而Nginx也確實在這上面作了很多文章。

根據哈希表的概念可知：哈希表本身就是一個數組，因此，是一塊連續的內存空間。
在Nginx中，內存的管理都是通過ngx_pool_t來管理的（不清楚的請移步這里）,因此，需要一個用來管理這塊連續內存的結構體。

但是由于哈希表為了解決沖突問題，通常采用鏈地址法，所以，這個管理內存的結構體會使用指針的指針。

另外，由于Nginx的哈希表是只讀的，沖突的元素個數可以在初始化是確定，所以使用數組來代替鏈表解決沖突是更優的選擇。

這個用來代替鏈表的數組還有個名字叫hash桶，所以，會在Nginx源碼中看到buckets這樣的命名。

Nginx的哈希表在內存上大概是長這個樣子的：

假設理想情況，所有的索引值key經過哈希函數映射后f(k)集合的大小為4。

為了解決沖突，我們將每個f(k)對應的數組大小設定為2。這樣，我們的hash表在邏輯上就變成了一個4x2的數組。

當然，為了更好的說明情況，這里假設哈希函數是理想的，因此，hash表不存在未使用的部分。

所以，在內存上，Nginx哈希表的本尊，就是一段連續的內存空間，此外，還需要兩個用來管理這段內存空間的數據結構。

1）大小為4的數組，類型為ngx_hash_elt_t *，用來分別指向不同的內存段，表示每個hash桶。
2）類型為ngx_hash_elt_t **的指針buckets，用來表示hash桶數組。

由于指針的指針可以完整的表示二維數組，因此，ngx_hash_elt_t *數組并不需要定義。只需定義ngx_hash_elt_t來表示hash表中的每個元素即可。

因此，Nginx哈希表的核心數據結構如下：

ngx_hash_elt_t用來表示hash表的元素。

ngx_hash_t用來表示整個hash表。

通過buckets這個指針的指針可以完整的訪問二維數組。

Nginx中是如何使用這兩個數據結構的呢？或者簡化一下，Nginx是如何初始化這兩個數據結構的呢？

首先，作為管理內存的結構體，ngx_hash_t既可以作為局部變量在棧上出現，也可以作為堆上的變量，使用ngx_pool_t管理。

以堆為例，

ngx_hash_t  *hash;
// 向ngx_pool_t申請空間，用于存放管理結構體ngx_hash_t及4個 ngx_hash_elt_t指針
hash = ngx_pcalloc(pool, sizeof(ngx_hash_t) + 4*sizeof(ngx_hash_elt_t *));

u_char *elts;
// 向ngx_pool_t申請hash表本身使用的連續內存塊
elts = ngx_palloc(pool, 4 * 2 * sizeof(ngx_hash_elt_t));

ngx_hash_elt_t **buckets;
// 將管理結構體成員變量賦于正確的值。
for (i = 0; i < 4; i++) {
    buckets[i] = (ngx_hash_elt_t *) elts;  // 4個ngx_hash_elt_t指針指向正確地址；
    elts += 2 * sizeof(ngx_hash_elt_t);
}
hash->buckets = buckets;
hash->size = 4;

這段代碼，在內存池中申請了一段連續的內存，分別用于1個ngx_hash_t和4個ngx_hash_elt_t *。

這樣就把管理hash表那段連續內存塊使用的ngx_hash_elt_t** buckets及ngx_hash_elt_t*數組一起創建了。

然后依次給每個ngx_hash_elt_t *賦值，使其指向正確的內存地址。

說明
以上代碼自Nginx源碼中簡化而來，去除了許多用于優化的代碼。

由于ngx_hash_t內容較多，這里只從設計角度分析了Nginx中的hash表。主要目的在于理清整體框架及思路。

細節部分，后續添加。先到這里。