1. 散列表（即哈希表概念）
散列表是根据元素的关键码值而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，
以加快查找速度。这个映射函数 f 叫做散列方法，存放记录的数组叫做散列表。
若结构中存在关键字和 K 相等的记录，则必定在 f(K) 的存储位置上。由此，不需要比较便可直接取得所查记录。我们称这
个对应关系 f 为散列方法，按这个思想建立的表则为散列表。
对于不同的关键字，可能得到同一散列地址，即关键码 key1 ≠ key2，而 f(key1) = f(key2)，这种现象称为碰撞。对该散列
方法来说，具有相同函数值的关键字称作同义词。综上所述，根据散列方法 H(key) 和处理碰撞的方法将一组关键字映像到一
个有限的连续的地址集（区间）上，并以关键字在地址集中的 "象" 作为记录在表中的存储位置，这种表便称为散列表，这一
映像过程称为散列造表或散列，所得的存储位置称为散列地址。
1.1 如何解决碰撞问题
通常有两个简单的解决方法：分离链接法和开放寻址法。
分离链接法，就是把散列到同一个槽中的所有元素都放在散列表外的一个链表中，这样查询元素时，在找到这个槽后，还得遍
历链表才能找到正确的元素，以此来解决碰撞问题。
开放寻址法，即所有元素都存放在散列表中，当查找一个元素时，要检查规则内的所有表项（例如，连续的非空槽或者整个空
间内符合散列方法的所有槽），直到找到所需的元素，或者最终发现元素不在表中。开放寻址法中没有链表，也没有元素存放
在散列表外。
Nginx 的散列表使用的是开放寻址法。
开放寻址法有许多种实现方法，Nginx 使用的是连续非空槽存储碰撞元素的方法。例如，当插入一个元素时，可以按照散列方
法找到指定槽，如果该槽非空且其存储的元素与待插入元素并非同一个元素，则依次检查其后连续的槽，直到找到一个空槽来
放置这个元素为止。查询元素时也是使用类似的方法，即从散列方法指定的位置起检查连续的非空槽中的元素。
2. Nginx 散列表的实现
2.1 ngx_hash_elt_t 结构体
对于散列表中的元素，Nginx 使用 ngx_hash_elt_t 结构体来存储。
1typedef struct { 2 /* 指向用户自定义元素数据的指针，如果当前 ngx_hash_elt_t 槽为空，则 value 的值为 0 */ 3 void *value; 4 /* 元素关键字的长度 */ 5 u_short len; 6 /* 元素关键字的首地址 */ 7 u_char name[1]; 8} ngx_hash_elt_t;
每一个散列表槽都由 1 个 ngx_hash_elt_t 结构体表示，当然，这个槽的大小与 ngx_hash_elt_t 结构体的大小（即
sizeof(ngx_hash_elt_t)）是不相等的，这是因为 name 成员只用于指出关键字的首地址，而关键字的长度是可变的。一个槽
占用多大的空间是在初始化散列表时决定的。
2.2 ngx_hash_t 结构体
基本的散列表由 ngx_hash_t 结构体表示。
1typedef struct { 2 /* 指向散列表的首地址，也是第 1 个槽的地址 */ 3 ngx_hash_elt_t **buckets; 4 /* 散列表中槽的总数 */ 5 ngx_uint_t size; 6} ngx_hash_t;
因此，在分配 buckets 成员时就决定了每个槽的长度（限制了每个元素关键字的最大长度），以及整个散列表所占用的空
间。
基本散列表的结构示意图
如上图，散列表的每个槽的首地址都是 ngx_hash_elt_t 结构体，value 成员指向用户有意义的结构体，而 len 是当前这
个槽中 name（也就是元素的关键字）的有效长度。ngx_hash_t 散列表的 buckets 指向了散列表的起始地址，而 size 指出
散列表中槽的总数。
2.3 ngx_hash_init_t 结构体
1typedef struct { 2 /* 指向普通的完全匹配散列表 */ 3 ngx_hash_t *hash; 4 5 /* 用于初始化添加元素的散列方法 */ 6 ngx_hash_key_pt key; 7 8 /* 散列表中槽的最大数目 */ 9 ngx_uint_t max_size; 10 /* 散列表中一个槽的大小，它限制了每个散列表元素关键字的最大长度 */ 11 ngx_uint_t bucket_size; 12 13 /* 散列表的名称 */ 14 char *name; 15 /* 内存池，用于分配散列表（最多3个，包括1个普通散列表、1个前置通配符散列表、1个后置通配符散列表） 16 * 中的所有槽 */ 17 ngx_pool_t *pool; 18 /* 临时内存池，仅存在于初始化散列表之前。它主要用于分配一些临时的动态数组， 19 * 带通配符的元素在初始化时需要用到这些数组 */ 20 ngx_pool_t *temp_pool; 21} ngx_hash_init_t;
该结构体用于初始化一个散列表。
2.4 ngx_hash_key_t 结构体
1typedef struct { 2 /* 元素关键字 */ 3 ngx_str_t key; 4 /* 由散列方法算出来的关键码 */ 5 ngx_uint_t key_hash; 6 /* 指向实际的用户数据 */ 7 void *value; 8}ngx_hash_key_t;
2.3 ngx_hash_init()：初始化一个基本散列表
1/* 计算该实际元素 name 所需的内存空间(有对齐处理)，而 sizeof(void *) 就是结束哨兵的所需内存空间 */ 2#define NGX_HASH_ELT_SIZE(name) \ 3 (sizeof(void *) + ngx_align((name)->key.len + 2, sizeof(void *))) 4 5/* 6 * @hinit：该指针指向的结构体中包含一些用于建立散列表的基本信息 7 * @names：元素关键字数组，该数组中每个元素以ngx_hash_key_t作为结构体，存储着预添加到散列表中的元素 8 * @nelts: 元素关键字数组中元素个数 9 */ 10ngx_int_t ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, ngx_uint_t nelts) 11{ 12 u_char *elts; 13 size_t len; 14 u_short *test; 15 ngx_uint_t i, n, key, size, start, bucket_size; 16 ngx_hash_elt_t *elt, **buckets; 17 18 if (hinit->max_size == 0) 19 { 20 ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0, 21 "could not build %s, you should " 22 "increase %s_max_size: %i", 23 hinit->name, hinit->name, hinit->max_size); 24 return NGX_ERROR; 25 } 26 27 for (n = 0; n < nelts; n++) 28 { 29 /* 这个判断是确保一个 bucket 至少能存放一个实际元素以及结束哨兵，如果有任意一个实际元素 30 * （比如其 name 字段特别长）无法存放到 bucket 内则报错返回 */ 31 if (hinit->bucket_size < NGX_HASH_ELT_SIZE(&names[n]) + sizeof(void *)) 32 { 33 ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0, 34 "could not build %s, you should " 35 "increase %s_bucket_size: %i", 36 hinit->name, hinit->name, hinit->bucket_size); 37 return NGX_ERROR; 38 } 39 } 40 41 /* 接下来的测试针对当前传入的所有实际元素，测试分配多少个 Hash 节点(也就是多少个 bucket)会比较好， 42 * 即能省内存又能少冲突，否则的话，直接把 Hash 节点数目设置为最大值 hinit->max_size 即可。 */ 43 44 test = ngx_alloc(hinit->max_size * sizeof(u_short), hinit->pool->log); 45 if (test == NULL) 46 { 47 return NGX_ERROR; 48 } 49 50 /* 计算一个 bucket 除去结束哨兵所占空间后的实际可用空间大小 */ 51 bucket_size = hinit->bucket_size - sizeof(void *); 52 53 /* 计算所需 bucket 的最小个数，注意到存储一个实际元素所需的内存空间的最小值也就是 54 * (2*sizeof(void *)) (即宏 NGX_HASH_ELT_SIZE 的对齐处理)，所以一个 bucket 可以存储 55 * 的最大实际元素个数就为 bucket_size / (2 * sizeof(void *))，然后总实际元素个数 nelts 56 * 除以这个值就是最少所需要的 bucket 个数 */ 57 start = nelts / (bucket_size / (2 * sizeof(void *))); 58 start = start ? start : 1; 59 60 /* 如果这个 if 条件成立，意味着实际元素个数非常多，那么有必要直接把 start 起始值调高，否则在后面的 61 * 循环里要执行过多的无用测试 */ 62 if (hinit->max_size > 10000 && nelts && hinit->max_size / nelts < 100) 63 { 64 start = hinit->max_size - 1000; 65 } 66 67 /* 下面的 for 循环就是获取 Hash 结构最终节点数目的逻辑。就是逐步增加 Hash 节点数目(那么对应的 68 * bucket 数目同步增加)，然后把所有的实际元素往这些 bucket 里添放，这有可能发生冲突，但只要 69 * 冲突的次数可以容忍，即任意一个 bucket 都还没满，那么就继续填，如果发生有任何一个 bucket 70 * 满溢了(test[key] 记录了 key 这个 hash 节点所对应的 bucket 内存储实际元素后的总大小，如果它大 71 * 于一个 bucket 可用的最大空间 bucket_size，自然就是满溢了)，那么就必须增加 Hash 节点、增加 72 * bucket。如果所有实际元素都填完后没有发生满溢，那么当前的 size 值就是最终的节点数目值 */ 73 for (size = start; size <= hinit->max_size; size++) 74 { 75 76 ngx_memzero(test, size * sizeof(u_short)); 77 78 for (n = 0; n < nelts; n++) 79 { 80 if (names[n].key.data == NULL) 81 { 82 continue; 83 } 84 85 key = names[n].key_hash % size; 86 test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n])); 87 88#if 0 89 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, 90 "%ui: %ui %ui \"%V\"", 91 size, key, test[key], &names[n].key); 92#endif 93 94 /* 判断是否满溢，若满溢，则必须增加 Hash 节点、增加 bucket */ 95 if (test[key] > (u_short) bucket_size) 96 { 97 goto next; 98 } 99 } 100 101 /* 这里表示已将所有元素都添放到 bucket 中，则此时的 size 即为所需的节点数目值 */ 102 goto found; 103 104 next: 105 106 continue; 107 } 108 109 size = hinit->max_size; 110 111 ngx_log_error(NGX_LOG_WARN, hinit->pool->log, 0, 112 "could not build optimal %s, you should increase " 113 "either %s_max_size: %i or %s_bucket_size: %i; " 114 "ignoring %s_bucket_size", 115 hinit->name, hinit->name, hinit->max_size, 116 hinit->name, hinit->bucket_size, hinit->name); 117 118found: 119 120 /* 找到需创建的 Hash 节点数目值，接下来就是实际的 Hash 结构创建工作。 121 * 注意：所有 buckets 所占的内存空间是连接在一起的，并且是按需分配（即某个 bucket 需多少内存 122 * 存储实际元素就分配多少内存，除了额外的对齐处理）*/ 123 124 /* 初始化test数组中每个元素的值为 sizeof(void *)，即ngx_hash_elt_t的成员value的所占内存大小 */ 125 for (i = 0; i < size; i++) 126 { 127 test[i] = sizeof(void *); 128 } 129 130 /* 遍历所有的实际元素，计算出每个元素在对应槽上所占内存大小，并赋给该元素在test数组上的 131 * 相应位置，即散列表中对应的槽 */ 132 for (n = 0; n < nelts; n++) 133 { 134 if (names[n].key.data == NULL) 135 { 136 continue; 137 } 138 139 /* 找到该元素在散列表中的映射位置 */ 140 key = names[n].key_hash % size; 141 /* 计算存储在该槽上的元素所占的实际内存大小 */ 142 test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n])); 143 } 144 145 len = 0; 146 147 /* 对test数组中的每个元素(也即每个实际元素在散列表中对应槽所占内存的实际大小) 148 * 进行对齐处理 */ 149 for (i = 0; i < size; i++) 150 { 151 if (test[i] == sizeof(void *)) 152 { 153 continue; 154 } 155 156 test[i] = (u_short) (ngx_align(test[i], ngx_cacheline_size)); 157 158 /* len 统计所有实际元素所占的内存总大小 */ 159 len += test[i]; 160 } 161 162 if (hinit->hash == NULL) 163 { 164 hinit->hash = ngx_pcalloc(hinit->pool, sizeof(ngx_hash_wildcard_t) 165 + size * sizeof(ngx_hash_elt_t *)); 166 if (hinit->hash == NULL) 167 { 168 ngx_free(test); 169 return NGX_ERROR; 170 } 171 172 buckets = (ngx_hash_elt_t **) 173 ((u_char *) hinit->hash + sizeof(ngx_hash_wildcard_t)); 174 175 } 176 else 177 { 178 /* 为槽分配内存空间，每个槽都是一个指向 ngx_hash_elt_t 结构体的指针 */ 179 buckets = ngx_pcalloc(hinit->pool, size * sizeof(ngx_hash_elt_t *)); 180 if (buckets == NULL) 181 { 182 ngx_free(test); 183 return NGX_ERROR; 184 } 185 } 186 187 /* 分配一块连续的内存空间，用于存储槽的实际数据 */ 188 elts = ngx_palloc(hinit->pool, len + ngx_cacheline_size); 189 if (elts == NULL) 190 { 191 ngx_free(test); 192 return NGX_ERROR; 193 } 194 195 /* 进行内存对齐 */ 196 elts = ngx_align_ptr(elts, ngx_cacheline_size); 197 198 /* 使buckets[i]指向 elts 这块内存的相应位置 */ 199 for (i = 0; i < size; i++) 200 { 201 if (test[i] == sizeof(void *)) 202 { 203 continue; 204 } 205 206 buckets[i] = (ngx_hash_elt_t *) elts; 207 elts += test[i]; 208 } 209 210 /* 复位teset数组的值 */ 211 for (i = 0; i < size; i++) 212 { 213 test[i] = 0; 214 } 215 216 for (n = 0; n < nelts; n++) 217 { 218 if (names[n].key.data == NULL) 219 { 220 continue; 221 } 222 223 /* 计算该实际元素在散列表的映射位置 */ 224 key = names[n].key_hash % size; 225 /* 根据key找到该实际元素应存放在槽中的具体位置的起始地址 */ 226 elt = (ngx_hash_elt_t *) ((u_char *) buckets[key] + test[key]); 227 228 /* 下面是对存放在该槽中的元素进行赋值 */ 229 elt->value = names[n].value; 230 elt->len = (u_short) names[n].key.len; 231 232 ngx_strlow(elt->name, names[n].key.data, names[n].key.len); 233 234 /* 更新test[key]的值，以便当有多个实际元素映射到同一个槽中时便于解决冲突问题， 235 * 从这可以看出Nginx解决碰撞问题使用的方法是开放寻址法中的用连续非空槽来解决 */ 236 test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n])); 237 } 238 239 /* 遍历所有的槽，为每个槽的末尾都存放一个为 NULL 的哨兵节点 */ 240 for (i = 0; i < size; i++) 241 { 242 if (buckets[i] == NULL) 243 { 244 continue; 245 } 246 247 elt = (ngx_hash_elt_t *) ((u_char *) buckets[i] + test[i]); 248 249 elt->value = NULL; 250 } 251 252 ngx_free(test); 253 254 hinit->hash->buckets = buckets; 255 hinit->hash->size = size; 256 257#if 0 258 259 for (i = 0; i < size; i++) { 260 ngx_str_t val; 261 ngx_uint_t key; 262 263 elt = buckets[i]; 264 265 if (elt == NULL) { 266 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, 267 "%ui: NULL", i); 268 continue; 269 } 270 271 while (elt->value) { 272 val.len = elt->len; 273 val.data = &elt->name[0]; 274 275 key = hinit->key(val.data, val.len); 276 277 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, 278 "%ui: %p \"%V\" %ui", i, elt, &val, key); 279 280 elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len, 281 sizeof(void *)); 282 } 283 } 284 285#endif 286 287 return NGX_OK; 288}
hash 数据结构的使用
2.4 ngx_hash_find()
1/* 2 * 参数含义： 3 * - hash：是散列表结构体的指针 4 * - key：是根据散列方法算出来的散列关键字 5 * - name和len：表示实际关键字的地址与长度 6 * 7 * 执行意义： 8 * 返回散列表中关键字与name、len指定关键字完全相同的槽中，ngx_hash_elt_t结构体中value 9 * 成员所指向的用户数据. 10 */ 11void *ngx_hash_find(ngx_hash_t *hash, ngx_uint_t key, u_char *name, size_t len) 12{ 13 ngx_uint_t i; 14 ngx_hash_elt_t *elt; 15 16 17#if 1 18 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "hf:\"%*s\"", len, name); 19#endif 20 21 /* 对key取模得到对应的hash节点 */ 22 elt = hash->buckets[key % hash->size]; 23 24 if (elt == NULL) 25 { 26 return NULL; 27 } 28 29 /* 然后在该hash节点所对应的bucket里逐个(该bucket的实现类似数组，结束有 30 * 哨兵保证)对比元素名称来找到唯一的那个实际元素，最后返回其value值 31 * (比如，如果在addr->hash结构里找到对应的实际元素，返回的value就是 32 * 其ngx_http_core_srv_conf_t配置) */ 33 while (elt->value) 34 { 35 if (len != (size_t) elt->len) 36 { 37 goto next; 38 } 39 40 for (i = 0; i < len; i++) 41 { 42 if (name[i] != elt->name[i]) 43 { 44 goto next; 45 } 46 } 47 48 return elt->value; 49 50 next: 51 52 elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len, 53 sizeof(void *)); 54 continue; 55 } 56 57 return NULL; 58}
2.5 Nginx提供的两种散列方法
1/* 散列方法1：使用BKDR算法将任意长度的字符串映射为整型 */ 2ngx_uint_t ngx_hash_key(u_char *data, size_t len) 3{ 4 ngx_uint_t i, key; 5 6 key = 0; 7 8 for (i = 0; i < len; i++) 9 { 10 key = ngx_hash(key, data[i]); 11 } 12 13 return key; 14} 15 16 17/* 散列方法2：将字符串全小写后，再使用BKDR算法将任意长度的字符串映射为整型 */ 18ngx_uint_t ngx_hash_key_lc(u_char *data, size_t len) 19{ 20 ngx_uint_t i, key; 21 22 key = 0; 23 24 for (i = 0; i < len; i++) 25 { 26 key = ngx_hash(key, ngx_tolower(data[i])); 27 } 28 29 return key; 30}
2.6 基本散列表的使用实例
Nginx 对虚拟主机的管理使用到了 Hash 数据结构，比如假设配置文件nginx.conf中有如下配置：
1server { 2 listen 192.168.1.1:80; 3 server_name www.web_test2.com blog.web_test2.com; 4... 5server { 6 listen 192.168.1.1:80; 7 server_name www.web_test1.com bbs.web_test1.com; 8...
当Nginx使用该配置文件启动后，如果来了一个客户端请求到192.168.1.1的80端口，那么Nginx需要做
一个查找，看当前请求该使用哪个Server配置。为了提高查找效率，在启动时，Nginx就将根据这些
server_name建立一个Hash数据结构。
在ngx_http.c的ngx_http_server_names方法中：
1. 2 hash.key = ngx_hash_key_lc; 3 hash.max_size = cmcf->server_names_hash_max_size; 4 hash.bucket_size = cmcf->server_names_hash_bucket_size; 5 hash.name = "server_names_hash"; 6 hash.pool = cf->pool; 7 8 if (ha.keys.nelts) 9 { 10 hash.hash = &addr->hash; 11 hash.temp_pool = NULL; 12 13 if (ngx_hash_init(&hash, ha.keys.elts, ha.keys.nelts) != NGX_OK) 14 { 15 goto failed; 16 } 17 } 18 ...
调用ngx_hash_init前Hash数据结构初始状态
调用ngx_hash_init后Hash数据结构状态
图中，字段buckets指向的就是Hash节点所对应的存储空间，由于buckets是一个二级指针，那么*buckets本身是一个数组，每
一个数组元素用来存储映射到此的Hash节点。由于可能有多个实际元素映射到同一个Hash节点（即发生冲突），所以对实际元
素再次进行数组形式的组织存储在一个bucket内，这个数组的结束以哨兵元素NULL作为标记，而前面的每一个ngx_hash_elt_t
结构对应一个实际元素的存储。
3. Nginx 通配符散列表的实现
3.1 原理
支持通配符的散列表，就是把基本散列表中元素的关键字，用去除通配符以后的字符作为关键字加入。
例如，对于关键字为 "www.test." 这样带通配符的情况，直接建立一个专用的后置通配符散列表，
存储元素的关键字为 "www.test"。这样，如果要检索 "www.test.cn" 是否匹配 "www.test."，可用
Nginx 提供的专用方法 ngx_hash_find_wc_tail 检索，ngx_hash_find_wc_tail 方法会把要查询的
www.test.cn 转化为 www.test 字符串再开始查询。
同理，对于关键字为 "*.test.com" 这样带前置通配符的情况，也直接建立一个专用的前置通配符散
列表，存储元素的关键字为 "com.test."。如果我们要检索 smtp.test.com 是否匹配 *.test.com，
可用 Nginx 提供的专用方法 ngx_hash_find_wc_head 检索，ngx_hash_find_wc_head 方法会把要查
询的 smtp.test.com 转化为 com.test. 字符串再开始查询。
3.2 相应结构体
3.2.1 ngx_hash_wildcard_t 结构体
1typedef struct { 2 /* 基本散列表 */ 3 ngx_hash_t hash; 4 /* 当使用这个ngx_hash_wildcard_t通配符散列表作为某个容器的元素时，可以使用这个value 5 * 指针指向用户数据 */ 6 void *value; 7}ngx_hash_wildcard_t;
3.2.2 ngx_hash_combined_t 结构体
1typedef struct { 2 /* 用于精确匹配的基本散列表 */ 3 ngx_hash_t hash; 4 /* 用于查询前置通配符的散列表 */ 5 ngx_hash_wildcard_t *wc_head; 6 /* 用于查询后置通配符的散列表 */ 7 ngx_hash_wildcard_t *wc_tail; 8}ngx_hash_combined_t;
注：前置通配符散列表中元素的关键字，在把 * 通配符去掉后，会按照 "." 符号分隔，并以倒序的
方式作为关键字来存储元素。相应地，在查询元素时也是做相同处理。
3.2.3 ngx_hash_keys_arrays_t 结构体
1typedef struct { 2 /* 下面的keys_hash、dns_wc_head_hash、dns_wc_tail_hash都是简易散列表，而hsize指明了 3 * 散列表中槽的个数，其简易散列方法也需要对hsize求余 */ 4 ngx_uint_t hsize; 5 6 /* 内存池，用于分配永久性内存 */ 7 ngx_pool_t *pool; 8 /* 临时内存池，下面的动态数组需要的内存都由temp_pool内存池分配 */ 9 ngx_pool_t *temp_pool; 10 11 /* 用动态数组以ngx_hash_key_t结构体保存着不含有通配符关键字的元素 */ 12 ngx_array_t keys; 13 /* 一个极其简易的散列表，它以数组的形式保存着hsize个元素，每个元素都是ngx_array_t 14 * 动态数组。在用户添加的元素过程中，会根据关键码将用户的ngx_str_t类型的关键字添加 15 * 到ngx_array_t动态数组中。这里所有的用户元素的关键字都不可以带通配符，表示精确 16 * 匹配 */ 17 ngx_array_t *keys_hash; 18 19 /* 用动态数组以ngx_hash_key_t结构体保存着含有前置通配符关键字的元素生成的中间关键字 */ 20 ngx_array_t dns_wc_head; 21 /* 一个极其简易的散列表，它以数组的形式保存着hsize个元素，每个元素都是ngx_array_t 22 * 动态数组。在用户添加的元素过程中，会根据关键码将用户的ngx_str_t类型的关键字添加 23 * 到ngx_array_t动态数组中。这里所有的用户元素的关键字都带前置通配符 */ 24 ngx_array_t *dns_wc_head_hash; 25 26 /* 用动态数组以ngx_hash_key_t结构体保存着含有后置通配符关键字的元素生成的中间关键字 */ 27 ngx_array_t dns_wc_tail; 28 /* 一个极其简易的散列表，它以数组的形式保存着hsize个元素，每个元素都是ngx_array_t 29 * 动态数组。在用户添加的元素过程中，会根据关键码将用户的ngx_str_t类型的关键字添加 30 * 到ngx_array_t动态数组中。这里所有的用户元素的关键字都带后置通配符 */ 31 ngx_array_t *dns_wc_tail_hash; 32} ngx_hash_keys_arrays_t;
3.3 通配符散列表相关函数
3.3.1 ngx_hash_wildcard_init(): 初始化通配符散列表
1/* 2 * 参数含义： 3 * - hinit：是散列表初始化结构体的指针 4 * - names：是数组的首地址，这个数组中每个元素以ngx_hash_key_t作为结构体， 5 * 它存储着预添加到散列表中的元素(这些元素的关键字要么是含有前 6 * 置通配符，要么含有后置通配符) 7 * - nelts：是names数组的元素数目 8 * 9 * 执行意义： 10 * 初始化通配符散列表(前置或者后置)。 11 */ 12ngx_int_t ngx_hash_wildcard_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, 13 ngx_uint_t nelts) 14{ 15 size_t len, dot_len; 16 ngx_uint_t i, n, dot; 17 ngx_array_t curr_names, next_names; 18 ngx_hash_key_t *name, *next_name; 19 ngx_hash_init_t h; 20 ngx_hash_wildcard_t *wdc; 21 22 /* 从临时内存池temp_pool中分配一个元素个数为nelts，大小为sizeof(ngx_hash_key_t) 23 * 的数组curr_name */ 24 if (ngx_array_init(&curr_names, hinit->temp_pool, nelts, 25 sizeof(ngx_hash_key_t)) 26 != NGX_OK) 27 { 28 return NGX_ERROR; 29 } 30 31 /* 从临时内存池temp_pool中分配一个元素个数为nelts，大小为sizeof(ngx_hash_key_t) 32 * 的数组next_name */ 33 if (ngx_array_init(&next_names, hinit->temp_pool, nelts, 34 sizeof(ngx_hash_key_t)) 35 != NGX_OK) 36 { 37 return NGX_ERROR; 38 } 39 40 /* 遍历names数组中保存的所有通配符字符串 */ 41 for (n = 0; n < nelts; n = i) 42 { 43 44#if 0 45 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, 46 "wc0: \"%V\"", &names[n].key); 47#endif 48 49 dot = 0; 50 51 /* 遍历该通配符字符串的每个字符，直到找到 '.' 为止 */ 52 for (len = 0; len < names[n].key.len; len++) 53 { 54 if (names[n].key.data[len] == '.') 55 { 56 /* 找到则置位该标识位 */ 57 dot = 1; 58 break; 59 } 60 } 61 62 /* 从curr_names数组中取出一个类型为ngx_hash_key_t的指针 */ 63 name = ngx_array_push(&curr_names); 64 if (name == NULL) 65 { 66 return NGX_ERROR; 67 } 68 69 /* 若dot为1，则len为'.'距该通配符字符串起始位置的偏移值， 70 * 否则为该通配符字符串的长度 */ 71 name->key.len = len; 72 /* 将通配符字符串赋值给name->key.data */ 73 name->key.data = names[n].key.data; 74 /* 以该通配符字符串作为关键字通过key散列方法算出该通配符字符串在散列表中的 75 * 映射位置 */ 76 name->key_hash = hinit->key(name->key.data, name->key.len); 77 /* 指向用户有意义的数据结构 */ 78 name->value = names[n].value; 79 80#if 0 81 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, 82 "wc1: \"%V\" %ui", &name->key, dot); 83#endif 84 85 dot_len = len + 1; 86 87 /* 若前面的遍历中已找到'.'，则len加1 */ 88 if (dot) 89 { 90 len++; 91 } 92 93 next_names.nelts = 0; 94 95 /* 当通配符字串的长度与len不等时，即表明dot为1 */ 96 if (names[n].key.len != len) 97 { 98 /* 从next_names数组中取出一个类型为ngx_hash_key_t的指针 */ 99 next_name = ngx_array_push(&next_names); 100 if (next_name == NULL) 101 { 102 return NGX_ERROR; 103 } 104 105 /* 将该通配符第一个'.'字符之后的字符串放在next_name中 */ 106 next_name->key.len = names[n].key.len - len; 107 next_name->key.data = names[n].key.data + len; 108 next_name->key_hash = 0; 109 next_name->value = names[n].value; 110 111#if 0 112 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, 113 "wc2: \"%V\"", &next_name->key); 114#endif 115 } 116 117 /* 这里n为names数组中余下尚未处理的通配符字符串中的第一个在names数组中的下标值, 118 * 该for循环是用于提高效率，其实现就是比较当前通配符字符串与names数组中的下一个 119 * 通配符字符，若发现'.'字符之前的字符串都完全相同，则直接将该通配符字符串'.' 120 * 之后的字符串添加到next_names数组中 */ 121 for (i = n + 1; i < nelts; i++) 122 { 123 /* 对该通配符字符串与names数组中的下一个通配符字符串进行比较，若不等，则 124 * 直接跳出该for循环，否则继续往下处理 */ 125 if (ngx_strncmp(names[n].key.data, names[i].key.data, len) != 0) 126 { 127 break; 128 } 129 130 /* 对在该通配符字符串中没有找到'.'的通配符字符串下面不进行处理' */ 131 if (!dot 132 && names[i].key.len > len 133 && names[i].key.data[len] != '.') 134 { 135 break; 136 } 137 138 /* 从next_names数组中取出一个类型为ngx_hash_key_t的指针 */ 139 next_name = ngx_array_push(&next_names); 140 if (next_name == NULL) 141 { 142 return NGX_ERROR; 143 } 144 145 next_name->key.len = names[i].key.len - dot_len; 146 next_name->key.data = names[i].key.data + dot_len; 147 next_name->key_hash = 0; 148 next_name->value = names[i].value; 149 150#if 0 151 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, 152 "wc3: \"%V\"", &next_name->key); 153#endif 154 } 155 156 /* 若next_names数组中有元素 */ 157 if (next_names.nelts) 158 { 159 160 h = *hinit; 161 h.hash = NULL; 162 163 if (ngx_hash_wildcard_init(&h, (ngx_hash_key_t *) next_names.elts, 164 next_names.nelts) 165 != NGX_OK) 166 { 167 return NGX_ERROR; 168 } 169 170 wdc = (ngx_hash_wildcard_t *) h.hash; 171 172 if (names[n].key.len == len) 173 { 174 wdc->value = names[n].value; 175 } 176 177 name->value = (void *) ((uintptr_t) wdc | (dot ? 3 : 2)); 178 179 } 180 else if (dot) 181 { 182 name->value = (void *) ((uintptr_t) name->value | 1); 183 } 184 } 185 186 if (ngx_hash_init(hinit, (ngx_hash_key_t *) curr_names.elts, 187 curr_names.nelts) 188 != NGX_OK) 189 { 190 return NGX_ERROR; 191 } 192 193 return NGX_OK; 194}
ngx_hash_combined_t通配符散列表的结构示意图
3.4 带通配符散列表的使用实例
散列表元素ngx_hash_elt_t中value指针指向的数据结构为下面定义的TestWildcardHashNode结构体，代码如下：
1typedef struct { 2 /* 用于散列表中的关键字 */ 3 ngx_str_t servername; 4 /* 这个成员仅是为了方便区别而已 */ 5 ngx_int_t se; 6}TestWildcardHashNode;
每个散列表元素的关键字是servername字符串。下面先定义ngx_hash_init_t和ngx_hash_keys_arrays_t变量，为初始化散列
表做准备，代码如下：
1/* 定义用于初始化散列表的结构体 */ 2ngx_hash_init_t hash; 3/* ngx_hash_keys_arrays_t用于预先向散列表中添加元素，这里的元素支持带通配符 */ 4ngx_hash_keys_arrays_t ha; 5/* 支持通配符的散列表 */ 6ngx_hash_combined_t combinedHash; 7 8ngx_memzero(&ha, sizeof(ngx_hash_keys_arrays_t));
combinedHash 是我们定义的用于指向散列表的变量，它包括指向 3 个散列表的指针，下面依次给这 3 个散列表指针赋值。
1/* 临时内存池只是用于初始化通配符散列表，在初始化完成后就可以销毁掉 */ 2ha.temp_pool = ngx_create_pool(16384, cf->log); 3if (ha.temp_pool == NULL) 4{ 5 return NGX_ERROR; 6} 7 8/* 假设该例子是在ngx_http_xxx_postconf函数中的，所以就用了ngx_conf_t类型的cf下的内存池 9 * 作为散列表的内存池 */ 10ha.pool = cf->pool; 11 12/* 调用ngx_hash_keys_array_init方法来初始化ha，为下一步向ha中加入散列表元素做好准备 */ 13if (ngx_hash_keys_array_init(&ha, NGX_HASH_LARGE) != NGX_OK) 14{ 15 return NGX_ERROR; 16}
如下代码，建立的 testHashNode[3] 这 3 个 TestWildcardHashNode 类型的结构体，分别表示可以用前置通配符匹配的散
列表元素、可以用后置通配符匹配的散列表元素、需要完全匹配的散列表元素。
1TestWildcardHahsNode testHashNode[3]; 2testHashNode[0].servername.len = ngx_strlen("*.text.com"); 3testHashNode[0].servername.data = ngx_pcalloc(cf->pool, ngx_strlen("*.test.com")); 4ngx_memcpy(testHashNode[0].servername.data, "*.test.com", ngx_strlen("*.test.com")); 5 6testHashNode[1].servername.len = ngx_strlen("www.test.*"); 7testHashNode[1].servername.data = ngx_pcalloc(cf->pool, ngx_strlen("www.test.*")); 8ngx_memcpy(testHashNode[1].servername.data, "www.test.*", ngx_strlen("www.test.*")); 9 10testHashNode[2].servername.len = ngx_strlen("www.text.com"); 11testHashNode[2].servername.data = ngx_pcalloc(cf->pool, ngx_strlen("www.test.com")); 12ngx_memcpy(testHashNode[2].servername.data, "www.test.com", ngx_strlen("www.test.com")); 13 14for (i = 0; i < 3; i++) 15{ 16 testHashNode[i].seq = i; 17 /* 这里flag必须设置为NGX_HASH_WILDCARD_KEY，才会处理带通配符的关键字 */ 18 ngx_hash_add_key(&ha, &testHashNode[i].servername, 19 &testHashNode[i], NGX_HASH_WILDCARD_KEY); 20}
在调用ngx_hash_init_t的初始化函数前，先设置好ngx_hash_init_t中的成员，如槽的大小、散列方法等：
1hash.key = ngx_hash_key_lc; 2hash.max_size = 100; 3hash.bucket_size = 48; 4hash.name = "test_server_name_hash"; 5hash.pool = cf->pool;
ha的keys动态数组中存放的是需要完全匹配的关键字，如果keys数组不为空，那么开始初始化第 1 个散列表：
1if (ha.keys.nelts) 2{ 3 /* 需要显式地把ngx_hash_init_t中的hash指针指向combinedHash中的完全匹配散列表 */ 4 hash.hash = &combinedHash.hash; 5 /* 初始化完全匹配散列表时不会使用到临时内存池 */ 6 hash.temp_pool = NULL; 7 8 /* 将keys动态数组直接传给ngx_hash_init方法即可，ngx_hash_init_t中的 9 * hash指针就是初始化成功的散列表 */ 10 if (ngx_hash_init(&hash, ha.keys.nelts, ha.keys.nelts) != NGX_OK) 11 { 12 return NGX_ERROR; 13 } 14}
下面继续初始化前置通配符散列表：
1if (ha.dns_wc_head.nelts) 2{ 3 hash.hash = NULL; 4 /* ngx_hash_wildcard_init方法需要用到临时内存池 */ 5 hash.temp_pool = ha.temp_pool; 6 if (ngx_hash_wildcard_init(&hash, ha.dns_wc_head.elts, ha.dns_wc_head.nelts) != NGX_OK) 7 { 8 return NGX_ERROR; 9 } 10 11 /* ngx_hash_init_t中的hash指针是ngx_hash_wildcard_init初始化成功的散列表， 12 * 需要将它赋到combinedHash.wc_head前置通配符散列表指针中 */ 13 combinedHash.wc_head = (ngx_hash_wildcard_t *)hash.hash; 14}
接着继续初始化后置通配符散列表：
1if (ha.dns_wc_tail.nelts) 2{ 3 hash.hash = NULL; 4 hash.temp_pool = hs.temp_pool; 5 if (ngx_hash_wildcard_init(&hash, ha.dns_wc_tail.elts, ha.dns_wc_tail.nelts) != NGX_OK) 6 { 7 return NGX_ERROR; 8 } 9 10 /* ngx_hash_init_t中的hash指针是ngx_hash_wildcard_init初始化成功的散列表，需要将它赋到 11 * combinedHash.wc_tail后置通配符散列表指针中 */ 12 combinedHash.wc_tail = (ngx_hash_wildcard_t *) hash.hash; 13}
此时，临时内存池已经没有存在意义了，即ngx_hash_keys_arrays_t中的这些数组、简易散列表都可以销毁了。这里只需要
简单地把temp_pool内存池销毁即可：
ngx_destroy_pool(ha.temp_pool);
下面检查一下散列表是否工作正常。首先，查询关键字www.test.org，实际上，它应该匹配后置通配符散列表中的元素
www.text.\*：
1/* 首先定义待查询的关键字符串findServer */ 2ngx_str_t findServer; 3findServer.len = ngx_strlen("www.test.org"); 4/* 为什么必须要在内存池中分配空间以保存关键字呢？因为我们使用的散列方法是 ngx_hash_key_l，它会试着把 5 * 关键字全小写 */ 6findServer.data = ngx_pcalloc(cf->pool, ngx_strlen("www.test.org")); 7ngx_memcpy(findServer.data, "www.test.org", ngx_strlen("www.test.org")); 8 9/* ngx_hash_find_combined方法会查找出www.test.*对应的散列表元素，返回其指向的用户数据 10 * ngx_hash_find_combined， 也就是testHashNode[1] */ 11TestWildcardHashNode *findHashNode = ngx_hash_find_combined(&combinedHash, 12 ngx_hash_key_lc(findServer.data, findServer.len), findServer.data, findServer.len);
如果没有查询到的话，那么findHashNode值为NULL。
接着查询www.test.com，实际上，testHashNode[0]、testHashNode[1]、testHashNode[2]这 3 个节点都是匹配的，因为
.test.com、www.test.、www.test.com都是匹配的。但按照完全匹配最优先的规则，ngx_hash_find_combined方法会返回
testHashNode[2]的地址，也就是www.test.com对应的元素。
1findServer.len = ngx_strlen("www.test.com"); 2findServer.data = ngx_pcalloc(cf->pool, ngx_strlen("www.test.com")); 3ngx_memcpy(findServer.data, "www.test.com", ngx_strlen("www.test.com"); 4 5findHashNode = ngx_hash_find_combined(&combinedHash, 6 ngx_hash_key_lc(findServer.data, findServer.len), 7 findServer.data, findServer.len);