摘要：现在使用的各种哈希函数基本上只能保证较小概率出现两个不同的其相同的情况。而出现两个值对应的相同的情况，称为哈希冲突。中的哈希表需要指出的是，中自造的哈希表属于内部使用的数据结构，因此，并不是一个通用的哈希表。
源文件路径
版本：1.8.0
csrccoreNgx_hash.h srccoreNgx_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的哈希表用于解决类似于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表。主要目的在于理清整体框架及思路。
细节部分，后续添加。先到这里。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/7839.html
摘要：现在使用的各种哈希函数基本上只能保证较小概率出现两个不同的其相同的情况。而出现两个值对应的相同的情况，称为哈希冲突。中的哈希表需要指出的是，中自造的哈希表属于内部使用的数据结构，因此，并不是一个通用的哈希表。 源文件路径 版本：1.8.0 csrccoreNgx_hash.h srccoreNgx_hash.c 关于hash表 Nginx实现的hash表和常见的hash表大体...
摘要：现在使用的各种哈希函数基本上只能保证较小概率出现两个不同的其相同的情况。而出现两个值对应的相同的情况，称为哈希冲突。中的哈希表需要指出的是，中自造的哈希表属于内部使用的数据结构，因此，并不是一个通用的哈希表。 源文件路径 版本：1.8.0 csrccoreNgx_hash.h srccoreNgx_hash.c 关于hash表 Nginx实现的hash表和常见的hash表大体...
摘要：本篇的上篇为源码分析上。主体思路分析中使用的哈希函数，围绕初始化时使用的结构体展开。这样得到一个关于请求的首部哈希数组。源码中大多数的代码是跟预估表大小相关的。的哈希表的核心是表的管理结构体数组及表内存空间分配。 本篇的上篇为 Nginx 源码分析：ngx_hash_t（上）。 建议先读完上篇再来读下篇。 上篇回顾了hash表的基础概念，分析了Nginx中hash表的内存模型及逻辑...
摘要：本篇的上篇为源码分析上。主体思路分析中使用的哈希函数，围绕初始化时使用的结构体展开。这样得到一个关于请求的首部哈希数组。源码中大多数的代码是跟预估表大小相关的。的哈希表的核心是表的管理结构体数组及表内存空间分配。 本篇的上篇为 Nginx 源码分析：ngx_hash_t（上）。 建议先读完上篇再来读下篇。 上篇回顾了hash表的基础概念，分析了Nginx中hash表的内存模型及逻辑...
摘要：本篇的上篇为源码分析上。主体思路分析中使用的哈希函数，围绕初始化时使用的结构体展开。这样得到一个关于请求的首部哈希数组。源码中大多数的代码是跟预估表大小相关的。的哈希表的核心是表的管理结构体数组及表内存空间分配。 本篇的上篇为 Nginx 源码分析：ngx_hash_t（上）。 建议先读完上篇再来读下篇。 上篇回顾了hash表的基础概念，分析了Nginx中hash表的内存模型及逻辑...
阅读 566·2021-11-18 10:02
阅读 2172·2021-11-11 16:54
阅读 2575·2021-09-02 09:45
阅读 480·2019-08-30 12:52
阅读 2457·2019-08-29 14:04
阅读 2622·2019-08-29 12:39
阅读 285·2019-08-29 12:27
阅读 1756·2019-08-26 13:23
