分享
 
 
 

Apache中的哈希表剖析(3)

王朝system·作者佚名  2006-03-18
窄屏简体版  字體: |||超大  

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

3.4.5哈希表合并

在Apache中经常需要将两个哈希表合并为一个新的哈希表,为此APR中提供了专门的哈希合并函数apr_hash_merge,该函数定义如下:

APR_DECLARE(apr_hash_t *) apr_hash_merge(apr_pool_t *p,

const apr_hash_t *h1,

const apr_hash_t *h2,

void * (*merger)(apr_pool_t *p,

const void *key,

apr_ssize_t klen,

const void *h1_val,

const void *h2_val,

const void *data),

const void *data);

h1和h2是两个需要进行合并的哈希表。由于某个键可能同时出现在h1和h2中,而合并后的哈希表中只允许存在一次,因此在新的合并后的哈希表中如何处理h1和h2中相同的键是必须考虑的事情。参数中的merge函数用来处理这种情况。data是传递个合并函数merger的额外参数。

{

apr_hash_t *res;

apr_hash_entry_t *new_vals = NULL;

apr_hash_entry_t *iter;

apr_hash_entry_t *ent;

unsigned int i,j,k;

res = apr_palloc(p, sizeof(apr_hash_t));

res->pool = p;

res->free = NULL;

res->hash_func = base->hash_func;

res->count = base->count;

res->max = (overlay->max > base->max) ? overlay->max : base->max;

if (base->count + overlay->count > res->max) {

res->max = res->max * 2 + 1;

}

res->array = alloc_array(res, res->max);

if (base->count + overlay->count) {

new_vals = apr_palloc(p, sizeof(apr_hash_entry_t) *

(base->count + overlay->count));

}

从大的角度而言,哈希表的合并非常简单:首先创建一个新的哈希表,然后将需要合并的哈希表填入到新哈希表中。创建新的哈希表可以分为三个步骤:

1)、创建apr_hash_t结构。这个可以通过apr_palloc实现,非常简单。

2)、初始化apr_hash_t内部的array数组。数组的大小取决于两方面:

■ 暂时将新哈希表的容量max设定为两个需要合并的哈希表中容量max最大的。

■ 如果现有的两个哈希表中已经使用的元素个数总和超过max,那么max个元素不足以存放两个哈希表中所有的元素,因此最终的容量调整为max*2 + 1。

3)、合并的两个哈希表中apr_hash_entry_t结点数目为bash->count + overlay->count,因此它们所占用的总内存大小为sizeof(apr_hash_entry_t)*(base->count+overlay->count)。合并前,两个哈希表中所有结点都是用链表方式保存,而在合并后所有的结点都用连续内存块保存,这点与前面的哈希表拷贝非常相似。

4)、一旦分配了需要的内存块,我们就必须调整array数组中的指针指向实际的内存。

j = 0;

for (k = 0; k <= base->max; k++) {

for (iter = base->array[k]; iter; iter = iter->next) {

i = iter->hash & res->max;

new_vals[j].klen = iter->klen;

new_vals[j].key = iter->key;

new_vals[j].val = iter->val;

new_vals[j].hash = iter->hash;

new_vals[j].next = res->array[i];

res->array[i] = &new_vals[j];

j++;

}

}

函数首先将第一个哈希表中的所有结点拷贝到上述的内存块中,同时调整array数组中的指针指向这些内存块。拷贝后的内存布局如下所示。

从下图中可以看出,对于源哈希表索引index链表,结点在链表中出现的顺序与在内存块中出现的顺序正好相反:源哈希中array[index]是链表中第一个结点的地址,而在目标哈希表中,array[index]则是链表中的最后一个结点的地址;

在第一次的拷贝中,另外一个重要的方面就是索引不变性。任意一个结点,如果在源哈希表中的索引为index,则它在新哈希表中的索引肯定也是index,这个可以下面的几行代码中看出:

i = iter->hash & res->max;

res->array[i] = &new_vals[j];

5)、当第一个哈希表拷贝到新哈希表后,对于第二个哈希表的处理就开始展开:

for (k = 0; k <= overlay->max; k++) {

for (iter = overlay->array[k]; iter; iter = iter->next) {

i = iter->hash & res->max ; u

for (ent = res->array[i]; ent; ent = ent->next) {

if ((ent->klen == iter->klen) &&

(memcmp(ent->key, iter->key, iter->klen) == 0)) {

if (merger) {

ent->val = (*merger)(p, iter->key, iter->klen,

iter->val, ent->val, data);

}

else {

ent->val = iter->val;

}

break;

}

}

if (!ent) {

new_vals[j].klen = iter->klen;

new_vals[j].key = iter->key;

new_vals[j].val = iter->val;

new_vals[j].hash = iter->hash;

new_vals[j].next = res->array[i];

res->array[i] = &new_vals[j];

res->count++;

j++;

}

}

}

与第一个哈希表的简单拷贝相比,第二个哈希表的处理无非也是将其中的每一个结点拷贝到新的哈希表中,因此最外层的循环为:

for (k = 0; k <= overlay->max; k++) {

for (iter = overlay->array[k]; iter; iter = iter->next) {

……

}

对于每一个结点,函数首先计算它的哈希值i,如u,并根据该哈希值i作出进一步的处理:

1)、如果经过第一次的拷贝之后,新哈希表中索引为i的链表仍然为NULL,那么该结点将直接插入索引i链表中。

2)、如果新哈希表中索引i链表已经存在,那么此时的处理又出现了进一步的分化:

■ 如果在索引i链表中存在一个与当前结点完全相同的结点(键长度相等,且键值完全相同),那么这种情况称之为键冲突,即哈希表1和哈希表2中存在完全相同的结点。对于这种情况通常的处理是由专门的合并函数merger完成,不过如果没有定义该合并函数,默认情况是否直接覆盖val。

■ 如果当前结点在索引i链表中不存在,那么此时意味着这是一个新结点,此时将其追加到索引i链表的尾部。比如哈希表2中的索引3链表,该链表中的结点最终插入到目标哈希表的10、11结点处。此时可以看到,10、11和第一个哈希表中的结点3不再连续,不过它们之间通过next关联在一起,如①所示。

最终合并后新哈希表的内存示意图如图所示。

3.4.6哈希表使用示例

下面的代码演示了哈希表的使用,包括下面几个方面:

1)、哈希表创建

2)、哈希表键/值增加

3)、哈希表键/值检索

4)、哈希表遍历

#include <stdio.h>

#include <stdlib.h>

#include <assert.h>

#include <apr_general.h>

#include <apr_hash.h>

#include <apr_strings.h>

//在哈希表中增加、删除、修改元素

static void modify_hashtab(apr_hash_t *ht, apr_pool_t *mp)

{

apr_hash_set(ht, "foo", APR_HASH_KEY_STRING, "FOO");

apr_hash_set(ht, apr_pstrdup(mp, "bar"), APR_HASH_KEY_STRING, apr_pstrdup(mp, "BAR"));

apr_hash_set(ht, apr_pstrdup(mp, "foobar"), APR_HASH_KEY_STRING, apr_pstrdup(mp, "BAR"));

apr_hash_set(ht, apr_pstrdup(mp, "barfoo"), APR_HASH_KEY_STRING, apr_pstrdup(mp, "FOO"));

/* To delete an entry, pass NULL as a value */

apr_hash_set(ht, apr_pstrdup(mp, "to-del"), APR_HASH_KEY_STRING, apr_pstrdup(mp, "TO-DEL"));

apr_hash_set(ht, "to-del", APR_HASH_KEY_STRING, NULL);

apr_hash_set(ht,apr_pstrdup(mp,"override"),APR_HASH_KEY_STRING,apr_pstrdup(mp,"old-val"));

apr_hash_set(ht,apr_pstrdup(mp,"override"),APR_HASH_KEY_STRING,apr_pstrdup(mp, "new-val"));

}

//迭代整个哈希表

static void iterate_hashtab(apr_hash_t *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);

}

}

int main(int argc, const char *argv[])

{

apr_pool_t *mp;

apr_hash_t *ht;

apr_initialize();

apr_pool_create(&mp, NULL);

ht = apr_hash_make(mp);

modify_hashtab(ht, mp);

{

const char *val = apr_hash_get(ht, "foo", APR_HASH_KEY_STRING);

printf("val for \"foo\" is %s\n", val);

}

iterate_hashtab(ht);

apr_pool_destroy(mp);

apr_terminate();

return 0;

}

程序运行结果如下:

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有