ngx_hash_t是nginx自己的hash表的實現。定義和實現位于src/core/ngx_hash.h|c中。ngx_hash_t的實現也與數據結構教科書上所描述的hash表的實現是大同小異。對于常用的解決沖突的方法有線性探測，二次探測和開鏈法等。ngx_hash_t使用的是最常用的一種，也就是開鏈法，這也是STL中的hash表使用的方法。 但是ngx_hash_t的實現又有其幾個顯著的特點: 1. ngx_hash_t不像其他的hash表的實現，可以插入刪除元素，它只能一次初始化，就構建起整個hash表以后，既不能再刪除，也不能在插入元素了。 1. ngx_hash_t的開鏈并不是真的開了一個鏈表，實際上是開了一段連續的存儲空間，幾乎可以看做是一個數組。這是因為ngx_hash_t在初始化的時候，會經歷一次預計算的過程，提前把每個桶里面會有多少元素放進去給計算出來，這樣就提前知道每個桶的大小了。那么就不需要使用鏈表，一段連續的存儲空間就足夠了。這也從一定程度上節省了內存的使用。 從上面的描述，我們可以看出來，這個值越大，越造成內存的浪費。就兩步，首先是初始化，然后就可以在里面進行查找了。下面我們詳細來看一下。 ngx_hash_t的初始化。 [](http:// "點擊提交Issue,反饋你的意見...") ngx_int_t ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, ngx_uint_t nelts); 首先我們來看一下初始化函數。該函數的第一個參數hinit是初始化的一些參數的一個集合。 names是初始化一個ngx_hash_t所需要的所有key的一個數組。而nelts就是key的個數。下面先看一下ngx_hash_init_t類型，該類型提供了初始化一個hash表所需要的一些基本信息。 [](http:// "點擊提交Issue,反饋你的意見...") typedef struct { ngx_hash_t *hash; ngx_hash_key_pt key; ngx_uint_t max_size; ngx_uint_t bucket_size; char *name; ngx_pool_t *pool; ngx_pool_t *temp_pool; } ngx_hash_init_t; | hash: | 該字段如果為NULL，那么調用完初始化函數后，該字段指向新創建出來的hash表。如果該字段不為NULL，那么在初始的時候，所有的數據被插入了這個字段所指的hash表中。 | |-----|-----| | key: | 指向從字符串生成hash值的hash函數。nginx的源代碼中提供了默認的實現函數ngx_hash_key_lc。 | | max_size: | hash表中的桶的個數。該字段越大，元素存儲時沖突的可能性越小，每個桶中存儲的元素會更少，則查詢起來的速度更快。當然，這個值越大，越造成內存的浪費也越大，(實際上也浪費不了多少)。 | | bucket_size: | 每個桶的最大限制大小，單位是字節。如果在初始化一個hash表的時候，發現某個桶里面無法存的下所有屬于該桶的元素，則hash表初始化失敗。 | | name: | 該hash表的名字。 | | pool: | 該hash表分配內存使用的pool。 | | temp_pool: | 該hash表使用的臨時pool，在初始化完成以后，該pool可以被釋放和銷毀掉。 | 下面來看一下存儲hash表key的數組的結構。 [](http:// "點擊提交Issue,反饋你的意見...") typedef struct { ngx_str_t key; ngx_uint_t key_hash; void *value; } ngx_hash_key_t; key和value的含義顯而易見，就不用解釋了。key_hash是對key使用hash函數計算出來的值。 對這兩個結構分析完成以后，我想大家應該都已經明白這個函數應該是如何使用了吧。該函數成功初始化一個hash表以后，返回NGX_OK，否則返回NGX_ERROR。 [](http:// "點擊提交Issue,反饋你的意見...") void *ngx_hash_find(ngx_hash_t *hash, ngx_uint_t key, u_char *name, size_t len); 在hash里面查找key對應的value。實際上這里的key是對真正的key（也就是name）計算出的hash值。len是name的長度。 如果查找成功，則返回指向value的指針，否則返回NULL。