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的数据结构定义如下：
typedef struct {
void *value; //ip，也就是<key,value>中的key
u_short len; //url长度
u_char name[]; //url，也就是<key,value>中的value
} ngx_hash_elt_t;
typedef struct {
ngx_hash_elt_t **buckets; //每个桶的起始地址
ngx_uint_t size; //桶的个数
} 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的，具体如下：
typedef struct {
ngx_hash_t hash;
void *value;
} ngx_hash_wildcard_t;
这个结构相比ngx_hash_t结构就是多了一个value指针，value这个字段是用来存放某个已经达到末尾的通配符url对应的value值，如果通配符url没有达到末尾，这个字段为NULL。
1.3 ngx_hash_init_t
ngx_hash_init_t结构主要用于提供创建一个hash所需要的一些信息，定义如下：
typedef struct {
ngx_hash_t *hash; //指向待新建的hash表
ngx_hash_key_pt key; //hash函数指针
ngx_uint_t max_size; //hash表中桶的最大值,实际桶的个数存放在前面ngx_hash_t中的size字段中
ngx_uint_t bucket_size; //每个桶的最大尺寸
char *name; //hash表的名字，其实没啥用（在log中用）
ngx_pool_t *pool; //构建hash所用的内存池
ngx_pool_t *temp_pool; //构建hash所用的临时内存池
} 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函数的时候可以看到。
typedef struct {
ngx_str_t key; //<key,value>中的key
ngx_uint_t key_hash; //key通过hash函数算出的hash值
void *value; //<key,value>中的value
} ngx_hash_key_t;
1.5 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，hash字段表示不保护通配符的hash，wc_head字段表示包含前缀通配符的hash，wc_tail表示包含后缀通配符的hash。由于用户配置的url通常会是是不包含通配符的url，包含前缀通配符的url和包含后缀通配符的rul中的一种或多种，所以一般使用这个结构来完全表示用户配置的url。
1.6 ngx_hash_keys_arrays_t
typedef struct {
ngx_uint_t hsize;
ngx_pool_t *pool;
ngx_pool_t *temp_pool;
ngx_array_t keys; //存放不包含通配符的<key,value>键值对
ngx_array_t *keys_hash; //用来检测冲突的
ngx_array_t dns_wc_head; //存放包含前缀通配符的<key,value>键值对
ngx_array_t *dns_wc_head_hash; //用来检测冲突的
ngx_array_t dns_wc_tail; //存放包含后缀通配符的<key,value>键值对
ngx_array_t *dns_wc_tail_hash; //用来检测冲突的
} 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，函数原型如下：
ngx_int_t
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>键值对，具体如下：
#define NGX_HASH_ELT_SIZE(name) \
(sizeof(void *) + ngx_align((name)->key.len + , sizeof(void *))) for (n = ; n < nelts; n++) {
if (hinit->bucket_size < NGX_HASH_ELT_SIZE(&names[n]) + sizeof(void *))
{
ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, ,
"could not build the %s, you should "
"increase %s_bucket_size: %i",
hinit->name, hinit->name, hinit->bucket_size);
return NGX_ERROR;
}
}
上面的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中桶的个数
bucket_size = hinit->bucket_size - sizeof(void *); //除去桶标记后桶的大小
start = nelts / (bucket_size / ( * sizeof(void *))); //桶的最小个数
start = start ? start : ;
if (hinit->max_size > && nelts && hinit->max_size / nelts < ) {
start = hinit->max_size - ;
}
//更新size来满足bucket_size
for (size = start; size < hinit->max_size; size++) {
ngx_memzero(test, size * sizeof(u_short));
for (n = ; n < nelts; n++) {
if (names[n].key.data == NULL) {
continue;
}
key = names[n].key_hash % size; //计算当前<key,value>在哪个桶
test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n])); //计算当前<key,value>插入到桶之后桶的大小 if (test[key] > (u_short) bucket_size) { //检查桶是否溢出了
goto next;
}
}
goto found;
next:
continue;
从最小桶的个数开始递增，直到所有的<key,value>键值对都能存放在对应的桶中不溢出，那当前的桶个数就是需要的桶个数。
（3）计算新创建的hash所占用的空间，并调用内存分配函数分配这些空间
for (i = ; i < size; i++) {
test[i] = sizeof(void *);
}
//计算每个桶的实际大小
for (n = ; n < nelts; n++) {
if (names[n].key.data == NULL) {
continue;
}
key = names[n].key_hash % size;
test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
}
//计算所有桶的大小
len = ;
for (i = ; i < size; i++) {
if (test[i] == sizeof(void *)) {
continue;
}
test[i] = (u_short) (ngx_align(test[i], ngx_cacheline_size)); //每个桶大小满足cache行对齐
len += test[i];
}
上面根据实际的<key,value>键值对来实际计算每个桶的大小，而不是所有桶的大小的设置成一样的，这样能很有效的节约内存空间，当然由于每个桶的大小是不固定的，所有每个桶的末尾需要一个额外空间（大小为sizeof(void*)）来标记桶的结束。并且每个桶大小满足cache行对齐，这样能加快访问速度，从这里也可以看出nginx无处不在优化程序的性能和资源的使用效率。
if (hinit->hash == NULL) { //hash为NULL，则动态生成管理hash的结构
//calloc会把获取的内存初始化为0
hinit->hash = ngx_pcalloc(hinit->pool, sizeof(ngx_hash_wildcard_t)
+ size * sizeof(ngx_hash_elt_t *));
if (hinit->hash == NULL) {
ngx_free(test);
return NGX_ERROR;
}
buckets = (ngx_hash_elt_t **)
((u_char *) hinit->hash + sizeof(ngx_hash_wildcard_t));
} else {
buckets = ngx_pcalloc(hinit->pool, size * sizeof(ngx_hash_elt_t *));
if (buckets == NULL) {
ngx_free(test);
return NGX_ERROR;
}
}
elts = ngx_palloc(hinit->pool, len + ngx_cacheline_size); //将所有桶占用的空间分配在连续的内存空间中
if (elts == NULL) {
ngx_free(test);
return NGX_ERROR;
}
elts = ngx_align_ptr(elts, ngx_cacheline_size);
for (i = ; i < size; i++) {
if (test[i] == sizeof(void *)) {
continue;
}
buckets[i] = (ngx_hash_elt_t *) elts; //初始化每个桶的起始位置
elts += test[i];
}
上面代码先动态分配每个桶的起始指针，然后动态分配所有桶的空间，然后根据每个桶的大小，将每个桶的起始指针初始化指向对应桶的起始地址。
（4）将每个<key,value>键值对复制到所在的桶中
for (i = ; i < size; i++) {
test[i] = ;
}
for (n = ; n < nelts; n++) {
if (names[n].key.data == NULL) {
continue;
}
key = names[n].key_hash % size; //计算当前<key,value>所在的桶
elt = (ngx_hash_elt_t *) ((u_char *) buckets[key] + test[key]); //计算当前<key,value>所在桶中的位置
//将当前<key,value>的值复制到桶中
elt->value = names[n].value;
elt->len = (u_short) names[n].key.len;
ngx_strlow(elt->name, names[n].key.data, names[n].key.len);
test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n])); //更新当前桶的大小
}
//为了标记每个桶的结束
for (i = ; i < size; i++) {
if (buckets[i] == NULL) {
continue;
}
elt = (ngx_hash_elt_t *) ((u_char *) buckets[i] + test[i]);
elt->value = NULL; //前面每个test加上sizeof(void *)就是为了这个value指针
}
通过调用ngx_hash_init函数，一个hash就建立起来了，该hash大概的情况如下图所示：
2.2 ngx_hash_add_key
ngx_int_t
ngx_hash_add_key(ngx_hash_keys_arrays_t *ha, ngx_str_t *key, void *value,
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
void *
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
ngx_int_t
ngx_hash_wildcard_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names,
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结构的。
for (n = ; n < nelts; n = i) {
dot = ;
//以.作为字段的分隔符
for (len = ; len < names[n].key.len; len++) {
if (names[n].key.data[len] == '.') {
dot = ;
break;
}
}
name = ngx_array_push(&curr_names);
if (name == NULL) {
return NGX_ERROR;
}
//将上面获取的字段作为当前hash的key
name->key.len = len;
name->key.data = names[n].key.data;
name->key_hash = hinit->key(name->key.data, name->key.len);
name->value = names[n].value;
dot_len = len + ;
if (dot) {
len++;
}
//收集同一前缀的所有后缀
next_names.nelts = ;
if (names[n].key.len != len) {
next_name = ngx_array_push(&next_names);
if (next_name == NULL) {
return NGX_ERROR;
}
next_name->key.len = names[n].key.len - len;
next_name->key.data = names[n].key.data + len;
next_name->key_hash = ;
next_name->value = names[n].value;
}
for (i = n + ; i < nelts; i++) {
if (ngx_strncmp(names[n].key.data, names[i].key.data, len) != ) {
break;
}
if (!dot
&& names[i].key.len > len
&& names[i].key.data[len] != '.')
{
break;
}
next_name = ngx_array_push(&next_names);
if (next_name == NULL) {
return NGX_ERROR;
}
next_name->key.len = names[i].key.len - dot_len;
next_name->key.data = names[i].key.data + dot_len;
next_name->key_hash = ;
next_name->value = names[i].value;
}
if (next_names.nelts) { //next_names中有元素
h = *hinit;
h.hash = NULL;
//递归建立当前字段的所有后缀字段组成的hash
if (ngx_hash_wildcard_init(&h, (ngx_hash_key_t *) next_names.elts,
next_names.nelts)
!= NGX_OK)
{
return NGX_ERROR;
}
wdc = (ngx_hash_wildcard_t *) h.hash;
if (names[n].key.len == len) { //当前字段已经达到末尾
wdc->value = names[n].value;
}
//将后缀组成的下一级hash地址作为当前字段的value保存下来
name->value = (void *) ((uintptr_t) wdc | (dot ? : )); //2只有在后缀通配符的情况下才会出现
} else if (dot) { //只有一个，而且不是后缀通配符
name->value = (void *) ((uintptr_t) name->value | );
}
}
//根据<当前字段,value>键值对建立hash
if (ngx_hash_init(hinit, (ngx_hash_key_t *) curr_names.elts,
curr_names.nelts)
!= NGX_OK)
{
return NGX_ERROR;
}
return NGX_OK;
}
怎样标记一个键值对<key,value>中的value是指向实际的value，还是指向下一级的hash地址，这是上面代码实现的一个巧妙的地方。由于每个hash表的地址或者实际value的地址都是以4字节对齐的，所以这些地址的低2位都是0，这样通过这两位的标记可以很好地解决这个问题。
2.5 ngx_hash_find_wc_head
void *
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）测试的数据如下：
static ngx_str_t urls[Max_Num] = {
ngx_string("*.com"), //220.181.111.147
ngx_string("*.baidu.com.cn"),
ngx_string("*.baidu.com"),
ngx_string(".baidu.com"),
ngx_string("*.google.com"),
ngx_string("www.sina.com.cn"), //58.63.236.35
ngx_string("www.google.com"), //74.125.71.105
ngx_string("www.qq.com"), //60.28.14.190
ngx_string("www.163.com"), //123.103.14.237
ngx_string("www.sohu.com"), //219.234.82.50
ngx_string("abo321.org"), //117.40.196.26
ngx_string(".abo321.org"), //117.40.196.26
ngx_string("www.abo321.*") //117.40.196.26
};
static ngx_str_t values[Max_Num] = {
ngx_string("220.181.111.147"),
ngx_string("220.181.111.147"),
ngx_string("220.181.111.147"),
ngx_string("220.181.111.147"),
ngx_string("220.181.111.147"),
ngx_string("58.63.236.35"),
ngx_string("74.125.71.105"),
ngx_string("60.28.14.190"),
ngx_string("123.103.14.237"),
ngx_string("219.234.82.50"),
ngx_string("117.40.196.26"),
ngx_string("117.40.196.26"),
ngx_string("117.40.196.26")
};
（2）测试代码为：https://github.com/cc1989/nginx_report/tree/master/nginx_test/hash
（3）测试结果
--------------------------------
create a new pool:
--------------------------------
pool = 0x810d020
.d
.last = 0x810d048
.end = 0x810d420
.next = (nil)
.failed =
.max =
.current = 0x810d020
.chain = (nil)
.large = (nil)
.cleanup = (nil)
.log = 0x8051518
available pool memory = --------------------------------
create and add urls to it:
--------------------------------
array = 0xbfed53b4
.elts = 0xb7542008
.nelts =
.size =
.nalloc =
.pool = 0x810d450
elements:
0xb7542008: {key = ("www.sina.com.cn", ), key_hash = , value = "58.63.236.35" }
0xb7542018: {key = ("www.google.com" , ), key_hash = - , value = "74.125.71.105" }
0xb7542028: {key = ("www.qq.com" , ), key_hash = , value = "60.28.14.190" }
0xb7542038: {key = ("www.163.com" , ), key_hash = - , value = "123.103.14.237" }
0xb7542048: {key = ("www.sohu.com" , ), key_hash = , value = "219.234.82.50" }
0xb7542058: {key = ("abo321.org" , ), key_hash = , value = "117.40.196.26" } array = 0xbfed53cc
.elts = 0xb7501008
.nelts =
.size =
.nalloc =
.pool = 0x810d450
elements:
0xb7501008: {key = ("com." , ), key_hash = , value = "220.181.111.147"}
0xb7501018: {key = ("cn.com.baidu." , ), key_hash = , value = "220.181.111.147"}
0xb7501028: {key = ("com.baidu." , ), key_hash = , value = "220.181.111.147"}
0xb7501038: {key = ("com.google." , ), key_hash = , value = "220.181.111.147"} array = 0xbfed53e4
.elts = 0xb74c0008
.nelts =
.size =
.nalloc =
.pool = 0x810d450
elements:
0xb74c0008: {key = ("www.abo321" , ), key_hash = , value = "117.40.196.26" } --------------------------------
the pool:
--------------------------------
pool = 0x810d020
.d
.last = 0x810d2a9
.end = 0x810d420
.next = (nil)
.failed =
.max =
.current = 0x810d020
.chain = (nil)
.large = (nil)
.cleanup = (nil)
.log = 0x8051518
available pool memory = array = 0xbfed53cc
.elts = 0xb7501008
.nelts =
.size =
.nalloc =
.pool = 0x810d450
elements:
0xb7501008: {key = ("cn.com.baidu." , ), key_hash = , value = "220.181.111.147"}
0xb7501018: {key = ("com." , ), key_hash = , value = "220.181.111.147"}
0xb7501028: {key = ("com.baidu." , ), key_hash = , value = "220.181.111.147"}
0xb7501038: {key = ("com.google." , ), key_hash = , value = "220.181.111.147"} array = 0xbfed53e4
.elts = 0xb74c0008
.nelts =
.size =
.nalloc =
.pool = 0x810d450
elements:
0xb74c0008: {key = ("www.abo321" , ), key_hash = , value = "117.40.196.26" } --------------------------------
the hash:
--------------------------------
hash = 0xbfed53fc: **buckets = 0x810d2ac, size =
0x810d2ac: buckets[] = 0x810d2c0
0x810d2b0: buckets[] = 0x810d300
0x810d2b4: buckets[] = 0x810d320 key : buckets : 0x810d320: {value = "58.63.236.35" , len = , name = "www.sina.com.cn"}
key -: buckets : 0x810d300: {value = "74.125.71.105" , len = , name = "www.google.com" }
key : buckets : 0x810d338: {value = "60.28.14.190" , len = , name = "www.qq.com" }
key -: buckets : 0x810d2c0: {value = "123.103.14.237" , len = , name = "www.163.com" }
key : buckets : 0x810d2d4: {value = "219.234.82.50" , len = , name = "www.sohu.com" }
key : buckets : 0x810d348: {value = "117.40.196.26" , len = , name = "abo321.org" }
value = NULL
hash = 0x8111cd0: **buckets = 0x8111cdc, size =
0x8111cdc: buckets[] = 0x8111ce0
buckets : 0x8111ce0: {value = "0x810d3c8 ", len = , name = "cn" }
value = NULL
hash = 0x810d3c8: **buckets = 0x810d3d4, size =
0x810d3d4: buckets[] = 0x810d3e0
buckets : 0x810d3e0: {value = "0x810d378 ", len = , name = "com" }
value = NULL
hash = 0x810d378: **buckets = 0x810d384, size =
0x810d384: buckets[] = 0x810d3a0
buckets : 0x810d3a0 {value = "220.181.111.147", len = , name = "baidu" }
buckets : 0x8111ce8: {value = "0x8111c80 ", len = , name = "com" }
value = "220.181.111.147"
hash = 0x8111c80: **buckets = 0x8111c8c, size =
0x8111c8c: buckets[] = 0x8111ca0
buckets : 0x8111ca0 {value = "220.181.111.147", len = , name = "baidu" }
buckets : 0x8111cac {value = "220.181.111.147", len = , name = "google" }
value = NULL
hash = 0x8111d70: **buckets = 0x8111d7c, size =
0x8111d7c: buckets[] = 0x8111d80
buckets : 0x8111d80: {value = "0x8111d20 ", len = , name = "www" }
value = NULL
hash = 0x8111d20: **buckets = 0x8111d2c, size =
0x8111d2c: buckets[] = 0x8111d40
buckets : 0x8111d40 {value = "117.40.196.26" , len = , name = "abo321" } --------------------------------
the pool:
--------------------------------
pool = 0x810d020
.d
.last = 0x810d418
.end = 0x810d420
.next = 0x8111c70
.failed =
.max =
.current = 0x810d020
.chain = (nil)
.large = (nil)
.cleanup = (nil)
.log = 0x8051518
available pool memory = pool = 0x8111c70
.d
.last = 0x8111dc0
.end = 0x8112070
.next = (nil)
.failed =
.max =
.current = 0x1
.chain = 0x810d0d8
.large = 0x8111ca0
.cleanup = (nil)
.log = (nil)
available pool memory = --------------------------------
find test:
--------------------------------
(url = "*.com" , key = ) found, (ip = "220.181.111.147")
(url = "*.baidu.com.cn" , key = ) found, (ip = "220.181.111.147")
(url = "*.baidu.com" , key = - ) found, (ip = "220.181.111.147")
(url = ".baidu.com" , key = ) found, (ip = "220.181.111.147")
(url = "*.google.com" , key = -) found, (ip = "220.181.111.147")
(url = "www.sina.com.cn", key = ) found, (ip = "58.63.236.35 ")
(url = "www.google.com" , key = - ) found, (ip = "74.125.71.105 ")
(url = "www.qq.com" , key = ) found, (ip = "60.28.14.190 ")
(url = "www.163.com" , key = - ) found, (ip = "123.103.14.237 ")
(url = "www.sohu.com" , key = ) found, (ip = "219.234.82.50 ")
(url = "abo321.org" , key = ) found, (ip = "117.40.196.26 ")
(url = ".abo321.org" , key = - ) not found!
(url = "www.abo321.*" , key = ) found, (ip = "117.40.196.26 ") (url = "*.xx.xx" , key = ) not found!
(url = "www.baidu.com" , key = ) found, (ip = "220.181.111.147")
(url = "www.baidu." , key = - ) not found!