Apache中的哈希表剖析(2)

转载请注明来源:http://blog.csdn.net/tingya

3.4.3数据插入和获取

对于哈希表而言，一个重要的任务就是插入key/value数据以及根据键值获取相应的值。APR中定义了函数apr_hash_set和apr_hash_get分别实现上面的功能。

首先我们来看apr_hash_get函数，该函数需要三个参数，分别用以描述操作的哈希表，键值以及键的长度。

APR_DECLARE(void *) apr_hash_get(apr_hash_t *ht,const void *key,apr_ssize_t klen)

{

apr_hash_entry_t *he;

he = *find_entry(ht, key, klen, NULL);

if (he)

return (void *)he->val;

else

return NULL;

}

从上面的函数可以看到，通过键值查找对应的哈希元素的过程真正的工作是由find_entry完成的，尽管find_entry是一个内部函数，不过它是很多函数的基础，其定义如下：

static apr_hash_entry_t **find_entry(apr_hash_t *ht,const void *key,apr_ssize_t klen,

const void *val)

{

apr_hash_entry_t **hep, *he;

unsigned int hash;

hash = ht->hash_func(key, &klen);

for (hep = &ht->array[hash & ht->max], he = *hep;

he; hep = &he->next, he = *hep) {

if (he->hash == hash

&& he->klen == klen

&& memcmp(he->key, key, klen) == 0)

break;

}

if (he || !val)

return hep;

/* add a new entry for non-NULL values */

if ((he = ht->free) != NULL)

ht->free = he->next;

else

he = apr_palloc(ht->pool, sizeof(*he));

he->next = NULL;

he->hash = hash;

he->key= key;

he->klen = klen;

he->val= val;

*hep = he;

ht->count++;

return hep;

}

整个函数的处理过程可以分为三大部分：

1)、根据键值key计算出它在整个表array中的索引值hash，这个过程非常的简单，通常可以直接调用apr_hash_t内部的hash_func计算获取

2)、正如前面所说，由于哈希值冲突的存在，因此存在多个键值对应同一个索引的情况，所有索引计算结果相同的键都保存在以array[hash]为首地址的链表中。因此对于在确定hash索引之后，下一步必须处理的就是遍历该索引对应的链表，在其中查找是否存在目标结点，当一个结点必须满足下面的条件的时候才能称之为完全匹配：

■ 当前结点的hash值与计算出的哈希值相等。一般情况下，这个条件都是满足的，因为不相等的话不可能挂接到hash索引对应的链表。

■ 键值长度完全相同

■ 键的值完全满足条件

3)、尽管函数的名称为find_entry，这个名字容易让人误会为函数仅仅完成查找功能，事实上并不如此。函数apr_hash_get和apr_hash_set内部都调用了该函数。因此，find_entry并不仅仅是查找，同时还具备增加结点的功能。至于到底是查找还是增加由最后一个参数val决定，如果val为NULL，则函数理所当然为查找，否则为添加。

对于查找功能，函数直接返回找到的元素结点。如果是增加，则将当前结点增加到hash索引链表的最末尾。

3.4.4哈希表迭代遍历

APR中哈希表的遍历遵循的一个原则就是深度遍历原则，按照这种思路，遍历过程首先将hash=0的链表中的所有结点遍历完毕，而后继续遍历hash=1的链表，直至hash=max的链表，这种思路可以用下面的图示描述，红虚线就是哈希表元素的遍历顺序：

在讲解APR中遍历算法之前，我们首先用最普通的方法来实现对哈希表的遍历，下面是遍历的框架代码：

int i=0;

for(;i<max;i++)

{

apr_hash_entry_t *ht;

if(array[i]==NULL)

continue;

ht=array[i];

while(ht!=NULL)

{

//处理该结点，或者打印或者其余操作

DoSomethingAboutTheNode();

ht=ht->next;

}

}

上面的程序基本能够实现对整个哈希表的遍历，而且也很容易理解。但是如果从使用者的角度去考虑一下就很容易发现尽管上面的遍历没有问题，但是对用户而言则并不是很现实。使用上面的遍历算法的一个前提就是用户必须能够知道哈希表的内部实现结构，事实上这个对大部分的用户并不现实，而且哈希表的内部结构通常总是对用户屏蔽的。如果这样，问题又出来了，既然用户不需要了解哈希表的内部实现细节，那么他又从何知道使用上面的遍历代码呢？？

在C++ STL中大部分的容器，比如vector，stack，list以及queue等等，它们内部都支持一种称之为迭代子的类型，该类型允许将容器类型和算法分开来，彼此独立设计，最后再通过胶合剂将它们关联起来，不过这种关联是一种松耦合关系，下面是使用向量(vector)迭代子对向量进行迭代的过程：

vector<int> coll;

……

vector<int>::iterator pos;

for (pos=coll.begin(); pos<coll.end(); ++pos) {

printf(“%d”,*pos);// cout << *pos << ' ';

}

从上面的代码中我们可以看到，对于用户而言根本不需要知道vector的内部细节，它需要知道的仅仅是从begin()访问到end()，至于begin()和end()返回的是不是向量中真正的第一个和最后一个，那不是用户需要考虑的事情。

不过迭代子是范型技术的产物，是和C++紧密联系的，而Apache则是纯C编写的，因此当然不可能直接使用STL，不过它显然是受了STL的影响——它的目的就是使用C语言仿造一个哈希表上的迭代子，使得算法与细节分开。下面是APR中使用仿迭代子对哈希表ht进行遍历的代码：

apr_hash_index_t *hi;

for (hi = apr_hash_first(NULL, ht); hi; hi = apr_hash_next(hi)) {

const char *k;

const char *v;

apr_hash_this(hi, (const void**)&k, NULL, (void**)&v);

printf("ht iteration: key=%s, val=%s\n", k, v);

}

在上面的代码中你根本就看不出哈希表的内部细节。这实际上也达到了我们前面提出的要求。

为了实现仿造的效果，哈希表中引入了一个辅助数据结构apr_hash_index_t，用于记录当前访问的结点的相关索引信息：

struct apr_hash_index_t {

apr_hash_t *ht;

apr_hash_entry_t *this, *next;

unsigned int index;

};

ht是当前访问的哈希表，index是当前访问的结点所在的哈希索引，值从0到max之间。this和next是这个结构的最重要的成员。this用以指向当前正在访问的结点，而next则指向按照深度遍历时this之后下一个将要被访问的结点。在整个遍历过程中，最重要的就是不断地调整this和next的指针，下面是可能出现的情况：

在分析上面的图示的时候，我们给出两个定义：直接后继结点和间接后继结点。

对于某个结点，它的直接后继结点就是可以通过next指针直接获取的结点。比如上图的(1)-(4)，this结点的直接后继结点都是NULL，而(5)中，this的直接后继存在，且为next。

对于某个结点，它的间接后继结点就是按照前述的哈希表深度遍历访问顺序中的下一个结点。对于图(5)，this的间接后继结点就是它的直接后继结点。下表给出了上图中的各个直接后继和间接后继结点的情况：

图	直接后继结点	间接后继结点
(1)	NULL	NULL
(2)	NULL	Not NULL
(3)	NULL	NULL
(4)	NULL	Not NULL
(5)	Not NULL	Not NULL

从上表可以看出(1)-(4)图可以归结为一个大类，那就是this的直接后继都是为NULL，这导致this结点和next结点位于不同的索引链表中，而(5)则是另外一个大类，它的直接后继不为NULL，这导致this和next位于同一链表中。对于给定的this结点，如何获取它的下一个结点？？Apache中使用apr_hash_next函数来获取this结点的下一个结点：

APR_DECLARE(apr_hash_index_t *) apr_hash_next(apr_hash_index_t *hi)

{

hi->this = hi->next;

while (!hi->this) {

if (hi->index > hi->ht->max)

return NULL;

hi->this = hi->ht->array[hi->index++];

}

hi->next = hi->this->next;

return hi;

}

this结点由传入参数hi指定，函数内部计算this的next结点，并继续通过hi返回出去。函数中正是利用了上面所说的分类规律：

■ while循环用于处理上图的(1)(2)(3)(4)四种情况，如果直接后继为NULL，则直接跳至下一个索引链表工作，直到索引为max为止。

■ hi->next=hi->this->next用以处理直接后继不为NULL的情况，那么此时只需要调整next就可以了。

除了apr_hash_next之外，Apache中还提供了另外两个辅助函数apr_hash_first和ap_hash_this。apr_hash_first主要为遍历整个哈希表作必要的准备，并返回整个哈希表的第一个元素的索引结构apr_hash_index_t。该函数需要两个参数：内部索引分配所需要的内存池以及需要遍历的哈希表：

APR_DECLARE(apr_hash_index_t *) apr_hash_first(apr_pool_t *p, apr_hash_t *ht)

{

apr_hash_index_t *hi;

if (p)

hi = apr_palloc(p, sizeof(*hi));

else

hi = &ht->iterator;

hi->ht = ht;

hi->index = 0;

hi->this = NULL;

hi->next = NULL;

return apr_hash_next(hi);

}

函数的前半部分主要进行apr_hash_index_t结构的初始化工作，如果内部具有迭代子，那么直接使用该迭代子，否则创建新的迭代子，并使用该迭代子进行第一次迭代，apr_hash_next将返回哈希表中的第一个元素，同时下一个间接后继结点同时也返回。

apr_hash_this函数主要返回给定结点的各种信息，通常情况下，总是将this指针传递个该函数：

APR_DECLARE(void) apr_hash_this(apr_hash_index_t *hi,const void **key,

apr_ssize_t *klen,void **val)

{

if (key)*key= hi->this->key;

if (klen) *klen = hi->this->klen;

if (val)*val= (void *)hi->this->val;

}

关于作者
张中庆，目前主要的研究方向是嵌入式浏览器，移动中间件以及大规模服务器设计。目前正在进行Apache的源代码分析，计划出版《Apache源代码全景分析》上下册。Apache系列文章为本书的草案部分，对Apache感兴趣的朋友可以通过flydish1234 at sina.com.cn与之联系!

如果你觉得本文不错，请点击文后的“推荐本文”链接！！