Nginx實現(xiàn)的hash表和常見的hash表大體一致，細(xì)節(jié)有區(qū)別，所以，要了解ngx_hash_t最好對hash表的基礎(chǔ)概念進行一下梳理。

從查詢的角度來看，數(shù)組根據(jù)索引值的查詢速度很快快。
原因在于數(shù)組內(nèi)元素的位置是基于數(shù)組起始位置的絕對位置，而且數(shù)組的存儲空間是連續(xù)的，可以根據(jù)下標(biāo)直接操作指針跳轉(zhuǎn)。

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

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

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

建立從名字到學(xué)號的對應(yīng)關(guān)系；

建立以學(xué)號為索引值的數(shù)組；

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

只要有了f(k)，那么將f(k)作為數(shù)組的下標(biāo)即可獲取k所對應(yīng)的信息。
即

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

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

理想是豐滿的，現(xiàn)實是骨感的。hash表在建立時最關(guān)鍵之處在于找到合適的哈希函數(shù)，使得：

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

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

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

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

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

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

具體內(nèi)容請自行g(shù)oogle，這里就不去挖老墳了。

從上述的分析可知，建立哈希表有兩個主要環(huán)節(jié)：

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

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

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

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

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

從上述分析，可知，hash表是一種拿空間換取時間的數(shù)據(jù)結(jié)構(gòu)。
關(guān)于hash表的各種實現(xiàn)方法及算法的算法復(fù)雜度，請自行g(shù)oogle。

需要指出的是，Nginx中自造的哈希表屬于內(nèi)部使用的數(shù)據(jù)結(jié)構(gòu)，因此，并不是一個通用的哈希表。此外，為了提高效率，作者做了相當(dāng)多的優(yōu)化，這些優(yōu)化使得Nginx中的哈希表與常規(guī)的哈希表長得不一樣。

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

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

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

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

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

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

Nginx的哈希表在內(nèi)存上大概是長這個樣子的：

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

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

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

所以，在內(nèi)存上，Nginx哈希表的本尊，就是一段連續(xù)的內(nèi)存空間，此外，還需要兩個用來管理這段內(nèi)存空間的數(shù)據(jù)結(jié)構(gòu)。

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

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

因此，Nginx哈希表的核心數(shù)據(jù)結(jié)構(gòu)如下：

ngx_hash_elt_t用來表示hash表的元素。

ngx_hash_t用來表示整個hash表。

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

Nginx中是如何使用這兩個數(shù)據(jù)結(jié)構(gòu)的呢？或者簡化一下，Nginx是如何初始化這兩個數(shù)據(jù)結(jié)構(gòu)的呢？

首先，作為管理內(nèi)存的結(jié)構(gòu)體，ngx_hash_t既可以作為局部變量在棧上出現(xiàn)，也可以作為堆上的變量，使用ngx_pool_t管理。

以堆為例，

ngx_hash_t  *hash;
// 向ngx_pool_t申請空間，用于存放管理結(jié)構(gòu)體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表本身使用的連續(xù)內(nèi)存塊
elts = ngx_palloc(pool, 4 * 2 * sizeof(ngx_hash_elt_t));

ngx_hash_elt_t **buckets;
// 將管理結(jié)構(gòu)體成員變量賦于正確的值。
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;

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

這樣就把管理hash表那段連續(xù)內(nèi)存塊使用的ngx_hash_elt_t** buckets及ngx_hash_elt_t*數(shù)組一起創(chuàng)建了。

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

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

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

細(xì)節(jié)部分，后續(xù)添加。先到這里。