如何完成 FastDFH 中 hash 的测试？

ljmmail

编制 hash 测试程序，怎么得到系统保存的 value 值不对

/* ** 这是一个针对 dfshash 函数进行测试的程序。 */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include  "dfshash.h" int hash_print(HashArray *pHash) {     HashData **ppBucket;     HashData **bucket_end;     HashData *hash_data;     int count = 0;     bucket_end = pHash->buckets + (*pHash->capacity);     printf("hash capacity = [%d] \n", (*pHash->capacity) );     for (ppBucket=pHash->buckets; ppBucket<bucket_end; ppBucket++)     {       count ++;         if (*ppBucket == NULL)         {             continue;         }         hash_data = *ppBucket;     printf("hash_code[%03d] %12d %s XXX", count-1, hash_data->hash_code, hash_data->key);         while (hash_data != NULL)         {           printf("%s  ", hash_data->value);             hash_data = hash_data->next;         }         printf("\n");     }     return 0; } int  main(int ac ,  char  *av[]) {     HashArray   pHash;     HashData   *Ph;     int  i1;     char  key[32];     char  vale[32];     hash_init(&pHash, DFH_Time33Hash, 10, 0.8);     for(i1=5; i1< 15; i1 ++ ){        sprintf(key, "key %02d", i1);        sprintf(vale, " 保存键值 %02d ", i1);        hash_insert_ex(&pHash, key, 20, vale, 20);     }     // 将需要处理的数据保存到 hash 桶中     hash_print(&pHash);     hash_stat_print(&pHash);     // 打印基本 hash 桶的分布情况     hash_best_op(&pHash, 10);     // 进行 hash 桶扩展，该扩展后将可以保证 hash 数据的充分分布     hash_print(&pHash);     hash_stat_print(&pHash);     // 打印新的 hash 桶的分布情况     sprintf(key, "key %02d", 20);     Ph = hash_find(&pHash, key, 20);     if(Ph) printf("测试 value [%s]\n", Ph->value);     hash_destroy(&pHash);     return 0; }

程序的测试结果为

hash capacity = [17]
hash_code[000]   -128244380 key 06 XXX 保存键值 14   
hash_code[004]  -1107202109 key 14 XXX 保存键值 14    保存键值 14    保存键值 14   
hash_code[008]   -500076889 key 09 XXX 保存键值 14    保存键值 14    保存键值 14   
hash_code[012]    448397826 key 13 XXX 保存键值 14   
hash_code[013]   -735369600 key 11 XXX 保存键值 14   
hash_code[016]   1055523046 key 08 XXX 保存键值 14   
capacity: 17, item_count=10, bucket_used: 6, avg length: 1.6667, max length: 3, bucket / item = 35.29%
hash capacity = [23]
hash_code[002]   -500076889 key 09 XXX 保存键值 14   
hash_code[003]  -1683844315 key 07 XXX 保存键值 14   
hash_code[004]   1427355555 key 05 XXX 保存键值 14   
hash_code[005]   -735369600 key 11 XXX 保存键值 14   
hash_code[008]   1055523046 key 08 XXX 保存键值 14   
hash_code[009]  -1107202109 key 14 XXX 保存键值 14   
hash_code[010]   2003997761 key 12 XXX 保存键值 14   
hash_code[011]    820230335 key 10 XXX 保存键值 14   
hash_code[015]    448397826 key 13 XXX 保存键值 14   
hash_code[021]   -128244380 key 06 XXX 保存键值 14   
capacity: 23, item_count=10, bucket_used: 10, avg length: 1.0000, max length: 1, bucket / item = 43.48%

怎么 hash 中保存的 value 数值是一致的，我感觉后面保存的参数应该与 key 中的参数一致，为什么不成功？

happy_fish100

默认情况下，hash取值采用的是指针（引用）方式。因为多个key都指向vale数组，所以最后值都是一样的。

按照你的测试脚本，应该采用复制方式。
初试化时使用函数hash_init_ex，hash_init_ex函数声明：
int hash_init_ex(HashArray *pHash, HashFunc hash_func, \
                const unsigned int capacity, const double load_factor, \
                const int64_t max_bytes, const bool bMallocValue);
最后一个参数bMallocValue传递1或true。

你的测试代码对应的地方修改如下：
hash_init(&pHash, DFH_Time33Hash, 10, 0.8, 0, true);

[ 本帖最后由 happy_fish100 于 2009-8-12 18:32 编辑 ]

ljmmail

你好，谢谢回复，根据你提示的修改，重新编译程序通过

新的测试结果为：

hash capacity = [17]
hash_code[001]   1565184731 key 13 XXX 保存键值 13    保存键值 11   
hash_code[005]  -2122657345 key 08 XXX 保存键值 08    保存键值 06   
hash_code[009]      9584796 key 14 XXX 保存键值 14   
hash_code[010]  -1174182630 key 12 XXX 保存键值 12    保存键值 10   
hash_code[013]    616710016 key 09 XXX 保存键值 09   
hash_code[014]   -567057410 key 07 XXX 保存键值 07    保存键值 05   
capacity: 17, item_count=10, bucket_used: 6, avg length: 1.6667, max length: 2, bucket / item = 35.29%
hash capacity = [23]
hash_code[001]   1565184731 key 13 XXX 保存键值 13   
hash_code[002]    381417305 key 11 XXX 保存键值 11   
hash_code[006]      9584796 key 14 XXX 保存键值 14   
hash_code[012]   -567057410 key 07 XXX 保存键值 07   
hash_code[013]  -1750824836 key 05 XXX 保存键值 05   
hash_code[017]  -2122657345 key 08 XXX 保存键值 08   
hash_code[018]    988542525 key 06 XXX 保存键值 06   
hash_code[019]  -1174182630 key 12 XXX 保存键值 12   
hash_code[020]   1937017240 key 10 XXX 保存键值 10   
hash_code[022]    616710016 key 09 XXX 保存键值 09   
capacity: 23, item_count=10, bucket_used: 10, avg length: 1.0000, max length: 1, bucket / item = 43.48%

ljmmail

另外，请问一下， hash_best_op(&pHash, 10 ); 函数使用的 第二个参数需要跟定什么样的数值比较合适？

在 hash_init_ex() 函数后，如果输入多与定义的数据会存在问题吗？

谢谢！！！

ljmmail

另外问个问题，我在使用修改后的程序做一个数据字典的测试，在执行 hash_best_op() 时，竟然 半小时都没有结束，不知什么原因。
附件是本程序的测试用例，本程序中主要是对 数据字典中行数据进行分解，将前面两个字段分别最为 KEY 和 VAL　进行处理。

happy_fish100

原帖由 ljmmail 于 2009-8-12 19:18 发表
另外，请问一下， hash_best_op(&pHash, 10 ); 函数使用的 第二个参数需要跟定什么样的数值比较合适？

在 hash_init_ex() 函数后，如果输入多与定义的数据会存在问题吗？

谢谢！！！

在从来没有优化过的情况下，hash_best_op的第二个参数取值为0即可。如果调用hash_best_op后，通过hash_stat_print可以打印出优化后的capacity。
然后可以将第二个参数值设置为优化后的capacity。因为hash_best_op采用了尝试法（穷举法），这样的目的可以避免穷举，一步到位。

>>在 hash_init_ex() 函数后，如果输入多与定义的数据会存在问题吗？
不会存在任何问题。将初始capacity设置为数据量大小，可以减少rehash次数，出于性能考虑，应尽量避免rehash。

happy_fish100

根据你描述的情况来看，一直在尝试找到合适的capacity，使得每个桶中最多只有一个数据项。

你将
hash_best_op(&pHash, 10000 );
修改为：
hash_best_op(&pHash,  0);
试试。

另外，hash value可以是结构体，感觉你的数据字典按结构体组织使用起来更方便一些？

ljmmail

happy_fish100 好，我按照你介绍的办法对 hash_best_op 进行调整，发现程序执行变化不大， 近 10 分钟没有输出结果，同时主机的 CPU 占用特高，机器反映变慢，不知还有什么调整方法。

我这边对数据字典的时候，现在仅仅考虑每行数据的前两个字段，后边的字段暂时可以忽略。

happy_fish100

我以前稍稍对比测试过，发现PJWHash的分布平均度比较好。
你可以试试PJWHash。

我以前管理的数据字典大约有70多个，采用hash_best_op可以达到每个桶中最多一个数据项，优化后当时的capacity是551。

如果实在不能优化，建议设置适当的初始化capacity来解决，就不要调用hash_best_op了。

ljmmail

谢谢回复，我感觉 hash_best_op() 函数的处理过程太复杂了，该程序是将从一个最小桶空间开始遍历，逐次选择一个新的 素数作为 新的桶基数，这是一个试探的过程，每次 桶 数据重构、核算冲突数的过程是非常麻烦的，导致机器的处理非常麻烦。
我想考虑可否简化 hash_best_op () 的处理过程，该函数处理的基础应该从 实际元素数 + 检测到的冲突数 开始处理， 减少 hash 桶核算试探的次数，使得问题得到解决。