本文主要是介绍nginx的通配符哈希表--ngx_hash_wildcard_t，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
概述 nginx的哈希表的一个重要的应用场景是虚拟主机server name 的匹配，因此除了提供常规的哈希表匹配操作符，基于通配符的哈希表也就必不可少了
nginx基于通配符的哈希表
nginx支持哈希表通过"www.techlog.*" 或"*.techlog.cn"这样的前缀或后缀通配符关键字对哈希表进行查找， 事实上，这是通过一个数据结构ngx_hash_wildcard_t实现的， 可以看到ngx_hash_wildcard_t仅仅是对ngx_hash_t的一个简单的封装：
//struct ngx_hash_wildcard_t
//支持通配符的散列表
typedef struct {
ngx_hash_t hash ;
void *value;
}ngx_hash_wildcard_t;
而支持前缀、后缀匹配的结构体正是通过它实现的；
//struct ngx_hash_combined_t
//通配符散列结构
typedef struct {
ngx_hash_t hash ;
ngx_hash_wildcard_t *wc_head;
ngx_hash_wildcard_t *wc_tail;
}ngx_hash_combined_t;
在实际的使用中，hash指向的哈希表存储了完整的字段，而wc_head指向的散列表中则存储了每个关键字的前缀（首个.前面的部分）后逆置的URL如（www.techlog.cn转化为cn.techlog）,而wc_tail指向的散列表则存储了去除尾缀的URL（如www.techlog.cn转换为www.techlog）,这样，通过对关键字进行一个简单的处理并在相应的散列表中匹配，即可实现支持首位通配符的散列表查询了
ngx_hash_key_t结构的初始化结构--ngx_hash_keys_arrays_t
//struct ngx_hash_keys_arrays_t
//用于初始化通配符散列结构的数据结构
typedef struct {
// 下面 6 个数组每个数组的元素个数
ngx_uint_t hsize;
// 用于分配空间的内存池结构
ngx_pool_t *pool; //内存池，用于分配永久性的内存
ngx_pool_t *temp_pool; //临时内存池，下面的临时动态数组都是好由临时内存池分配
// 存储完整匹配关键字的 ngx_str_t 结构动态数组，存放所有的非通配符key数组
ngx_array_t keys;
// 存储完整匹配关键字的 ngx_hash_key_t 结构动态数组，这是一个二维数组，第一维代表的是bucket的编号，那么keys_hash[i]中存放的是所有的key算出来的hash值对size取模以后的值为i的key。假设有3个key，分别是key1,key2和key3假设hash的值算出来以后对hsize取模的值都是i，那么这三个key的就顺序///存放在keys_hash[i][0],keys_hash[i][1],keys_hash[i][2]。该值在调用过程来保存和检验是否有冲突的key值，也就是是否有重复
ngx_array_t *keys_hash;
// 存储前缀匹配关键字的 ngx_str_t 结构动态数组。比如"*,abc.com"被处理完成以后，变成"come.abc"被存放在此数组中
ngx_array_t dns_wc_head;
// 存储前缀匹配关键字的 ngx_hash_key_t 结构动态数组，该值在调用的过程中用来保存和检测是否有冲突的前向通配符的key值，也就是是否有重复
ngx_array_t *dns_wc_head_hash;
// 存储后缀匹配关键字的 ngx_str_t 结构动态数组。比如:"mail.xxx.*"被处理完成以后，变成"mail.xxx."被存放在此数组中
ngx_array_t dns_wc_tail;
// 存储后缀匹配关键字的 ngx_hash_key_t 结构动态数组。该值在调用过程中用来保存和检测是否有冲突的后向统配符的key值，也就是是否有重复
ngx_array_t *dns_wc_tail_hash;
} ngx_hash_keys_arrays_t; // }}}
通配符散列表的初始化--ngx_hash_wildcard_init
首先看一下ngx_hash_wildcard_init的内存结构，当构造此类型的hash表的时候，实际上是构造了表的讴个hash表的一个“链表”，是通过hash表中的key“链接“起来的。比如:对于"*.abc.com"会构造出2个hash表，第一个hash表中有一个key为com的表项，该表项的value包含有指向第二个人hash表的指针，而第二个hash表中有一个表项abc,该表项的value包含有指向*.abc.com对应的value的指针。那么查询的时候，比如查询www.abc.com的时候，先查com,通过查com可以找到第二级的hash表，在第二级hash表中，再查找abc，依次类推，直到某一级的hash表中查找到的表项对应的value对应一个真正的值而非一个指向下一级hash表的指针的时候，查询过程结束
源代码，ngx_hash_wildcard是一个递归函数，递归创建上图的hash链表，如下注释
精彩的读点有：
由于指针都字节对齐了，底4位肯定为0，这种操作（name->value=(void *)((uitptr_t)wdc|(dot ? 3:2)))巧妙的使用了指针的的低位携带额外信息，节省了内存，
name->value = (void *) ((uintptr_t) wdc | (dot ? 3 : 2));
name->value = (void *) ((uintptr_t) name->value | 1);
这两行代码分别在不同的情况下执行
ngx_hash_wildcard_t value 尾部2位取值
取值 意义
01 无下一级哈希
10 指向最后一集哈希
11 后续还很很多级哈希
这篇关于nginx的通配符哈希表--ngx_hash_wildcard_t的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
