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域名支持前置或者后置的通配符（不支持通配符在域名的中间）。

本节会以一个完整的通配符散列表为例来说明这个容器的用法。

7.7.1　ngx_hash_t基本散列表

散列表是根据元素的关键码值而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数f叫做散列方法，存放记录的数组叫做散列表。

若结构中存在关键字和K相等的记录，则必定在f（K）的存储位置上。由此，不需要比较便可直接取得所查记录。我们称这个对应关系f为散列方法，按这个思想建立的表则为散列表。

对于不同的关键字，可能得到同一散列地址，即关键码key1≠key2，而f（key1）=f（key2），这种现象称为碰撞。对该散列方法来说，具有相同函数值的关键字称做同义词。综上所述，根据散列方法H（key）和处理碰撞的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称为散列地址。

若对于关键字集合中的任一个关键字，经散列方法映象到地址集合中任何一个地址的概率是相等的，则称此类散列方法为均匀散列方法，这就使关键字经过散列方法得到了一个“随机的地址”，从而减少了碰撞。

1.如何解决碰撞问题

如果得知散列表中的所有元素，那么可以设计出“完美”的散列方法，使得所有的元素经过f（K）散列方法运算后得出的值都不同，这样就避免了碰撞问题。然而，通用的散列表是不可能预知散列表中的所有元素的，这样，通用的散列表都需要解决碰撞问题。

当散列表出现碰撞时要如何解决呢？一般有两个简单的解决方法：分离链接法和开放寻址法。

分离链接法，就是把散列到同一个槽中的所有元素都放在散列表外的一个链表中，这样查询元素时，在找到这个槽后，还得遍历链表才能找到正确的元素，以此来解决碰撞问题。

开放寻址法，即所有元素都存放在散列表中，当查找一个元素时，要检查规则内的所有的表项（例如，连续的非空槽或者整个空间内符合散列方法的所有槽），直到找到所需的元素，或者最终发现元素不在表中。开放寻址法中没有链表，也没有元素存放在散列表外。

Nginx的散列表使用的是开放寻址法。

开放寻址法有许多种实现方式，Nginx使用的是连续非空槽存储碰撞元素的方法。例如，当插入一个元素时，可以按照散列方法找到指定槽，如果该槽非空且其存储的元素与待插入元素并非同一元素，则依次检查其后连续的槽，直到找到一个空槽来放置这个元素为止。查询元素时也是使用类似的方法，即从散列方法指定的位置起检查连续的非空槽中的元素。

2.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指出散列表中槽的总数。

图　7-10　ngx_hash_t基本散列表的结构示意图

ngx_hash_t散列表还提供了ngx_hash_find方法用于查询元素，下面先来看一下它的定义。

voidngx_hash_find（ngx_hash_thash,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。

3.ngx_hash_t的散列方法

Nginx设计了ngx_hash_key_pt散列方法指针，也就是说，完全可以按照ngx_hash_key_pt的函数原型自定义散列方法，如下所示。

typedef ngx_uint_t（ngx_hash_key_pt）（u_chardata,size_t len）；

其中，传入的data是元素关键字的首地址，而len是元素关键字的长度。可以把任意的数据结构强制转换为u_char*并传给ngx_hash_key_pt散列方法，从而决定返回什么样的散列整型关键码来使碰撞率降低。

当然，Nginx也提供了两种基本的散列方法，它会假定关键字是字符串。如果关键字确实是字符串，那么可以使用表7-8提供的散列方法。

这两种散列方法的区别仅仅在于ngx_hash_key_lc将关键字字符串全小写后再调用ngx_hash_key来计算关键码。