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

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

雖然數(shù)組的查詢速度很快，但是數(shù)組的索引值必須是數(shù)值，這就很討厭了。
因?yàn)楹芏嗲闆r下，索引值并不是數(shù)字，而是字符串什么的。比如用名字來(lái)索引一個(gè)人。

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

這個(gè)解決方法中有兩個(gè)主要部分：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ngx_hash_t用來(lái)表示整個(gè)hash表。

通過(guò)buckets這個(gè)指針的指針可以完整的訪問(wèn)二維數(shù)組。

Nginx中是如何使用這兩個(gè)數(shù)據(jù)結(jié)構(gòu)的呢？或者簡(jiǎn)化一下，Nginx是如何初始化這兩個(gè)數(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申請(qǐng)空間，用于存放管理結(jié)構(gòu)體ngx_hash_t及4個(gè) ngx_hash_elt_t指針
hash = ngx_pcalloc(pool, sizeof(ngx_hash_t) + 4*sizeof(ngx_hash_elt_t *));

u_char *elts;
// 向ngx_pool_t申請(qǐng)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個(gè)ngx_hash_elt_t指針指向正確地址；
    elts += 2 * sizeof(ngx_hash_elt_t);
}
hash->buckets = buckets;
hash->size = 4;

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

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

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

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

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

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