nginx实现了自己的hash数据结构，正如数据结构中讲述的那样，nginx用开放链表法解决冲突，不过不同的是一旦一个hash表被初始化后就不会被修改，即插入和删除，只进行查询操作，所以nginx通过计算初始化时key的个数来确定hash表中桶的个数和每个桶的容量，这样能最大限度的利用内存资源。虽然用开放链表法，实际上每个桶都是一块连续的内存空间。nginx实现了两类hash结构，一类是key中包含通配符的ngx_hash_wildcard_t，另一类则是key中不包含通配符的ngx_hash_t，这里的通配符指*号。之所以会有这两类hash，是因为nginx主要用hash来存放url与ip的对应关系，目的是为了通过url来查找ip，而url是可以用通配符表示的，如*.baidu.com。接下来先通过深入到nginx源码中看看hash中定义的数据结构，然后看看两类hash是怎样实现的，最后通过一个例子来使用这两类hash。
1 相关的数据结构
1.1 ngx_hash_t结构
这类hash的数据结构定义如下：
1 typedef struct { 2 void *value; //ip，也就是 中的key 3 u_short len; //url长度 4 u_char name[1]; //url，也就是 中的value 5 } ngx_hash_elt_t; 6 7 8 typedef struct { 9 ngx_hash_elt_t **buckets; //每个桶的起始地址10 ngx_uint_t size; //桶的个数11 } ngx_hash_t; ngx_hash_t结构管理这个hash，ngx_hash_elt_t是hash桶中一个元素的表示。ngx_hash_elt_t字段中的value既可以指向实际的ip，也可以指向另一个hash表（这种情况只能出现在包含通配符的hash中），name字段既可以指向完整的url，也可以指向url的一部分（这种情况也只能出现在包含通配符的hash中）。
1.2 ngx_hash_wildcard_t
这个结构主要用于包含通配符的hash的，具体如下：
1 typedef struct {2 ngx_hash_t hash;3 void *value;4 } ngx_hash_wildcard_t; 这个结构相比ngx_hash_t结构就是多了一个value指针，value这个字段是用来存放某个已经达到末尾的通配符url对应的value值，如果通配符url没有达到末尾，这个字段为NULL。
1.3 ngx_hash_init_t
ngx_hash_init_t结构主要用于提供创建一个hash所需要的一些信息，定义如下：
1 typedef struct { 2 ngx_hash_t *hash; //指向待新建的hash表 3 ngx_hash_key_pt key; //hash函数指针 4 5 ngx_uint_t max_size; //hash表中桶的最大值,实际桶的个数存放在前面ngx_hash_t中的size字段中 6 ngx_uint_t bucket_size; //每个桶的最大尺寸 7 8 char *name; //hash表的名字，其实没啥用（在log中用） 9 ngx_pool_t *pool; //构建hash所用的内存池10 ngx_pool_t *temp_pool; //构建hash所用的临时内存池11 } ngx_hash_init_t; hash字段如果为NULL的话，会动态创建管理hash的结构ngx_hash_t，这种情况通常在包含通配符的情况下使用；如果不为NULL，则使用这个字段指向的ngx_hash_t结构，这种情况通常在不包含通配符的情况下使用。
1.4 ngx_hash_key_t
ngx_hash_key_t结构主要用于初始化hash表的，正如前面说的，nginx只能一次性的初始化，初始化之后就不能插入和修改了，所以用一个ngx_table_elt_t结构的数组来存放要插入到hash中的所有<key,value>对，所有初始化hash的函数都需要根据这样一个数组来初始化hash，这个在后面初始化hash函数的时候可以看到。
1 typedef struct {2 ngx_str_t key; // 中的key3 ngx_uint_t key_hash; //key通过hash函数算出的hash值4 void *value; // 中的value5 } ngx_hash_key_t; 1.5 ngx_hash_combined_t
1 typedef struct {2 ngx_hash_t hash;3 ngx_hash_wildcard_t *wc_head;4 ngx_hash_wildcard_t *wc_tail;5 } ngx_hash_combined_t; 这个结构包含了三类hash，hash字段表示不保护通配符的hash，wc_head字段表示包含前缀通配符的hash，wc_tail表示包含后缀通配符的hash。由于用户配置的url通常会是是不包含通配符的url，包含前缀通配符的url和包含后缀通配符的rul中的一种或多种，所以一般使用这个结构来完全表示用户配置的url。
1.6 ngx_hash_keys_arrays_t
1 typedef struct { 2 ngx_uint_t hsize; 3 ngx_pool_t *pool; 4 ngx_pool_t *temp_pool; 5 6 ngx_array_t keys; //存放不包含通配符的 键值对 7 ngx_array_t *keys_hash; //用来检测冲突的 8 9 ngx_array_t dns_wc_head; //存放包含前缀通配符的 键值对10 ngx_array_t *dns_wc_head_hash; //用来检测冲突的11 12 ngx_array_t dns_wc_tail; //存放包含后缀通配符的 键值对13 ngx_array_t *dns_wc_tail_hash; //用来检测冲突的14 } ngx_hash_keys_arrays_t; 这个结构存放了初始化hash需要的所有键值对，keys数组用来初始化不包含通配符的hash，dns_wc_head数组用来初始化包含前缀通配符的hash，dns_wc_tail数组用来初始化包含后缀通配符的hash，并且dns_wc_head和dns_wc_tail数组包含的<key,value>键值对中的key都是已经去掉通配符的key，具体情况在后面ngx_hash_add_key函数的介绍中会详细说明。
2 相关函数
2.1 ngx_hash_init
这个函数用来初始化不包含通配符的hash，函数原型如下：
1 ngx_int_t2 ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, ngx_uint_t nelts)
hinit参数是初始化hash的相关信息，names存放了所有需要插入到hash中的<key,value>对，nelts是<key,value>对的个数。这个函数主要做了4部分的工作：
（1）检查bucket_size是否合法，也就是它的值必须保证一个桶至少能存放一个<key,value>键值对，具体如下：
1 #define NGX_HASH_ELT_SIZE(name) \ 2 (sizeof(void *) + ngx_align((name)->key.len + 2, sizeof(void *))) 3 4 for (n = 0; n < nelts; n++) { 5 if (hinit->bucket_size < NGX_HASH_ELT_SIZE(&names[n]) + sizeof(void *)) 6 { 7 ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0, 8 "could not build the %s, you should " 9 "increase %s_bucket_size: %i",10 hinit->name, hinit->name, hinit->bucket_size);11 return NGX_ERROR;12 }13 } 上面的for循环保证hash的桶至少能装一个<key,value>键值对，宏NGX_HASH_ELT_SIZE用来计算一个ngx_hash_key_t表示一个实际的<key,value>键值对占用内存的大小，之所以NGX_HASH_ELT_SIZE(&names[n]) 后面需要加上sizeof(void *)，主要是每个桶都用一个值位NULL的void*指针来标记结束。
（2）计算hash中桶的个数
1 bucket_size = hinit->bucket_size - sizeof(void *); //除去桶标记后桶的大小 2 start = nelts / (bucket_size / (2 * sizeof(void *))); //桶的最小个数 3 start = start ? start : 1; 4 if (hinit->max_size > 10000 && nelts && hinit->max_size / nelts < 100) { 5 start = hinit->max_size - 1000; 6 } 7 //更新size来满足bucket_size 8 for (size = start; size < hinit->max_size; size++) { 9 ngx_memzero(test, size * sizeof(u_short));10 for (n = 0; n < nelts; n++) {11 if (names[n].key.data == NULL) {12 continue;13 }14 key = names[n].key_hash % size; //计算当前 在哪个桶15 test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n])); //计算当前 插入到桶之后桶的大小16 17 if (test[key] > (u_short) bucket_size) { //检查桶是否溢出了18 goto next;19 }20 }21 goto found;22 next:23 continue;24 从最小桶的个数开始递增，直到所有的<key,value>键值对都能存放在对应的桶中不溢出，那当前的桶个数就是需要的桶个数。
（3）计算新创建的hash所占用的空间，并调用内存分配函数分配这些空间
1 for (i = 0; i < size; i++) { 2 test[i] = sizeof(void *); 3 } 4 //计算每个桶的实际大小 5 for (n = 0; n < nelts; n++) { 6 if (names[n].key.data == NULL) { 7 continue; 8 } 9 10 key = names[n].key_hash % size;11 test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));12 }13 //计算所有桶的大小14 len = 0;15 16 for (i = 0; i < size; i++) {17 if (test[i] == sizeof(void *)) {18 continue;19 }20 21 test[i] = (u_short) (ngx_align(test[i], ngx_cacheline_size)); //每个桶大小满足cache行对齐22 23 len += test[i];24 } 上面根据实际的<key,value>键值对来实际计算每个桶的大小，而不是所有桶的大小的设置成一样的，这样能很有效的节约内存空间，当然由于每个桶的大小是不固定的，所有每个桶的末尾需要一个额外空间（大小为sizeof(void*)）来标记桶的结束。并且每个桶大小满足cache行对齐，这样能加快访问速度，从这里也可以看出nginx无处不在优化程序的性能和资源的使用效率。
1 if (hinit->hash == NULL) { //hash为NULL，则动态生成管理hash的结构 2 //calloc会把获取的内存初始化为0 3 hinit->hash = ngx_pcalloc(hinit->pool, sizeof(ngx_hash_wildcard_t) 4 + size * sizeof(ngx_hash_elt_t *)); 5 if (hinit->hash == NULL) { 6 ngx_free(test); 7 return NGX_ERROR; 8 } 9 10 buckets = (ngx_hash_elt_t **)11 ((u_char *) hinit->hash + sizeof(ngx_hash_wildcard_t));12 13 } else {14 buckets = ngx_pcalloc(hinit->pool, size * sizeof(ngx_hash_elt_t *));15 if (buckets == NULL) {16 ngx_free(test);17 return NGX_ERROR;18 }19 }20 21 elts = ngx_palloc(hinit->pool, len + ngx_cacheline_size); //将所有桶占用的空间分配在连续的内存空间中22 if (elts == NULL) {23 ngx_free(test);24 return NGX_ERROR;25 }26 27 elts = ngx_align_ptr(elts, ngx_cacheline_size);28 29 for (i = 0; i < size; i++) {30 if (test[i] == sizeof(void *)) {31 continue;32 }33 34 buckets[i] = (ngx_hash_elt_t *) elts; //初始化每个桶的起始位置35 elts += test[i];36 37 } 上面代码先动态分配每个桶的起始指针，然后动态分配所有桶的空间，然后根据每个桶的大小，将每个桶的起始指针初始化指向对应桶的起始地址。
（4）将每个<key,value>键值对复制到所在的桶中
1 for (i = 0; i < size; i++) { 2 test[i] = 0; 3 } 4 5 for (n = 0; n < nelts; n++) { 6 if (names[n].key.data == NULL) { 7 continue; 8 } 9 10 key = names[n].key_hash % size; //计算当前 所在的桶11 elt = (ngx_hash_elt_t *) ((u_char *) buckets[key] + test[key]); //计算当前 所在桶中的位置12 //将当前 的值复制到桶中13 elt->value = names[n].value;14 elt->len = (u_short) names[n].key.len;15 16 ngx_strlow(elt->name, names[n].key.data, names[n].key.len);17 test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n])); //更新当前桶的大小18 }19 //为了标记每个桶的结束20 for (i = 0; i < size; i++) {21 if (buckets[i] == NULL) {22 continue;23 }24 25 elt = (ngx_hash_elt_t *) ((u_char *) buckets[i] + test[i]);26 27 elt->value = NULL; //前面每个test加上sizeof(void *)就是为了这个value指针28 } 通过调用ngx_hash_init函数，一个hash就建立起来了，该hash大概的情况如下图所示：
2.2 ngx_hash_add_key
1 ngx_int_t2 ngx_hash_add_key(ngx_hash_keys_arrays_t *ha, ngx_str_t *key, void *value,3 ngx_uint_t flags)
ha中包含了三类ngx_hash_key_t类型的数组，分别用来初始化三类hash（介绍ngx_hash_keys_arrays_t时已说明），那么新的<key,value>应该加入到哪个数组中就是ngx_hash_add_key这个函数的主要任务。参数中的flags用来标记是否key中可能包含通配符，一般这个参数设置为NGX_HASH_WILDCARD_KEY，即可能包含通配符。需要注意的是这个函数会改变包含通配符的key，将通配符去掉，如*.baidu.com会改变为com.baidu.，.baidu.com会改变为com.baidu，www.baidu.*会改变为www.baidu，www.baidu.这种通配是不允许出现的。
2.3 ngx_hash_find
1 void *2 ngx_hash_find(ngx_hash_t *hash, ngx_uint_t key, u_char *name, size_t len)
这个函数通过给定的key和name在hash表中查找对应的<name,value>键值对，并将查找到的value值返回，参数中的key是name通过hash计算出来的。这个函数的实现很简单，就是通过key找到要查找的键值对在哪个桶中，然后遍历这个桶中的每个元素找key等于name的元素。
2.4 ngx_hash_wildcard_init
1 ngx_int_t2 ngx_hash_wildcard_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names,3 ngx_uint_t nelts)
这个函数是nginx实现通配hash的关键所在，该函数通过对通配键值对建立多级hash来实现通配hash。实现的hash表大致如下图所示：
上面的图只显示了二级hash，实际上可以由多级hash。下面我们举个实际的例子来加深理解，假设有下面这些键值对：
<*.com, "220.181.111.147">，<*.baidu.com, "220.181.111.147">，<*.baidu.com.cn, "220.181.111.147">，<*.google.com，"58.63.236.35">
（1）通过函数ngx_hash_add_key将上面的键值对加入到ngx_hash_keys_arrays_t结构中的dns_wc_head数组中，该数组的值如下图所示：
{key = ("com." , 4 ), key_hash = 0 , value = "220.181.111.147"}
{key = ("cn.com.baidu." , 13), key_hash = 0 , value = "220.181.111.147"} {key = ("com.baidu." , 10), key_hash = 0 , value = "220.181.111.147"} {key = ("com.google." , 11), key_hash = 0 , value = "58.63.236.35"}（2）将上面的dns_wc_head数组传递给ngx_hash_wildcard_init，生成的hash如下图所示：
现在来看下ngx_hash_wildcard_init是怎样实现上面图所示的多级hash结构的。
1 for (n = 0; n < nelts; n = i) { 2 3 dot = 0; 4 //以.作为字段的分隔符 5 for (len = 0; len < names[n].key.len; len++) { 6 if (names[n].key.data[len] == '.') { 7 dot = 1; 8 break; 9 }10 }11 12 name = ngx_array_push(&curr_names);13 if (name == NULL) {14 return NGX_ERROR;15 }16 //将上面获取的字段作为当前hash的key17 name->key.len = len;18 name->key.data = names[n].key.data;19 name->key_hash = hinit->key(name->key.data, name->key.len);20 name->value = names[n].value;21 22 dot_len = len + 1;23 24 if (dot) {25 len++;26 }27 //收集同一前缀的所有后缀28 next_names.nelts = 0;29 30 if (names[n].key.len != len) {31 next_name = ngx_array_push(&next_names);32 if (next_name == NULL) {33 return NGX_ERROR;34 }35 36 next_name->key.len = names[n].key.len - len;37 next_name->key.data = names[n].key.data + len;38 next_name->key_hash = 0;39 next_name->value = names[n].value;40 }41 42 for (i = n + 1; i < nelts; i++) {43 if (ngx_strncmp(names[n].key.data, names[i].key.data, len) != 0) {44 break;45 }46 47 if (!dot48 && names[i].key.len > len49 && names[i].key.data[len] != '.')50 {51 break;52 }53 54 next_name = ngx_array_push(&next_names);55 if (next_name == NULL) {56 return NGX_ERROR;57 }58 59 next_name->key.len = names[i].key.len - dot_len;60 next_name->key.data = names[i].key.data + dot_len;61 next_name->key_hash = 0;62 next_name->value = names[i].value;63 }64 65 if (next_names.nelts) { //next_names中有元素66 67 h = *hinit;68 h.hash = NULL; 69 //递归建立当前字段的所有后缀字段组成的hash70 if (ngx_hash_wildcard_init(&h, (ngx_hash_key_t *) next_names.elts,71 next_names.nelts)72 != NGX_OK)73 {74 return NGX_ERROR;75 }76 77 wdc = (ngx_hash_wildcard_t *) h.hash;78 79 if (names[n].key.len == len) { //当前字段已经达到末尾80 wdc->value = names[n].value;81 }82 //将后缀组成的下一级hash地址作为当前字段的value保存下来83 name->value = (void *) ((uintptr_t) wdc | (dot ? 3 : 2)); //2只有在后缀通配符的情况下才会出现84 85 } else if (dot) { //只有一个，而且不是后缀通配符86 name->value = (void *) ((uintptr_t) name->value | 1);87 }88 }89 //根据 <当前字段,value> 键值对建立hash90 if (ngx_hash_init(hinit, (ngx_hash_key_t *) curr_names.elts,91 curr_names.nelts)92 != NGX_OK)93 {94 return NGX_ERROR;95 }96 97 return NGX_OK;98 } 怎样标记一个键值对<key,value>中的value是指向实际的value，还是指向下一级的hash地址，这是上面代码实现的一个巧妙的地方。由于每个hash表的地址或者实际value的地址都是以4字节对齐的，所以这些地址的低2位都是0，这样通过这两位的标记可以很好地解决这个问题。
2.5 ngx_hash_find_wc_head
1 void *2 ngx_hash_find_wc_head(ngx_hash_wildcard_t *hwc, u_char *name, size_t len)
这个函数根据name在前缀通配符hash中查找对应的value值。有了hash表后，查找是件相对更容易的事，从后往前的获取name的每个字段（根据.分割），用每个字段查hash表，如果获取的value值的标记存在下一级hash，则用同样的方法查下一个字段对应的hash表，就这样直到查到的value为真实的值为止。另一个通配符查找函数ngx_hash_find_wc_tail这是同样的原理，不同的是对name从前往后处理每个字段而已。
3 测试
测试的程序主要是使用nginx实现的数据结构和函数，先通过下列url和ip建立hash，然后对给定的url查找ip。
（1）测试的数据如下：
1 static ngx_str_t urls[Max_Num] = { 2 ngx_string("*.com"), //220.181.111.147 3 ngx_string("*.baidu.com.cn"), 4 ngx_string("*.baidu.com"), 5 ngx_string(".baidu.com"), 6 ngx_string("*.google.com"), 7 ngx_string("www.sina.com.cn"), //58.63.236.35 8 ngx_string("www.google.com"), //74.125.71.105 9 ngx_string("www.qq.com"), //60.28.14.19010 ngx_string("www.163.com"), //123.103.14.23711 ngx_string("www.sohu.com"), //219.234.82.5012 ngx_string("abo321.org"), //117.40.196.2613 ngx_string(".abo321.org"), //117.40.196.2614 ngx_string("www.abo321.*") //117.40.196.2615 };16 17 static ngx_str_t values[Max_Num] = {18 ngx_string("220.181.111.147"),19 ngx_string("220.181.111.147"),20 ngx_string("220.181.111.147"),21 ngx_string("220.181.111.147"),22 ngx_string("220.181.111.147"),23 ngx_string("58.63.236.35"),24 ngx_string("74.125.71.105"),25 ngx_string("60.28.14.190"),26 ngx_string("123.103.14.237"),27 ngx_string("219.234.82.50"),28 ngx_string("117.40.196.26"),29 ngx_string("117.40.196.26"),30 ngx_string("117.40.196.26")31 }; （2）测试代码为：https://github.com/cc1989/nginx_report/tree/master/nginx_test/hash
（3）测试结果
1 -------------------------------- 2 create a new pool: 3 -------------------------------- 4 pool = 0x810d020 5 .d 6 .last = 0x810d048 7 .end = 0x810d420 8 .next = (nil) 9 .failed = 0 10 .max = 984 11 .current = 0x810d020 12 .chain = (nil) 13 .large = (nil) 14 .cleanup = (nil) 15 .log = 0x8051518 16 available pool memory = 984 17 18 -------------------------------- 19 create and add urls to it: 20 -------------------------------- 21 array = 0xbfed53b4 22 .elts = 0xb7542008 23 .nelts = 6 24 .size = 16 25 .nalloc = 16384 26 .pool = 0x810d450 27 elements: 28 0xb7542008: {key = ("www.sina.com.cn", 15), key_hash = 1528635686 , value = "58.63.236.35" } 29 0xb7542018: {key = ("www.google.com" , 14), key_hash = -702889725 , value = "74.125.71.105" } 30 0xb7542028: {key = ("www.qq.com" , 10), key_hash = 203430122 , value = "60.28.14.190" } 31 0xb7542038: {key = ("www.163.com" , 11), key_hash = -640386838 , value = "123.103.14.237" } 32 0xb7542048: {key = ("www.sohu.com" , 12), key_hash = 1313636595 , value = "219.234.82.50" } 33 0xb7542058: {key = ("abo321.org" , 10), key_hash = 1050805370 , value = "117.40.196.26" } 34 35 array = 0xbfed53cc 36 .elts = 0xb7501008 37 .nelts = 4 38 .size = 16 39 .nalloc = 16384 40 .pool = 0x810d450 41 elements: 42 0xb7501008: {key = ("com." , 4 ), key_hash = 0 , value = "220.181.111.147"} 43 0xb7501018: {key = ("cn.com.baidu." , 13), key_hash = 0 , value = "220.181.111.147"} 44 0xb7501028: {key = ("com.baidu." , 10), key_hash = 0 , value = "220.181.111.147"} 45 0xb7501038: {key = ("com.google." , 11), key_hash = 0 , value = "220.181.111.147"} 46 47 array = 0xbfed53e4 48 .elts = 0xb74c0008 49 .nelts = 1 50 .size = 16 51 .nalloc = 16384 52 .pool = 0x810d450 53 elements: 54 0xb74c0008: {key = ("www.abo321" , 10), key_hash = 0 , value = "117.40.196.26" } 55 56 -------------------------------- 57 the pool: 58 -------------------------------- 59 pool = 0x810d020 60 .d 61 .last = 0x810d2a9 62 .end = 0x810d420 63 .next = (nil) 64 .failed = 0 65 .max = 984 66 .current = 0x810d020 67 .chain = (nil) 68 .large = (nil) 69 .cleanup = (nil) 70 .log = 0x8051518 71 available pool memory = 375 72 73 array = 0xbfed53cc 74 .elts = 0xb7501008 75 .nelts = 4 76 .size = 16 77 .nalloc = 16384 78 .pool = 0x810d450 79 elements: 80 0xb7501008: {key = ("cn.com.baidu." , 13), key_hash = 0 , value = "220.181.111.147"} 81 0xb7501018: {key = ("com." , 4 ), key_hash = 0 , value = "220.181.111.147"} 82 0xb7501028: {key = ("com.baidu." , 10), key_hash = 0 , value = "220.181.111.147"} 83 0xb7501038: {key = ("com.google." , 11), key_hash = 0 , value = "220.181.111.147"} 84 85 array = 0xbfed53e4 86 .elts = 0xb74c0008 87 .nelts = 1 88 .size = 16 89 .nalloc = 16384 90 .pool = 0x810d450 91 elements: 92 0xb74c0008: {key = ("www.abo321" , 10), key_hash = 0 , value = "117.40.196.26" } 93 94 -------------------------------- 95 the hash: 96 -------------------------------- 97 hash = 0xbfed53fc: **buckets = 0x810d2ac, size = 3 98 0x810d2ac: buckets[0] = 0x810d2c0 99 0x810d2b0: buckets[1] = 0x810d300100 0x810d2b4: buckets[2] = 0x810d320101 102 key 1528635686: buckets 2: 0x810d320: {value = "58.63.236.35" , len = 15, name = "www.sina.com.cn"}103 key -702889725: buckets 1: 0x810d300: {value = "74.125.71.105" , len = 14, name = "www.google.com" }104 key 203430122 : buckets 2: 0x810d338: {value = "60.28.14.190" , len = 10, name = "www.qq.com" }105 key -640386838: buckets 0: 0x810d2c0: {value = "123.103.14.237" , len = 11, name = "www.163.com" }106 key 1313636595: buckets 0: 0x810d2d4: {value = "219.234.82.50" , len = 12, name = "www.sohu.com" }107 key 1050805370: buckets 2: 0x810d348: {value = "117.40.196.26" , len = 10, name = "abo321.org" }108 value = NULL109 hash = 0x8111cd0: **buckets = 0x8111cdc, size = 1110 0x8111cdc: buckets[0] = 0x8111ce0111 buckets 0: 0x8111ce0: {value = "0x810d3c8 ", len = 2, name = "cn" }112 value = NULL113 hash = 0x810d3c8: **buckets = 0x810d3d4, size = 1114 0x810d3d4: buckets[0] = 0x810d3e0115 buckets 0: 0x810d3e0: {value = "0x810d378 ", len = 3, name = "com" }116 value = NULL117 hash = 0x810d378: **buckets = 0x810d384, size = 1118 0x810d384: buckets[0] = 0x810d3a0119 buckets 0: 0x810d3a0 {value = "220.181.111.147", len = 5, name = "baidu" }120 buckets 0: 0x8111ce8: {value = "0x8111c80 ", len = 3, name = "com" }121 value = "220.181.111.147"122 hash = 0x8111c80: **buckets = 0x8111c8c, size = 1123 0x8111c8c: buckets[0] = 0x8111ca0124 buckets 0: 0x8111ca0 {value = "220.181.111.147", len = 5, name = "baidu" }125 buckets 0: 0x8111cac {value = "220.181.111.147", len = 6, name = "google" }126 value = NULL127 hash = 0x8111d70: **buckets = 0x8111d7c, size = 1128 0x8111d7c: buckets[0] = 0x8111d80129 buckets 0: 0x8111d80: {value = "0x8111d20 ", len = 3, name = "www" }130 value = NULL131 hash = 0x8111d20: **buckets = 0x8111d2c, size = 1132 0x8111d2c: buckets[0] = 0x8111d40133 buckets 0: 0x8111d40 {value = "117.40.196.26" , len = 6, name = "abo321" }134 135 --------------------------------136 the pool:137 --------------------------------138 pool = 0x810d020139 .d140 .last = 0x810d418141 .end = 0x810d420142 .next = 0x8111c70143 .failed = 0144 .max = 984145 .current = 0x810d020146 .chain = (nil)147 .large = (nil)148 .cleanup = (nil)149 .log = 0x8051518150 available pool memory = 8151 152 pool = 0x8111c70153 .d154 .last = 0x8111dc0155 .end = 0x8112070156 .next = (nil)157 .failed = 0158 .max = 135339148159 .current = 0x1160 .chain = 0x810d0d8161 .large = 0x8111ca0162 .cleanup = (nil)163 .log = (nil)164 available pool memory = 688165 166 --------------------------------167 find test:168 --------------------------------169 (url = "*.com" , key = 40256957 ) found, (ip = "220.181.111.147")170 (url = "*.baidu.com.cn" , key = 234385007 ) found, (ip = "220.181.111.147")171 (url = "*.baidu.com" , key = -724157846 ) found, (ip = "220.181.111.147")172 (url = ".baidu.com" , key = 1733355200 ) found, (ip = "220.181.111.147")173 (url = "*.google.com" , key = -1465170800) found, (ip = "220.181.111.147")174 (url = "www.sina.com.cn", key = 1528635686 ) found, (ip = "58.63.236.35 ")175 (url = "www.google.com" , key = -702889725 ) found, (ip = "74.125.71.105 ")176 (url = "www.qq.com" , key = 203430122 ) found, (ip = "60.28.14.190 ")177 (url = "www.163.com" , key = -640386838 ) found, (ip = "123.103.14.237 ")178 (url = "www.sohu.com" , key = 1313636595 ) found, (ip = "219.234.82.50 ")179 (url = "abo321.org" , key = 1050805370 ) found, (ip = "117.40.196.26 ")180 (url = ".abo321.org" , key = -4578520 ) not found!181 (url = "www.abo321.*" , key = 1494696375 ) found, (ip = "117.40.196.26 ")182 183 (url = "*.xx.xx" , key = 51835370 ) not found!184 (url = "www.baidu.com" , key = 270263191 ) found, (ip = "220.181.111.147")185 (url = "www.baidu." , key = -239024726 ) not found!