转载

Nginx 源码分析：ngx_hash_t（上）

源文件路径

版本：1.8.0

csrc/core/Ngx_hash.h src/core/Ngx_hash.c

关于hash表

Nginx 实现的hash表和常见的hash表大体一致，细节有区别，所以，要了解 ngx_hash_t 最好对hash表的基础概念进行一下梳理。

数组与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表的问题及解决方法

理想是丰满的，现实是骨感的。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）建立哈希表（都是窟窿的数组）

其中，为了解决哈希冲突（假设采用链地址法），所建立的哈希表（数组）里的元素可能是一个链表或者一个数组。也就是说，哈希表是一个二维的结构。同时，对于索引关键字，要求哈希函数获得的哈希值控制在一定范围内。

因此，哈希表大概长成这个样子：

ctypedef struct node_s{  char    *key;  char    *val;  node_t  *next; }node_t; #define HASHSIZE 101 node_t* hashtable[HASHSIZE];

其中 hashtable 表示哈希表， key 表示索引值，比如上述例子中某个学生的名字， node_t 表示哈希表中存储的信息，同时也可以看到 node_t 是链表的一个节点，用于解决哈希冲突。

假设 key 的值是字符串 "xiaoming" ，根据某个哈希函数，得出的值为 6 ，那么 "xiaoming" 的信息就可以从 hashtable[6] 链表中取得，这样再去遍历 hashtable[6] 这个链表，找到 key 等于 "xiaoming" 的链表节点，其 val 就是要查找的值。

从上述分析，可知，hash表是一种拿空间换取时间的数据结构。关于hash表的各种实现方法及算法的算法复杂度，请自行google。

`Nginx` 中的哈希表

需要指出的是， 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表的元素。

ctypedef struct {     void             *value;     u_short           len;     u_char            name[1]; } ngx_hash_elt_t;

ngx_hash_t用来表示整个hash表。

ctypedef struct {     ngx_hash_elt_t  **buckets;     ngx_uint_t        size; } ngx_hash_t;

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

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

正文到此结束