Nginx 源码分析：ngx_hash_t（上）

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表。主要目的在于理清整体框架及思路。

细节部分，后续添加。先到这里。