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。