青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

Shuffy

不斷的學習，不斷的思考，才能不斷的進步.Let's do better together!
posts - 102, comments - 43, trackbacks - 0, articles - 19

字符串Hash函數評估

Posted on 2011-11-04 14:21 Shuffy 閱讀(671) 評論(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
  4. #ifdef __cplusplus
  5. extern "C" {
  6. #endif
  8. /* A Simple Hash Function */
  9. unsigned int simple_hash(char *str);
  11. /* RS Hash Function */
  12. unsigned int RS_hash(char *str);
  14. /* JS Hash Function */
  15. unsigned int JS_hash(char *str);
  17. /* P. J. Weinberger Hash Function */
  18. unsigned int PJW_hash(char *str);
  20. /* ELF Hash Function */
  21. unsigned int ELF_hash(char *str);
  23. /* BKDR Hash Function */
  24. unsigned int BKDR_hash(char *str);
  26. /* SDBM Hash Function */
  27. unsigned int SDBM_hash(char *str);
  29. /* DJB Hash Function */
  30. unsigned int DJB_hash(char *str);
  32. /* AP Hash Function */
  33. unsigned int AP_hash(char *str);
  35. /* CRC Hash Function */
  36. unsigned int CRC_hash(char *str);
  38. #ifdef __cplusplus
  39. }
  40. #endif
  42. #endif

hash.c

 

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

 

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

原文地址：http://blog.csdn.net/liuben/article/details/5050697
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

    • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            
欧美日韩高清在线|
午夜欧美电影在线观看|
欧美日韩亚洲免费|
欧美精品啪啪|
欧美日韩国产123|
欧美日韩日本视频|
国产精品av久久久久久麻豆网|
欧美午夜精品久久久久久久|
国产精品成人一区二区艾草|
国产精品久久久久久久久久免费|
狠狠88综合久久久久综合网|
国产亚洲成av人在线观看导航|
狠狠色狠狠色综合日日五|
亚洲精品黄色|
亚洲视频狠狠|
海角社区69精品视频|
亚洲第一久久影院|
99re在线精品|
欧美一级久久|
亚洲国产精品尤物yw在线观看|
亚洲国产精品一区二区久|
亚洲一区在线免费观看|
久久久久久电影|
亚洲日韩欧美视频|
亚洲性图久久|
久久综合一区二区|
国产精品久久久久久五月尺|
狠狠干成人综合网|
国产精品99久久久久久久久久久久|
欧美一区二区三区视频免费播放
|
在线看一区二区|
猛干欧美女孩|
亚洲精品国产精品国自产观看浪潮|
在线亚洲高清视频|
性欧美xxxx视频在线观看|
欧美成熟视频|
在线亚洲+欧美+日本专区|
男同欧美伦乱|
狠狠色2019综合网|
亚洲欧美一区二区三区在线|
亚洲国产精品嫩草影院|
午夜亚洲一区|
国产精品午夜在线|
一本大道久久精品懂色aⅴ|
国产色产综合产在线视频|
日韩一级视频免费观看在线|
久久蜜桃精品|
亚洲综合不卡|
欧美日韩久久久久久|
亚洲二区视频在线|
亚洲欧洲一区二区三区|
久久成人精品|
亚洲在线日韩|
国产精品久久久久久久久婷婷
|
在线视频一区二区|
亚洲国产欧美一区二区三区同亚洲
|
可以免费看不卡的av网站|
欧美一区二区三区久久精品|
亚洲人成在线观看网站高清|
久久男女视频|
在线观看91精品国产麻豆|
久久精品视频在线|
欧美伊人久久大香线蕉综合69|
国产精品免费看|
亚洲永久网站|
亚洲在线第一页|
国内精品久久国产|
欧美成人精品h版在线观看|
久久久久免费观看|
亚洲精品乱码|
亚洲天堂免费观看|
国产婷婷色一区二区三区在线|
久久精品国产免费观看|
久久久噜噜噜久噜久久
|
亚洲欧美日韩爽爽影院|
国产精品区一区二区三|
久久成人免费日本黄色|
欧美一区亚洲|
亚洲第一在线视频|
亚洲电影视频在线|
亚洲精品影视在线观看|
欧美母乳在线|
国产精品一区二区你懂得|
国产精品国码视频|
久久精品国产免费|
久久久中精品2020中文|
最近中文字幕日韩精品|
99精品欧美一区|
国产日韩专区在线|
蜜桃精品久久久久久久免费影院|
欧美高清在线一区|
欧美在线观看视频在线|
欧美精品91|
欧美一区二区三区视频免费播放|
久久精品盗摄|
亚洲少妇自拍|
欧美在线观看一区二区|
亚洲精品美女在线|
午夜一区二区三视频在线观看|
亚洲电影免费观看高清完整版在线|
亚洲人体一区|
国产亚洲制服色|
99视频+国产日韩欧美|
在线不卡欧美|
亚洲一区二区精品视频|
亚洲黄色小视频|
久久本道综合色狠狠五月|
夜夜精品视频|
噜噜噜在线观看免费视频日韩|
亚洲欧美激情精品一区二区|
久久亚洲综合色|
久久福利毛片|
国产精品久久久久久久一区探花
|
亚洲永久精品大片|
欧美成人精品一区二区三区|
久久免费视频网站|
欧美日韩国产一区二区三区地区|
久久欧美中文字幕|
国产毛片精品视频|
亚洲精品自在在线观看|
亚洲国产毛片完整版
|
久久久91精品国产一区二区三区|
亚洲在线一区二区|
欧美黄色大片网站|
免费久久精品视频|
国产伦一区二区三区色一情|
99视频在线观看一区三区|
亚洲毛片av在线|
欧美韩日高清|
亚洲人成在线观看一区二区|
亚洲人成亚洲人成在线观看|
欧美综合激情网|
亚洲欧美综合一区|
欧美日韩午夜视频在线观看|
亚洲精选91|
在线亚洲一区观看|
欧美激情黄色片|
亚洲欧洲一区二区在线播放|
亚洲黄一区二区三区|
久久综合色综合88|
久久亚洲精品中文字幕冲田杏梨
|
欧美超级免费视 在线|
久久综合久久综合这里只有精品|
国产亚洲精品资源在线26u|
亚洲欧美日韩精品久久|
久久国产精品一区二区|
激情成人中文字幕|
久久久久高清|
欧美国产一区二区在线观看|
1000部精品久久久久久久久|
久久久久久999|
亚洲黄色尤物视频|
亚洲四色影视在线观看|
国产精品成人观看视频免费
|
亚洲精品久久视频|
亚洲一区免费网站|
国产精品视频不卡|
欧美一区二区久久久|
麻豆精品视频在线观看|
亚洲国产欧美一区|
欧美日韩小视频|
亚洲欧洲av一区二区|
久久久久久久综合日本|
亚洲国产日韩欧美在线99|
欧美 日韩 国产一区二区在线视频
|
国产日本亚洲高清|
久久精品视频在线|
亚洲激情av|
欧美一区二区三区在线看|
国产一区二区三区在线观看网站
|
久久国产一区|
亚洲片在线观看|
久久国产欧美|
亚洲裸体俱乐部裸体舞表演av|
国产精品视区|
欧美a一区二区|
欧美一级艳片视频免费观看|
91久久综合|
久久久精品一区|
亚洲精品视频免费观看|
国产精品午夜在线观看|
欧美福利一区二区|
欧美一区91|
日韩视频在线一区|
欧美不卡高清|
久久xxxx|
亚洲综合99|
亚洲国产综合在线|
国产婷婷色一区二区三区在线
|
av不卡免费看|
狠狠色伊人亚洲综合成人|
欧美日韩国内|
欧美va天堂|
久久青青草综合|
亚洲综合激情|
aa级大片欧美三级|
亚洲青色在线|
亚洲国产毛片完整版
|
亚洲午夜电影在线观看|
欧美国产免费|