Open Linkerist opened 5 years ago
支持通配符的散列表是Nginx独创的。Nginx首先实现了基础的常用散列表，在这个基础上，它又根据Web服务器的特点，对于URI域名这种场景设计了支持通配符的散列表，当然，只支持前置通配符和后置通配符，如www.test.和.test.com。Nginx对于这种散列表做了非常多的优化设计，它的实现较为复杂。在7.7节中，将会非常详细地描述它的实现，当然，如果只是使用这种散列表，并不需要完全看懂7.7节，可以只看一下7.7.3节的例子，这将会简单许多。不过，要想能够灵活地修改Nginx的各种使用散列表的代码，还是建议读者仔细阅读一下7.7节的内容。 散列表（也叫哈希表）是典型的以空间换时间的数据结构，在一些合理的假设下，对任意元素的检索、插入速度的期望时间为O(1)，这种高效的方式非常适合频繁读取、插入、删除元素，以及对速度敏感的场合。因此，散列表在以效率、性能著称的Nginx服务器中得到了广泛的应用。 注意，Nginx不只提供了基本的散列表。Nginx作为一个Web服务器，它的各种散列表中的关键字多以字符串为主，特别是URI域名，如www.test.com 。这时一个基本的要求就出现了，如何让散列表支持通配符呢？前面在2.4.1节中介绍了nginx.conf中主机名称的配置，这里的主机域名是允许以作为通配符的，包括前置通配符，如.test.com，或者后置通配符，如www.test.*。Nginx封装了ngx_hash_combined_t容器，专门针对URI域名支持前置或者后置的通配符（不支持通配符在域名的中间）。
ngx_hash_t基本散列表 散列表是根据元素的关键码值而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数f叫作散列方法，存放记录的数组叫做散列表。 若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需要比较便可直接取得所查记录。我们称这个对应关系f为散列方法，按这个思想建立的表则为散列表。 对于不同的关键字，可能得到同一散列地址，即关键码key1≠key2，而f(key1)=f(key2)，这种现象称为碰撞。对该散列方法来说，具有相同函数值的关键字称作同义词。综上所述，根据散列方法H(key)和处理碰撞的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称为散列地址。 若对于关键字集合中的任一个关键字，经散列方法映象到地址集合中任何一个地址的概率是相等的，则称此类散列方法为均匀散列方法，这就使关键字经过散列方法得到了一个“随机的地址”，从而减少了碰撞。
如何解决碰撞问题 如果得知散列表中的所有元素，那么可以设计出“完美”的散列方法，使得所有的元素经过f(K)散列方法运算后得出的值都不同，这样就避免了碰撞问题。然而，通用的散列表是不可能预知散列表中的所有元素的，这样，通用的散列表都需要解决碰撞问题。 当散列表出现碰撞时要如何解决呢？一般有两个简单的解决方法：分离链接法和开放寻址法。 分离链接法，就是把散列到同一个槽中的所有元素都放在散列表外的一个链表中，这样查询元素时，在找到这个槽后，还得遍历链表才能找到正确的元素，以此来解决碰撞问题。 开放寻址法，即所有元素都存放在散列表中，当查找一个元素时，要检查规则内的所有的表项（例如，连续的非空槽或者整个空间内符合散列方法的所有槽），直到找到所需的元素，或者最终发现元素不在表中。开放寻址法中没有链表，也没有元素存放在散列表外。 Nginx的散列表使用的是开放寻址法。 开放寻址法有许多种实现方式，Nginx使用的是连续非空槽存储碰撞元素的方法。例如，当插入一个元素时，可以按照散列方法找到指定槽，如果该槽非空且其存储的元素与待插入元素并非同一元素，则依次检查其后连续的槽，直到找到一个空槽来放置这个元素为止。查询元素时也是使用类似的方法，即从散列方法指定的位置起检查连续的非空槽中的元素。
ngx_hash_t散列表的实现 对于散列表中的元素，Nginx使用ngx_hash_elt_t结构体来存储。下面看一下ngx_hash_elt_t的成员，代码如下。
typedef struct { /* 指向用户自定义元素数据的指针，如果当前ngx_hash_elt_t槽为空，则value的值为0 */ void value; /* 元素关键字的长度 */ u_short len; /* 元素关键字的首地址 */ u_char name[1]; } ngx_hash_elt_t;
每一个散列表槽都由1个ngx_hash_elt_t结构体表示，当然，这个槽的大小与ngx_hash_elt_t结构体的大小（也就是sizeof(ngx_hash_elt_t)）是不相等的，这是因为name成员只用于指出关键字的首地址，而关键字的长度是可变长度。那么，一个槽究竟占用多大的空间呢？其实这是在初始化散列表时决定的。基本的散列表由ngx_hash_t结构体表示，如下所示。
typedef struct { // 指向散列表的首地址，也是第1个槽的地址 ngx_hash_elt_t **buckets; // 散列表中槽的总数 ngx_uint_t size; } ngx_hash_t;
因此，在分配buckets成员时就决定了每个槽的长度（限制了每个元素关键字的最大长度），以及整个散列表所占用的空间。在7.7.2节中将会介绍Nginx提供的散列表初始化方法。 如图7-10所示，散列表的每个槽的首地址都是ngx_hash_elt_t结构体，value成员指向用户有意义的结构体，而len是当前这个槽中name（也就是元素的关键字）的有效长度。ngx_hash_t散列表的buckets指向了散列表的起始地址，而size指出散列表中槽的总数。 ngx_hash_t散列表还提供了ngx_hash_find方法用于查询元素，下面先来看一下它的定义。
void ngx_hash_find(ngx_hash_t hash, ngx_uint_t key, u_char *name, size_t len)
其中，参数hash是散列表结构体的指针，而key则是根据散列方法算出来的散列关键字，name和len则表示实际关键字的地址与长度。ngx_hash_find的执行结果就是返回散列表中关键字与name、len指定关键字完全相同的槽中，ngx_hash_elt_t结构体中value成员所指向的用户数据。如果ngx_hash_find没有查询到这个元素，就会返回NULL。
ngx_hash_t的散列方法 Nginx设计了ngx_hash_key_pt散列方法指针，也就是说，完全可以按照ngx_hash_key_pt的函数原型自定义散列方法，如下所示。
typedef ngx_uint_t (*ngx_hash_key_pt) (u_char *data, size_t len);
其中，传入的data是元素关键字的首地址，而len是元素关键字的长度。可以把任意的数据结构强制转换为u_char*并传给ngx_hash_key_pt散列方法，从而决定返回什么样的散列整型关键码来使碰撞率降低。 当然，Nginx也提供了两种基本的散列方法，它会假定关键字是字符串。如果关键字确实是字符串，那么可以使用表7-8提供的散列方法。 这两种散列方法的区别仅仅在于ngx_hash_key_lc将关键字字符串全小写后再调用ngx_hash_key来计算关键码。
支持通配符的散列表 如果散列表元素的关键字是URI域名，Nginx设计了支持简单通配符的散列表ngx_hash_combined_t，那么它可以支持简单的前置通配符或者后置通配符。
原理 所谓支持通配符的散列表，就是把基本散列表中元素的关键字，用去除通配符以后的字符作为关键字加入，原理其实很简单。例如，对于关键字为“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.字符串再开始查询（如图7-11所示）。 Nginx封装了ngx_hash_wildcard_t结构体，专用于表示前置或者后置通配符的散列表。
typedef struct { // 基本散列表 ngx_hash_t hash; /* 当使用这个ngx_hash_wildcard_t通配符散列表作为某容器的元素时，可以使用这个value指针指向用户数据 */ void value; } ngx_hash_wildcard_t;
实际上，ngx_hash_wildcard_t只是对ngx_hash_t进行了简单的封装，所加的value指针其用途也是多样化的。ngx_hash_wildcard_t同时提供了两种方法，分别用于查询前置或者后置通配符的元素，见表7-9。 下面回顾一下Nginx对于server_name主机名通配符的支持规则。
实际上，上面介绍的这个规则就是Nginx实现的ngx_hash_combined_t通配符散列表的规则。下面先来看一下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;
如图7-12所示，ngx_hash_combined_t是由3个散列表所组成：第1个散列表hash是普通的基本散列表，第2个散列表wc_head所包含的都是带前置通配符的元素，第3个散列表wc_tail所包含的都是带后置通配符的元素。
Note: 前置通配符散列表中元素的关键字，在把*通配符去掉后，会按照“.”符号分隔，并以倒序的方式作为关键字来存储元素。相应的，在查询元素时也是做相同处理。
在查询元素时，可以使用ngx_hash_combined_t提供的方法ngx_hash_find_combined，下面先来看看它的定义（它的参数、返回值含义与ngx_hash_find_wc_head或者ngx_hash_find_wc_tail方法相同）。
void ngx_hash_find_combined(ngx_hash_combined_t hash, ngx_uint_t key, u_char *name,size_t len);
在实际向ngx_hash_combined_t通配符散列表查询元素时，ngx_hash_find_combined方法的活动图如图7-13所示，这是有严格顺序的，即当1个查询关键字同时匹配3个散列表时，一定是返回普通的完全匹配散列表的相应元素。
如何初始化 上文中对于普通的散列表和通配符散列表的原理和查询方法做了详细的解释，实际上，Nginx也封装了完善的初始化方法，以用于这些散列表，并且Nginx还具备在初始化时添加通配符元素的能力。鉴于此，如果功能较多，初始化方法的使用就会有些复杂。下面介绍一下初始化方法的使用。 Nginx专门提供了ngx_hash_init_t结构体用于初始化散列表，代码如下。
typedef struct { // 指向普通的完全匹配散列表 ngx_hash_t *hash; // 用于初始化预添加元素的散列方法 ngx_hash_key_pt key; // 散列表中槽的最大数目 ngx_uint_t max_size; // 散列表中一个槽的空间大小，它限制了每个散列表元素关键字的最大长度 ngx_uint_t bucket_size; // 散列表的名称 char name; /* 内存池，它分配散列表（最多3个，包括1个普通散列表、1个前置通配符散列表、1个后置通配符散列表）中的所有槽 */ ngx_pool_t pool; /* 临时内存池，它仅存在于初始化散列表之前。它主要用于分配一些临时的动态数组，带通配符的元素在初始化时需要用到这些数组 */ ngx_pool_t temp_pool; } ngx_hash_init_t;
ngx_hash_init_t结构体的用途只在于初始化散列表，到底初始化散列表时会预分配多少个槽呢？这并不完全由max_size成员决定的，而是由在做初始化准备时预先加入到散列表的所有元素决定的，包括这些元素的总数、每个元素关键字的长度等，还包括操作系统一个页面的大小。这个算法较复杂，可以在ngx_hash_init_t函数中得到。我们在使用它时只需要了解在初始化后每个ngx_hash_t结构体中的size成员不由ngx_hash_init_t完全决定即可。图7-14显示了ngx_hash_init_t结构体及其支持的方法。 ngx_hash_init_t的这两个方法负责将ngx_hash_keys_arrays_t中的相应元素初始化到散列表中，表7-10描述了这两个初始化方法的用法。 表7-10的两个方法都用到了ngx_hash_key_t结构，下面简单地介绍一下它的成员。实际上，如果只是使用散列表，完全可以不用关心ngx_hash_key_t的结构，但为了更深入地理解和应用还是简要介绍一下它。
typedef struct { // 元素关键字 ngx_str_t key; // 由散列方法算出来的关键码 ngx_uint_t key_hash; // 指向实际的用户数据 void *value; } ngx_hash_key_t;
ngx_hash_keys_arrays_t对应的ngx_hash_add_key方法负责构造ngx_hash_key_t结构。下面来看一下ngx_hash_keys_arrays_t结构体，它不负责构造散列表，然而它却是使用ngx_hash_init或者ngx_hash_wildcard_init方法的前提条件，换句话说，如果先构造好了ngx_hash_keys_arrays_t结构体，就可以非常简单地调用ngx_hash_init或者ngx_hash_wildcard_init方法来创建支持通配符的散列表了。
typedef struct { /* 下面的keys_hash、dns_wc_head_hash、dns_wc_tail_hash都是简易散列表，而hsize指明了散列表的槽个数，其简易散列方法也需要对hsize求余 */ ngx_uint_t hsize; /* 内存池，用于分配永久性内存，到目前的Nginx版本为止，该pool成员没有任何意义 */ ngx_pool_t pool; // 临时内存池，下面的动态数组需要的内存都由temp_pool内存池分配 ngx_pool_t *temp_pool; // 用动态数组以ngx_hash_key_t结构体保存着不含有通配符关键字的元素 ngx_array_t keys; /* * 一个极其简易的散列表，它以数组的形式保存着hsize个元素，每个元素都是ngx_array_t动态 * 数组。在用户添加的元素过程中，会根据关键码将用户的ngx_str_t类型的关键字添加到 * ngx_array_t动态数组中。这里所有的用户元素的关键字都不可以带通配符，表示精确匹配 */ ngx_array_t keys_hash; /* 用动态数组以ngx_hash_key_t结构体保存着含有前置通配符关键字的元素生成的中间关键字 */ ngx_array_t dns_wc_head; // 一个极其简易的散列表，它以数组的形式保存着hsize个元素，每个元素都是ngx_array_t动态数组。在用户添加元素过程中，会根据关键码将用户的ngx_str_t类型的关键字添加到ngx_array_t动态数组中。这里所有的用户元素的关键字都带前置通配符 ngx_array_t dns_wc_head_hash; // 用动态数组以ngx_hash_key_t结构体保存着含有后置通配符关键字的元素生成的中间关键字 ngx_array_t dns_wc_tail; // 一个极其简易的散列表，它以数组的形式保存着hsize个元素，每个元素都是ngx_array_t动态数组。在用户添加元素过程中，会根据关键码将用户的ngx_str_t类型的关键字添加到ngx_array_t动态数组中。这里所有的用户元素的关键字都带后置通配符 ngx_array_t dns_wc_tail_hash; } ngx_hash_keys_arrays_t;
如图7-15所示，ngx_hash_keys_arrays_t中的3个动态数组容器keys、dns_wc_head、dns_wc_tail会以ngx_hash_key_t结构体作为元素类型，分别保存完全匹配关键字、带前置通配符的关键字、带后置通配符的关键字。同时，ngx_hash_keys_arrays_t建立了3个简易的散列表keys_hash、dns_wc_head_hash、dns_wc_tail_hash，这3个散列表用于快速向上述3个动态数组容器中插入元素。 为什么要设立这3个简易散列表呢？如果没有这3个散列表，在向keys、dns_wc_head、dns_wc_tail动态数组添加元素时，为了避免出现相同关键字的元素，每添加一个关键字元素都需要遍历整个数组。有了keys_hash、dns_wc_head_hash、dns_wc_tail_hash这3个简易散列表后，每向keys、dns_wc_head、dns_wc_tail动态数组添加1个元素时，就用这个元素的关键字计算出散列码，然后按照散列码在keys_hash、dns_wc_head_hash、dns_wc_tail_hash散列表中的相应位置建立ngx_array_t动态数组，动态数组中的每个元素是ngx_str_t，它指向关键字字符串。这样，再次添加同名关键字时，就可以由散列码立刻获得曾经添加的关键字，以此来判定是否合法或者进行元素合并操作。 ngx_hash_keys_arrays_t之所以设计得比较复杂，是为了让keys、dns_wc_head、dns_wc_tail这3个动态数组中存放的都是有效的元素。表7-11介绍了ngx_hash_keys_arrays_t提供的两个方法。 ngx_hash_keys_array_init方法的type参数将会决定ngx_hash_keys_arrays_t中3个简易散列表的大小。当type为NGX_HASH_SMALL时，这3个散列表中槽的数目为107个；当type为NGX_HASH_LARGE时，这3个散列表中槽的数目为10007个。 在使用ngx_hash_keys_array_init初始化ngx_hash_keys_arrays_t结构体后，就可以调用ngx_hash_add_key方法向其加入散列表元素了。当添加元素成功后，再调用ngx_hash_init_t提供的两个初始化方法来创建散列表，这样得到的散列表就是完全可用的容器了。
带通配符散列表的使用例子 散列表元素ngx_hash_elt_t中value指针指向的数据结构为下面定义的TestWildcardHash-Node结构体，代码如下。
typedef struct { // 用于散列表中的关键字 ngx_str_t servername; // 这个成员仅是为了方便区别而已 ngx_int_t seq; } TestWildcardHashNode;
每个散列表元素的关键字是servername字符串。下面先定义ngx_hash_init_t和ngx_hash_keys_arrays_t变量，为初始化散列表做准备，代码如下。
// 定义用于初始化散列表的结构体 ngx_hash_init_t hash; /* ngx_hash_keys_arrays_t用于预先向散列表中添加元素，这里的元素支持带通配符 */ ngx_hash_keys_arrays_t ha; // 支持通配符的散列表 ngx_hash_combined_t combinedHash; ngx_memzero(&ha, sizeof(ngx_hash_keys_arrays_t));
combinedHash是我们定义的用于指向散列表的变量，它包括指向3个散列表的指针，下面会依次给这3个散列表指针赋值。
// 临时内存池只是用于初始化通配符散列表，在初始化完成后就可以销毁掉 ha.temp_pool = ngx_create_pool(16384, cf->log); if (ha.temp_pool == NULL) { return NGX_ERROR; } /* 由于这个例子是在ngx_http_mytest_postconf函数中的，所以就用了ngx_conf_t 类型的cf下的内存池作为散列表的内存池 */ ha.pool = cf->pool;
调用ngx_hash_keys_array_init方法来初始化ha，为下一步向ha中加入散列表元素做好准备，代码如下。
if (ngx_hash_keys_array_init(&ha, NGX_HASH_LARGE) != NGX_OK) { return NGX_ERROR; }
本节按照图7-12和图7-15中的例子建立3个数据，并且会覆盖7.7节中介绍的散列表内容。我们建立的testHashNode[3]这3个TestWildcardHashNode类型的结构体，分别表示可以用前置通配符匹配的散列表元素、可以用后置通配符匹配的散列表元素、需要完全匹配的散列表元素。
TestWildcardHashNode testHashNode[3]; testHashNode[0].servername.len = ngx_strlen(".test.com"); testHashNode[0].servername.data = ngx_pcalloc(cf->pool, ngx_strlen(".test.com")); ngx_memcpy(testHashNode[0].servername.data,".test.com",ngx_strlen(".test.com")); testHashNode[1].servername.len = ngx_strlen("www.test.*"); testHashNode[1].servername.data = ngx_pcalloc(cf->pool, ngx_strlen("www.test.*")); ngx_memcpy(testHashNode[1].servername.data,"www.test.*",ngx_strlen("www.test.*")); testHashNode[2].servername.len = ngx_strlen("www.test.com"); testHashNode[2].servername.data = ngx_pcalloc(cf->pool, ngx_strlen("www.test.com")); ngx_memcpy(testHashNode[2].servername.data,"www.test.com",ngx_strlen("www.test.com"));
下面通过调用ngx_hash_add_key方法将testHashNode[3]这3个成员添加到ha中。
for (i = 0; i < 3; i++) { testHashNode[i].seq = i; ngx_hash_add_key(&ha, &testHashNode[i].servername, &testHashNode[i],NGX_HASH_WILDCARD_KEY); }
注意，在上面添加散列表元素时，flag设置为NGX_HASH_WILDCARD_KEY，这样才会处理带通配符的关键字。 在调用ngx_hash_init_t的初始化函数前，先得设置好ngx_hash_init_t中的成员，如槽的大小、散列方法等，如下所示。
hash.key = ngx_hash_key_lc; hash.max_size = 100; hash.bucket_size = 48; hash.name = "test_server_name_hash"; hash.pool = cf->pool;
ha的keys动态数组中存放的是需要完全匹配的关键字，如果keys数组不为空，那么开始初始化第1个散列表，代码如下。
if (ha.keys.nelts) { /* 需要显式地把ngx_hash_init_t中的hash指针指向combinedHash中的完全匹配散列表 */ hash.hash = &combinedHash.hash; // 初始化完全匹配散列表时不会使用到临时内存池 hash.temp_pool = NULL; /* 将keys动态数组直接传给ngx_hash_init方法即可，ngx_hash_init_t中的hash指针就是初始化成功的散列表 */ if (ngx_hash_init(&hash, ha.keys.elts, ha.keys.nelts) != NGX_OK) { return NGX_ERROR; } }
下面继续初始化前置通配符散列表，代码如下。
if (ha.dns_wc_head.nelts) { hash.hash = NULL; // 注意，ngx_hash_wildcard_init方法需要使用临时内存池 hash.temp_pool = ha.temp_pool; if (ngx_hash_wildcard_init(&hash, ha.dns_wc_head.elts, ha.dns_wc_head.nelts)!= NGX_OK) { return NGX_ERROR; } /* ngx_hash_init_t中的hash指针是ngx_hash_wildcard_init初始化成功的散列表，需要将它赋到combinedHash.wc_head前置通配符散列表指针中 */ combinedHash.wc_head = (ngx_hash_wildcard_t ) hash.hash; }
下面继续初始化后置通配符散列表，代码如下。
if (ha.dns_wc_tail.nelts) { hash.hash = NULL; // 注意，ngx_hash_wildcard_init方法需要使用临时内存池 hash.temp_pool = ha.temp_pool; if (ngx_hash_wildcard_init(&hash, ha.dns_wc_tail.elts, ha.dns_wc_tail.nelts)!= NGX_OK) { return NGX_ERROR; } /* ngx_hash_init_t中的hash指针是ngx_hash_wildcard_init初始化成功的散列表，需要将它赋到combinedHash.wc_tail后置通配符散列表指针中 */ combinedHash.wc_tail = (ngx_hash_wildcard_t ) hash.hash; }
到此，临时内存池已经没有存在的意义了，也就是说，ngx_hash_keys_arrays_t中的这些数组、简易散列表都可以销毁了。这时，只需要简单地把temp_pool内存池销毁就可以了，代码如下。
ngx_destroy_pool(ha.temp_pool);
下面检查一下散列表是否工作正常。首先，查询关键字www.test.org，实际上，它应该匹配后置通配符散列表中的元素www.test.*，代码如下。
// 首先定义待查询的关键字字符串findServer ngx_str_t findServer; findServer.len = ngx_strlen("www.test.org"); /* 为什么必须要在内存池中分配空间以保存关键字呢？因为我们使用的散列方法是ngx_hash_key_lc，它会试着把关键字全小写 */ findServer.data = ngx_pcalloc(cf->pool, ngx_strlen("www.test.org")); ngx_memcpy(findServer.data,"www.test.org",ngx_strlen("www.test.org")); /* ngx_hash_find_combined方法会查找出www.test.*对应的散列表元素，返回其指向的用户数据ngx_hash_find_combined，也就是testHashNode[1] */ TestWildcardHashNode* findHashNode = ngx_hash_find_combined(&combinedHash, 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对应的元素。
findServer.len = ngx_strlen("www.test.com"); findServer.data = ngx_pcalloc(cf->pool, ngx_strlen("www.test.com")); ngx_memcpy(findServer.data,"www.test.com",ngx_strlen("www.test.com")); findHashNode = ngx_hash_find_combined(&combinedHash, ngx_hash_key_lc(findServer.data, findServer.len), findServer.data, findServer.len);
下面测试一下后置通配符散列表。如果查询的关键字是“smtp.test.com”，那么查询到的应该是关键字为*.test.com的元素testHashNode[0]。
findServer.len = ngx_strlen("smtp.test.com"); findServer.data = ngx_pcalloc(cf->pool, ngx_strlen("smtp.test.com")); ngx_memcpy(findServer.data,"smtp.test.com",ngx_strlen("smtp.test.com")); findHashNode = ngx_hash_find_combined(&combinedHash, ngx_hash_key_lc(findServer.data, findServer.len), findServer.data, findServer.len);
本文暂取自代码、网络或书籍，只用作学习备忘，不作盈利等他用，如有侵权，请联系Linkerist@163.com
支持通配符的散列表是Nginx独创的。Nginx首先实现了基础的常用散列表，在这个基础上，它又根据Web服务器的特点，对于URI域名这种场景设计了支持通配符的散列表，当然，只支持前置通配符和后置通配符，如www.test.和.test.com。Nginx对于这种散列表做了非常多的优化设计，它的实现较为复杂。在7.7节中，将会非常详细地描述它的实现，当然，如果只是使用这种散列表，并不需要完全看懂7.7节，可以只看一下7.7.3节的例子，这将会简单许多。不过，要想能够灵活地修改Nginx的各种使用散列表的代码，还是建议读者仔细阅读一下7.7节的内容。 散列表（也叫哈希表）是典型的以空间换时间的数据结构，在一些合理的假设下，对任意元素的检索、插入速度的期望时间为O(1)，这种高效的方式非常适合频繁读取、插入、删除元素，以及对速度敏感的场合。因此，散列表在以效率、性能著称的Nginx服务器中得到了广泛的应用。 注意，Nginx不只提供了基本的散列表。Nginx作为一个Web服务器，它的各种散列表中的关键字多以字符串为主，特别是URI域名，如www.test.com 。这时一个基本的要求就出现了，如何让散列表支持通配符呢？前面在2.4.1节中介绍了nginx.conf中主机名称的配置，这里的主机域名是允许以作为通配符的，包括前置通配符，如.test.com，或者后置通配符，如www.test.*。Nginx封装了ngx_hash_combined_t容器，专门针对URI域名支持前置或者后置的通配符（不支持通配符在域名的中间）。
ngx_hash_t基本散列表 散列表是根据元素的关键码值而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数f叫作散列方法，存放记录的数组叫做散列表。 若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需要比较便可直接取得所查记录。我们称这个对应关系f为散列方法，按这个思想建立的表则为散列表。 对于不同的关键字，可能得到同一散列地址，即关键码key1≠key2，而f(key1)=f(key2)，这种现象称为碰撞。对该散列方法来说，具有相同函数值的关键字称作同义词。综上所述，根据散列方法H(key)和处理碰撞的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称为散列地址。 若对于关键字集合中的任一个关键字，经散列方法映象到地址集合中任何一个地址的概率是相等的，则称此类散列方法为均匀散列方法，这就使关键字经过散列方法得到了一个“随机的地址”，从而减少了碰撞。
如何解决碰撞问题 如果得知散列表中的所有元素，那么可以设计出“完美”的散列方法，使得所有的元素经过f(K)散列方法运算后得出的值都不同，这样就避免了碰撞问题。然而，通用的散列表是不可能预知散列表中的所有元素的，这样，通用的散列表都需要解决碰撞问题。 当散列表出现碰撞时要如何解决呢？一般有两个简单的解决方法：分离链接法和开放寻址法。 分离链接法，就是把散列到同一个槽中的所有元素都放在散列表外的一个链表中，这样查询元素时，在找到这个槽后，还得遍历链表才能找到正确的元素，以此来解决碰撞问题。 开放寻址法，即所有元素都存放在散列表中，当查找一个元素时，要检查规则内的所有的表项（例如，连续的非空槽或者整个空间内符合散列方法的所有槽），直到找到所需的元素，或者最终发现元素不在表中。开放寻址法中没有链表，也没有元素存放在散列表外。 Nginx的散列表使用的是开放寻址法。 开放寻址法有许多种实现方式，Nginx使用的是连续非空槽存储碰撞元素的方法。例如，当插入一个元素时，可以按照散列方法找到指定槽，如果该槽非空且其存储的元素与待插入元素并非同一元素，则依次检查其后连续的槽，直到找到一个空槽来放置这个元素为止。查询元素时也是使用类似的方法，即从散列方法指定的位置起检查连续的非空槽中的元素。
ngx_hash_t散列表的实现 对于散列表中的元素，Nginx使用ngx_hash_elt_t结构体来存储。下面看一下ngx_hash_elt_t的成员，代码如下。
每一个散列表槽都由1个ngx_hash_elt_t结构体表示，当然，这个槽的大小与ngx_hash_elt_t结构体的大小（也就是sizeof(ngx_hash_elt_t)）是不相等的，这是因为name成员只用于指出关键字的首地址，而关键字的长度是可变长度。那么，一个槽究竟占用多大的空间呢？其实这是在初始化散列表时决定的。基本的散列表由ngx_hash_t结构体表示，如下所示。
因此，在分配buckets成员时就决定了每个槽的长度（限制了每个元素关键字的最大长度），以及整个散列表所占用的空间。在7.7.2节中将会介绍Nginx提供的散列表初始化方法。 如图7-10所示，散列表的每个槽的首地址都是ngx_hash_elt_t结构体，value成员指向用户有意义的结构体，而len是当前这个槽中name（也就是元素的关键字）的有效长度。ngx_hash_t散列表的buckets指向了散列表的起始地址，而size指出散列表中槽的总数。
ngx_hash_t散列表还提供了ngx_hash_find方法用于查询元素，下面先来看一下它的定义。
其中，参数hash是散列表结构体的指针，而key则是根据散列方法算出来的散列关键字，name和len则表示实际关键字的地址与长度。ngx_hash_find的执行结果就是返回散列表中关键字与name、len指定关键字完全相同的槽中，ngx_hash_elt_t结构体中value成员所指向的用户数据。如果ngx_hash_find没有查询到这个元素，就会返回NULL。
ngx_hash_t的散列方法 Nginx设计了ngx_hash_key_pt散列方法指针，也就是说，完全可以按照ngx_hash_key_pt的函数原型自定义散列方法，如下所示。
其中，传入的data是元素关键字的首地址，而len是元素关键字的长度。可以把任意的数据结构强制转换为u_char*并传给ngx_hash_key_pt散列方法，从而决定返回什么样的散列整型关键码来使碰撞率降低。 当然，Nginx也提供了两种基本的散列方法，它会假定关键字是字符串。如果关键字确实是字符串，那么可以使用表7-8提供的散列方法。
这两种散列方法的区别仅仅在于ngx_hash_key_lc将关键字字符串全小写后再调用ngx_hash_key来计算关键码。
支持通配符的散列表 如果散列表元素的关键字是URI域名，Nginx设计了支持简单通配符的散列表ngx_hash_combined_t，那么它可以支持简单的前置通配符或者后置通配符。
原理 所谓支持通配符的散列表，就是把基本散列表中元素的关键字，用去除通配符以后的字符作为关键字加入，原理其实很简单。例如，对于关键字为“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.字符串再开始查询（如图7-11所示）。
Nginx封装了ngx_hash_wildcard_t结构体，专用于表示前置或者后置通配符的散列表。
实际上，ngx_hash_wildcard_t只是对ngx_hash_t进行了简单的封装，所加的value指针其用途也是多样化的。ngx_hash_wildcard_t同时提供了两种方法，分别用于查询前置或者后置通配符的元素，见表7-9。
下面回顾一下Nginx对于server_name主机名通配符的支持规则。
实际上，上面介绍的这个规则就是Nginx实现的ngx_hash_combined_t通配符散列表的规则。下面先来看一下ngx_hash_combined_t的结构，代码如下。
如图7-12所示，ngx_hash_combined_t是由3个散列表所组成：第1个散列表hash是普通的基本散列表，第2个散列表wc_head所包含的都是带前置通配符的元素，第3个散列表wc_tail所包含的都是带后置通配符的元素。
在查询元素时，可以使用ngx_hash_combined_t提供的方法ngx_hash_find_combined，下面先来看看它的定义（它的参数、返回值含义与ngx_hash_find_wc_head或者ngx_hash_find_wc_tail方法相同）。
在实际向ngx_hash_combined_t通配符散列表查询元素时，ngx_hash_find_combined方法的活动图如图7-13所示，这是有严格顺序的，即当1个查询关键字同时匹配3个散列表时，一定是返回普通的完全匹配散列表的相应元素。
如何初始化 上文中对于普通的散列表和通配符散列表的原理和查询方法做了详细的解释，实际上，Nginx也封装了完善的初始化方法，以用于这些散列表，并且Nginx还具备在初始化时添加通配符元素的能力。鉴于此，如果功能较多，初始化方法的使用就会有些复杂。下面介绍一下初始化方法的使用。 Nginx专门提供了ngx_hash_init_t结构体用于初始化散列表，代码如下。
ngx_hash_init_t结构体的用途只在于初始化散列表，到底初始化散列表时会预分配多少个槽呢？这并不完全由max_size成员决定的，而是由在做初始化准备时预先加入到散列表的所有元素决定的，包括这些元素的总数、每个元素关键字的长度等，还包括操作系统一个页面的大小。这个算法较复杂，可以在ngx_hash_init_t函数中得到。我们在使用它时只需要了解在初始化后每个ngx_hash_t结构体中的size成员不由ngx_hash_init_t完全决定即可。图7-14显示了ngx_hash_init_t结构体及其支持的方法。
ngx_hash_init_t的这两个方法负责将ngx_hash_keys_arrays_t中的相应元素初始化到散列表中，表7-10描述了这两个初始化方法的用法。
表7-10的两个方法都用到了ngx_hash_key_t结构，下面简单地介绍一下它的成员。实际上，如果只是使用散列表，完全可以不用关心ngx_hash_key_t的结构，但为了更深入地理解和应用还是简要介绍一下它。
ngx_hash_keys_arrays_t对应的ngx_hash_add_key方法负责构造ngx_hash_key_t结构。下面来看一下ngx_hash_keys_arrays_t结构体，它不负责构造散列表，然而它却是使用ngx_hash_init或者ngx_hash_wildcard_init方法的前提条件，换句话说，如果先构造好了ngx_hash_keys_arrays_t结构体，就可以非常简单地调用ngx_hash_init或者ngx_hash_wildcard_init方法来创建支持通配符的散列表了。
如图7-15所示，ngx_hash_keys_arrays_t中的3个动态数组容器keys、dns_wc_head、dns_wc_tail会以ngx_hash_key_t结构体作为元素类型，分别保存完全匹配关键字、带前置通配符的关键字、带后置通配符的关键字。同时，ngx_hash_keys_arrays_t建立了3个简易的散列表keys_hash、dns_wc_head_hash、dns_wc_tail_hash，这3个散列表用于快速向上述3个动态数组容器中插入元素。
为什么要设立这3个简易散列表呢？如果没有这3个散列表，在向keys、dns_wc_head、dns_wc_tail动态数组添加元素时，为了避免出现相同关键字的元素，每添加一个关键字元素都需要遍历整个数组。有了keys_hash、dns_wc_head_hash、dns_wc_tail_hash这3个简易散列表后，每向keys、dns_wc_head、dns_wc_tail动态数组添加1个元素时，就用这个元素的关键字计算出散列码，然后按照散列码在keys_hash、dns_wc_head_hash、dns_wc_tail_hash散列表中的相应位置建立ngx_array_t动态数组，动态数组中的每个元素是ngx_str_t，它指向关键字字符串。这样，再次添加同名关键字时，就可以由散列码立刻获得曾经添加的关键字，以此来判定是否合法或者进行元素合并操作。
ngx_hash_keys_arrays_t之所以设计得比较复杂，是为了让keys、dns_wc_head、dns_wc_tail这3个动态数组中存放的都是有效的元素。表7-11介绍了ngx_hash_keys_arrays_t提供的两个方法。
ngx_hash_keys_array_init方法的type参数将会决定ngx_hash_keys_arrays_t中3个简易散列表的大小。当type为NGX_HASH_SMALL时，这3个散列表中槽的数目为107个；当type为NGX_HASH_LARGE时，这3个散列表中槽的数目为10007个。
在使用ngx_hash_keys_array_init初始化ngx_hash_keys_arrays_t结构体后，就可以调用ngx_hash_add_key方法向其加入散列表元素了。当添加元素成功后，再调用ngx_hash_init_t提供的两个初始化方法来创建散列表，这样得到的散列表就是完全可用的容器了。
带通配符散列表的使用例子 散列表元素ngx_hash_elt_t中value指针指向的数据结构为下面定义的TestWildcardHash-Node结构体，代码如下。
每个散列表元素的关键字是servername字符串。下面先定义ngx_hash_init_t和ngx_hash_keys_arrays_t变量，为初始化散列表做准备，代码如下。
combinedHash是我们定义的用于指向散列表的变量，它包括指向3个散列表的指针，下面会依次给这3个散列表指针赋值。
调用ngx_hash_keys_array_init方法来初始化ha，为下一步向ha中加入散列表元素做好准备，代码如下。
本节按照图7-12和图7-15中的例子建立3个数据，并且会覆盖7.7节中介绍的散列表内容。我们建立的testHashNode[3]这3个TestWildcardHashNode类型的结构体，分别表示可以用前置通配符匹配的散列表元素、可以用后置通配符匹配的散列表元素、需要完全匹配的散列表元素。
下面通过调用ngx_hash_add_key方法将testHashNode[3]这3个成员添加到ha中。
注意，在上面添加散列表元素时，flag设置为NGX_HASH_WILDCARD_KEY，这样才会处理带通配符的关键字。 在调用ngx_hash_init_t的初始化函数前，先得设置好ngx_hash_init_t中的成员，如槽的大小、散列方法等，如下所示。
ha的keys动态数组中存放的是需要完全匹配的关键字，如果keys数组不为空，那么开始初始化第1个散列表，代码如下。
下面继续初始化前置通配符散列表，代码如下。
下面继续初始化后置通配符散列表，代码如下。
到此，临时内存池已经没有存在的意义了，也就是说，ngx_hash_keys_arrays_t中的这些数组、简易散列表都可以销毁了。这时，只需要简单地把temp_pool内存池销毁就可以了，代码如下。
下面检查一下散列表是否工作正常。首先，查询关键字www.test.org，实际上，它应该匹配后置通配符散列表中的元素www.test.*，代码如下。
如果没有查询到的话，那么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对应的元素。
下面测试一下后置通配符散列表。如果查询的关键字是“smtp.test.com”，那么查询到的应该是关键字为*.test.com的元素testHashNode[0]。
本文暂取自代码、网络或书籍，只用作学习备忘，不作盈利等他用，如有侵权，请联系Linkerist@163.com