Shuffy

不断的学习,不断的思考,才能不断的进步.Let's do better together!
posts - 102, comments - 43, trackbacks - 0, articles - 19

字符串Hash函数评估

Posted on 2011-11-04 14:21 Shuffy 阅读(471) 评论(0)  编辑 收藏 引用

Hash查找因为其O(1)的查找性能而著称,被对查找性能要求高的应用所广泛采用。它的基本思想是:
(1) 创建一个定长的线性Hash表,一般可以初始化时指定length;

(2) 设计Hash函数,将关键字key散射到Hash表中。其中hash函数设计是最为关键的,均匀分布、冲突概率小全在它;

(3) 通常采用拉链方法来解决hash冲突问题,即散射到同一个hash表项的关键字,以链表形式来表示(也称为桶backet);

(4) 给定关键字key,就可以在O(1) + O(m)的时间复杂度内定位到目标。其中,m为拉链长度,即桶深。

 

Hash应用中,字符串是最为常见的关键字,应用非常普通,现在的程序设计语言中基本上都提供了字符串hash表的支持。字符串hash函数非常多,常见的主要有Simple_hash, RS_hash, JS_hash, PJW_hash, ELF_hash, BKDR_hash, SDBM_hash, DJB_hash, AP_hash, CRC_hash等。它们的C语言实现见后面附录代码: hash.h, hash.c。那么这么些字符串hash函数,谁好熟非呢?评估hash函数优劣的基准主要有以下两个指标:

(1) 散列分布性

即桶的使用率backet_usage = (已使用桶数) / (总的桶数),这个比例越高,说明分布性良好,是好的hash设计。

(2) 平均桶长

即avg_backet_len,所有已使用桶的平均长度。理想状态下这个值应该=1,越小说明冲突发生地越少,是好的hash设计。

hash函数计算一般都非常简洁,因此在耗费计算时间复杂性方面判别甚微,这里不作对比。

 

评估方案设计是这样的:

(1) 以200M的视频文件作为输入源,以4KB的块为大小计算MD5值,并以此作为hash关键字;

(2) 分别应用上面提到的各种字符串hash函数,进行hash散列模拟;

(3) 统计结果,用散列分布性和平均桶长两个指标进行评估分析。

 

测试程序见附录代码hashtest.c,测试结果如下表所示。从这个结果我们也可以看出,这些字符串hash函数真是不相仲伯,难以决出高低,所以实际应用中可以根据喜好选择。当然,最好实际测试一下,毕竟应用特点不大相同。其他几组测试结果也类似,这里不再给出。

 

Hash函数 桶数 Hash调用总数 最大桶长 平均桶长 桶使用率%
simple_hash 10240 47198 16 4.63 99.00%
RS_hash 10240 47198 16 4.63 98.91%
JS_hash 10240 47198 15 4.64 98.87%
PJW_hash 10240 47198 16 4.63 99.00%
ELF_hash 10240 47198 16 4.63 99.00%
BKDR_hash 10240 47198 16 4.63 99.00%
SDBM_hash 10240 47198 16 4.63 98.90%
DJB_hash 10240 47198 15 4.64 98.85%
AP_hash 10240 47198 16 4.63 98.96%
CRC_hash 10240 47198 16 4.64 98.77%

附录源代码:

hash.h

 

  1. #ifndef _HASH_H
  2. #define _HASH_H
  3. #ifdef __cplusplus
  4. extern "C" {
  5. #endif
  6. /* A Simple Hash Function */
  7. unsigned int simple_hash(char *str);
  8. /* RS Hash Function */
  9. unsigned int RS_hash(char *str);
  10. /* JS Hash Function */
  11. unsigned int JS_hash(char *str);
  12. /* P. J. Weinberger Hash Function */
  13. unsigned int PJW_hash(char *str);
  14. /* ELF Hash Function */
  15. unsigned int ELF_hash(char *str);
  16. /* BKDR Hash Function */
  17. unsigned int BKDR_hash(char *str);
  18. /* SDBM Hash Function */
  19. unsigned int SDBM_hash(char *str);
  20. /* DJB Hash Function */
  21. unsigned int DJB_hash(char *str);
  22. /* AP Hash Function */
  23. unsigned int AP_hash(char *str);
  24. /* CRC Hash Function */
  25. unsigned int CRC_hash(char *str);
  26. #ifdef __cplusplus
  27. }
  28. #endif
  29. #endif

hash.c

 

  1. #include <string.h>
  2. #include "hash.h"
  3. /* A Simple Hash Function */
  4. unsigned int simple_hash(char *str)
  5. {
  6. register unsigned int hash;
  7. register unsigned char *p;
  8. for(hash = 0, p = (unsigned char *)str; *p ; p++)
  9. hash = 31 * hash + *p;
  10. return (hash & 0x7FFFFFFF);
  11. }
  12. /* RS Hash Function */
  13. unsigned int RS_hash(char *str)
  14. {
  15. unsigned int b = 378551;
  16. unsigned int a = 63689;
  17. unsigned int hash = 0;
  18. while (*str)
  19. {
  20. hash = hash * a + (*str++);
  21. a *= b;
  22. }
  23. return (hash & 0x7FFFFFFF);
  24. }
  25. /* JS Hash Function */
  26. unsigned int JS_hash(char *str)
  27. {
  28. unsigned int hash = 1315423911;
  29. while (*str)
  30. {
  31. hash ^= ((hash << 5) + (*str++) + (hash >> 2));
  32. }
  33. return (hash & 0x7FFFFFFF);
  34. }
  35. /* P. J. Weinberger Hash Function */
  36. unsigned int PJW_hash(char *str)
  37. {
  38. unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
  39. unsigned int ThreeQuarters = (unsigned int)((BitsInUnignedInt * 3) / 4);
  40. unsigned int OneEighth = (unsigned int)(BitsInUnignedInt / 8);
  41. unsigned int HighBits = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
  42. unsigned int hash = 0;
  43. unsigned int test = 0;
  44. while (*str)
  45. {
  46. hash = (hash << OneEighth) + (*str++);
  47. if ((test = hash & HighBits) != 0)
  48. {
  49. hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
  50. }
  51. }
  52. return (hash & 0x7FFFFFFF);
  53. }
  54. /* ELF Hash Function */
  55. unsigned int ELF_hash(char *str)
  56. {
  57. unsigned int hash = 0;
  58. unsigned int x = 0;
  59. while (*str)
  60. {
  61. hash = (hash << 4) + (*str++);
  62. if ((x = hash & 0xF0000000L) != 0)
  63. {
  64. hash ^= (x >> 24);
  65. hash &= ~x;
  66. }
  67. }
  68. return (hash & 0x7FFFFFFF);
  69. }
  70. /* BKDR Hash Function */
  71. unsigned int BKDR_hash(char *str)
  72. {
  73. unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
  74. unsigned int hash = 0;
  75. while (*str)
  76. {
  77. hash = hash * seed + (*str++);
  78. }
  79. return (hash & 0x7FFFFFFF);
  80. }
  81. /* SDBM Hash Function */
  82. unsigned int SDBM_hash(char *str)
  83. {
  84. unsigned int hash = 0;
  85. while (*str)
  86. {
  87. hash = (*str++) + (hash << 6) + (hash << 16) - hash;
  88. }
  89. return (hash & 0x7FFFFFFF);
  90. }
  91. /* DJB Hash Function */
  92. unsigned int DJB_hash(char *str)
  93. {
  94. unsigned int hash = 5381;
  95. while (*str)
  96. {
  97. hash += (hash << 5) + (*str++);
  98. }
  99. return (hash & 0x7FFFFFFF);
  100. }
  101. /* AP Hash Function */
  102. unsigned int AP_hash(char *str)
  103. {
  104. unsigned int hash = 0;
  105. int i;
  106. for (i=0; *str; i++)
  107. {
  108. if ((i & 1) == 0)
  109. {
  110. hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
  111. }
  112. else
  113. {
  114. hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
  115. }
  116. }
  117. return (hash & 0x7FFFFFFF);
  118. }
  119. /* CRC Hash Function */
  120. unsigned int CRC_hash(char *str)
  121. {
  122. unsigned int nleft = strlen(str);
  123. unsigned long long sum = 0;
  124. unsigned short int *w = (unsigned short int *)str;
  125. unsigned short int answer = 0;
  126. /*
  127. * Our algorithm is simple, using a 32 bit accumulator (sum), we add
  128. * sequential 16 bit words to it, and at the end, fold back all the
  129. * carry bits from the top 16 bits into the lower 16 bits.
  130. */
  131. while ( nleft > 1 ) {
  132. sum += *w++;
  133. nleft -= 2;
  134. }
  135. /*
  136. * mop up an odd byte, if necessary
  137. */
  138. if ( 1 == nleft ) {
  139. *( unsigned char * )( &answer ) = *( unsigned char * )w ;
  140. sum += answer;
  141. }
  142. /*
  143. * add back carry outs from top 16 bits to low 16 bits
  144. * add hi 16 to low 16
  145. */
  146. sum = ( sum >> 16 ) + ( sum & 0xFFFF );
  147. /* add carry */
  148. sum += ( sum >> 16 );
  149. /* truncate to 16 bits */
  150. answer = ~sum;
  151. return (answer & 0xFFFFFFFF);
  152. }

 

hashtest.c

 

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <sys/types.h>
  4. #include <sys/stat.h>
  5. #include <fcntl.h>
  6. #include <errno.h>
  7. #include <string.h>
  8. #include "hash.h"
  9. #include "md5.h"
  10. struct hash_key {
  11. unsigned char *key;
  12. struct hash_key *next;
  13. };
  14. struct hash_counter_entry {
  15. unsigned int hit_count;
  16. unsigned int entry_count;
  17. struct hash_key *keys;
  18. };
  19. #define BLOCK_LEN 4096
  20. static int backet_len = 10240;
  21. static int hash_call_count = 0;
  22. static struct hash_counter_entry *hlist = NULL;
  23. unsigned int (*hash_func)(char *str);
  24. void choose_hash_func(char *hash_func_name)
  25. {
  26. if (0 == strcmp(hash_func_name, "simple_hash"))
  27. hash_func = simple_hash;
  28. else if (0 == strcmp(hash_func_name, "RS_hash"))
  29. hash_func = RS_hash;
  30. else if (0 == strcmp(hash_func_name, "JS_hash"))
  31. hash_func = JS_hash;
  32. else if (0 == strcmp(hash_func_name, "PJW_hash"))
  33. hash_func = PJW_hash;
  34. else if (0 == strcmp(hash_func_name, "ELF_hash"))
  35. hash_func = ELF_hash;
  36. else if (0 == strcmp(hash_func_name, "BKDR_hash"))
  37. hash_func = BKDR_hash;
  38. else if (0 == strcmp(hash_func_name, "SDBM_hash"))
  39. hash_func = SDBM_hash;
  40. else if (0 == strcmp(hash_func_name, "DJB_hash"))
  41. hash_func = DJB_hash;
  42. else if (0 == strcmp(hash_func_name, "AP_hash"))
  43. hash_func = AP_hash;
  44. else if (0 == strcmp(hash_func_name, "CRC_hash"))
  45. hash_func = CRC_hash;
  46. else
  47. hash_func = NULL;
  48. }
  49. void insert_hash_entry(unsigned char *key, struct hash_counter_entry *hlist)
  50. {
  51. unsigned int hash_value = hash_func(key) % backet_len;
  52. struct hash_key *p;
  53. p = hlist[hash_value].keys;
  54. while(p) {
  55. if (0 == strcmp(key, p->key))
  56. break;
  57. p = p->next;
  58. }
  59. if (p == NULL)
  60. {
  61. p = (struct hash_key *)malloc(sizeof(struct hash_key));
  62. if (p == NULL)
  63. {
  64. perror("malloc in insert_hash_entry");
  65. return;
  66. }
  67. p->key = strdup(key);
  68. p->next = hlist[hash_value].keys;
  69. hlist[hash_value].keys = p;
  70. hlist[hash_value].entry_count++;
  71. }
  72. hlist[hash_value].hit_count++;
  73. }
  74. void hashtest_init()
  75. {
  76. int i;
  77. hash_call_count = 0;
  78. hlist = (struct hash_counter_entry *) malloc (sizeof(struct hash_counter_entry) * backet_len);
  79. if (NULL == hlist)
  80. {
  81. perror("malloc in hashtest_init");
  82. return;
  83. }
  84. for (i = 0; i < backet_len; i++)
  85. {
  86. hlist[i].hit_count = 0;
  87. hlist[i].entry_count = 0;
  88. hlist[i].keys = NULL;
  89. }
  90. }
  91. void hashtest_clean()
  92. {
  93. int i;
  94. struct hash_key *pentry, *p;
  95. if (NULL == hlist)
  96. return;
  97. for (i = 0; i < backet_len; ++i)
  98. {
  99. pentry = hlist[i].keys;
  100. while(pentry)
  101. {
  102. p = pentry->next;
  103. if (pentry->key) free(pentry->key);
  104. free(pentry);
  105. pentry = p;
  106. }
  107. }
  108. free(hlist);
  109. }
  110. void show_hashtest_result()
  111. {
  112. int i, backet = 0, max_link = 0, sum = 0;
  113. int conflict_count = 0, hit_count = 0;
  114. float avg_link, backet_usage;
  115. for(i = 0; i < backet_len; i++)
  116. {
  117. if (hlist[i].hit_count > 0)
  118. {
  119. backet++;
  120. sum += hlist[i].entry_count;
  121. if (hlist[i].entry_count > max_link)
  122. {
  123. max_link = hlist[i].entry_count;
  124. }
  125. if (hlist[i].entry_count > 1)
  126. {
  127. conflict_count++;
  128. }
  129. hit_count += hlist[i].hit_count;
  130. }
  131. }
  132. backet_usage = backet/1.0/backet_len * 100;;
  133. avg_link = sum/1.0/backet;
  134. printf("backet_len = %d/n", backet_len);
  135. printf("hash_call_count = %d/n", hash_call_count);
  136. printf("hit_count = %d/n", hit_count);
  137. printf("conflict count = %d/n", conflict_count);
  138. printf("longest hash entry = %d/n", max_link);
  139. printf("average hash entry length = %.2f/n", avg_link);
  140. printf("backet usage = %.2f%/n", backet_usage);
  141. }
  142. void usage()
  143. {
  144. printf("Usage: hashtest filename hash_func_name [backet_len]/n");
  145. printf("hash_func_name:/n");
  146. printf("/tsimple_hash/n");
  147. printf("/tRS_hash/n");
  148. printf("/tJS_hash/n");
  149. printf("/tPJW_hash/n");
  150. printf("/tELF_hash/n");
  151. printf("/tBKDR_hash/n");
  152. printf("/tSDBM_hash/n");
  153. printf("/tDJB_hash/n");
  154. printf("/tAP_hash/n");
  155. printf("/tCRC_hash/n");
  156. }
  157. void md5_to_32(unsigned char *md5_16, unsigned char *md5_32)
  158. {
  159. int i;
  160. for (i = 0; i < 16; ++i)
  161. {
  162. sprintf(md5_32 + i * 2, "%02x", md5_16[i]);
  163. }
  164. }
  165. int main(int argc, char *argv[])
  166. {
  167. int fd = -1, rwsize = 0;
  168. unsigned char md5_checksum[16 + 1] = {0};
  169. unsigned char buf[BLOCK_LEN] = {0};
  170. if (argc < 3)
  171. {
  172. usage();
  173. return -1;
  174. }
  175. if (-1 == (fd = open(argv[1], O_RDONLY)))
  176. {
  177. perror("open source file");
  178. return errno;
  179. }
  180. if (argc == 4)
  181. {
  182. backet_len = atoi(argv[3]);
  183. }
  184. hashtest_init();
  185. choose_hash_func(argv[2]);
  186. while (rwsize = read(fd, buf, BLOCK_LEN))
  187. {
  188. md5(buf, rwsize, md5_checksum);
  189. insert_hash_entry(md5_checksum, hlist);
  190. hash_call_count++;
  191. memset(buf, 0, BLOCK_LEN);
  192. memset(md5_checksum, 0, 16 + 1);
  193. }
  194. close(fd);
  195. show_hashtest_result();
  196. hashtest_clean();
  197. return 0;
  198. }

原文地址:http://blog.csdn.net/liuben/article/details/5050697

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理