Apache中的哈希表剖析(1)|apache,哈希,hash-中国源码网

3.4 哈希表

3.4.1哈希表概述

作为线性数据结构，与前面所说的表格和队列等相比，哈希表无疑是查找速度比较快的一种。APR中较好的支持哈希表。APR中哈希表在文件apr_hash.h和apr_hash.c中实现。其数据结构定义如下：

struct apr_hash_t {–

apr_pool_t *pool;

apr_hash_entry_t **array;

apr_hash_index_t iterator; /* For apr_hash_first(NULL, ...) */

unsigned int count, max;

apr_hashfunc_t hash_func;

apr_hash_entry_t *free; /* List of recycled entries */

};

与其余的数据结构类似，第一个成员通常是分配该结构的内存池。哈希表中的每一个元素都用apr_hash_entry_t结构描述，array指向一个数组，该数组中每一个元素都是一个指向apr_hash_entry_t类型的链表。为了方便对哈希表的迭代循环遍历，每个结构中都维持一个apr_hash_index_t用以辅助迭代，该成员的详细细节我们在后面的部分会深入讨论。

count用以记录当前整个哈希表中结点的总数目。max则是当前哈希表中允许的哈希值的最大值，反映到结构中就是array数组中的元素的个数。

hash_func则是哈希函数，通过该函数可以确定给定元素在哈希表中的索引，可以使用默认的哈希函数，也可以使用自定义的哈希函数。

现在我们来看一下哈希表元素数据结构apr_hash_entry_t，该结构定义如下：

struct apr_hash_entry_t {

apr_hash_entry_t *next;

unsigned int hash;

const void *key;

apr_ssize_t klen;

const void *val;

};

hash是当前元素在哈希表中所对应的哈希索引值，key则是哈希项的键，value则是哈希项的值。哈希表中以键值key作为唯一的标识索引。如果键值存在冲突，那么这些冲突键将用链表关联起来。整个哈希表的结构可以用下面的图描述：

3.4.2哈希表创建

3.4.2.1 零创建

APR中创建一个哈希表可以通过两种途径：apr_hash_make和apr_hash_make_custom实现：

APR_DECLARE(apr_hash_t *) apr_hash_make(apr_pool_t *pool);

APR_DECLARE(apr_hash_t *) apr_hash_make_custom(apr_pool_t *pool, apr_hashfunc_t hash_func);

两者的区别就是哈希算法的不同。对于apr_hash_make而言，它的主要的工作就是创建apr_hash_t结构，并对其中的成员进行初始化，其中哈希元素的个数被初始化为16个，同时使用默认的哈希算法apr_hashfunc_default，而apr_hash_make_custom则使用自定义的哈希函数hash_func。

unsigned int apr_hashfunc_default(const char *char_key, apr_ssize_t *klen)

{

unsigned int hash = 0;

const unsigned char *key = (const unsigned char *)char_key;

const unsigned char *p;

apr_ssize_t i;

if (*klen == APR_HASH_KEY_STRING) {

for (p = key; *p; p++) {

hash = hash * 33 + *p;

}

*klen = p - key;

}

else {

for (p = key, i = *klen; i; i--, p++) {

hash = hash * 33 + *p;

}

return hash;

}

对于给定的键值key，apr_hashfunc_default返回它在哈希表中的索引。默认哈希算法采用了目前最为流行的times 33哈希算法，目前该算法被广泛使用在多个软件项目包括perl和巴克利(Berkeley DB)数据库中。对于字符串而言这是目前所知道的最好的哈希算法，原因在于该算法的速度非常快，而且分类非常好。

不过你不愿意使用该索引算法而希望使用自己的，那么你可以使用apr_hash_make_custom函数，它接受一个自定义的哈希算法函数，并将其赋值给apr_hash_t结构内的func成员，从而取代默认算法函数。

apr_hashfunc_t函数指针定义如下：

typedef unsigned int (*apr_hashfunc_t)(const char *key, apr_ssize_t *klen);

它需要两个参数，一个是需要进行哈希计算的键，另一个则是该键的长度。函数返回计算后的索引。

3.4.2.2 拷贝创建

与大部分数据结构一样，对于哈希表，APR也提供了拷贝创建方法，允许从一个已有的哈希表创建一个新的哈希表，拷贝函数声明如下：

APR_DECLARE(apr_hash_t *) apr_hash_copy(apr_pool_t *pool,const apr_hash_t *orig)

orig是源哈希表，在拷贝中所用所有的内存都来自内存池pool，拷贝后的哈希表由函数返回。

APR_DECLARE(apr_hash_t *) apr_hash_copy(apr_pool_t *pool,const apr_hash_t *orig)

{

apr_hash_t *ht;

apr_hash_entry_t *new_vals;