• <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>
            

    
            

            




            







												


        


            
	
            
		
			

            

            
	
            
		
			
            Shuffy
            
			
不斷的學(xué)習(xí)，不斷的思考，才能不斷的進(jìn)步.Let's do better together!
		            		
	
            

            

            

            

            posts - 102, comments - 43, trackbacks - 0, articles - 19
            


            		
	
            
	
            
		
			
		
		
			
            
				
					
	
            
		
		
            Hash查找因?yàn)槠銸(1)的查找性能而著稱，被對(duì)查找性能要求高的應(yīng)用所廣泛采用。它的基本思想是：
            (1) 創(chuàng)建一個(gè)定長(zhǎng)的線性Hash表，一般可以初始化時(shí)指定length;
            

            (2) 設(shè)計(jì)Hash函數(shù)，將關(guān)鍵字key散射到Hash表中。其中hash函數(shù)設(shè)計(jì)是最為關(guān)鍵的，均勻分布、沖突概率小全在它；
            

            (3) 通常采用拉鏈方法來解決hash沖突問題，即散射到同一個(gè)hash表項(xiàng)的關(guān)鍵字，以鏈表形式來表示(也稱為桶backet);
            

            (4) 給定關(guān)鍵字key，就可以在O(1) + O(m)的時(shí)間復(fù)雜度內(nèi)定位到目標(biāo)。其中，m為拉鏈長(zhǎng)度，即桶深。
            

             
            

            Hash應(yīng)用中，字符串是最為常見的關(guān)鍵字，應(yīng)用非常普通，現(xiàn)在的程序設(shè)計(jì)語(yǔ)言中基本上都提供了字符串hash表的支持。字符串hash函數(shù)非常多，常見的主要有Simple_hash, RS_hash, JS_hash, PJW_hash, ELF_hash, BKDR_hash, SDBM_hash, DJB_hash, AP_hash, CRC_hash等。它們的C語(yǔ)言實(shí)現(xiàn)見后面附錄代碼: hash.h, hash.c。那么這么些字符串hash函數(shù)，誰(shuí)好熟非呢？評(píng)估hash函數(shù)優(yōu)劣的基準(zhǔn)主要有以下兩個(gè)指標(biāo)：
            

            (1) 散列分布性
            

            即桶的使用率backet_usage = (已使用桶數(shù)) / (總的桶數(shù))，這個(gè)比例越高，說明分布性良好，是好的hash設(shè)計(jì)。
            

            (2) 平均桶長(zhǎng)
            

            即avg_backet_len，所有已使用桶的平均長(zhǎng)度。理想狀態(tài)下這個(gè)值應(yīng)該=1，越小說明沖突發(fā)生地越少，是好的hash設(shè)計(jì)。
            

            hash函數(shù)計(jì)算一般都非常簡(jiǎn)潔，因此在耗費(fèi)計(jì)算時(shí)間復(fù)雜性方面判別甚微，這里不作對(duì)比。
            

             
            

            評(píng)估方案設(shè)計(jì)是這樣的：
            

            (1) 以200M的視頻文件作為輸入源，以4KB的塊為大小計(jì)算MD5值，并以此作為hash關(guān)鍵字;
            

            (2) 分別應(yīng)用上面提到的各種字符串hash函數(shù)，進(jìn)行hash散列模擬；
            

            (3) 統(tǒng)計(jì)結(jié)果，用散列分布性和平均桶長(zhǎng)兩個(gè)指標(biāo)進(jìn)行評(píng)估分析。
            

             
            

            測(cè)試程序見附錄代碼hashtest.c，測(cè)試結(jié)果如下表所示。從這個(gè)結(jié)果我們也可以看出，這些字符串hash函數(shù)真是不相仲伯，難以決出高低，所以實(shí)際應(yīng)用中可以根據(jù)喜好選擇。當(dāng)然，最好實(shí)際測(cè)試一下，畢竟應(yīng)用特點(diǎn)不大相同。其他幾組測(cè)試結(jié)果也類似，這里不再給出。
            

             
            

            









            
Hash函數(shù)
桶數(shù)
Hash調(diào)用總數(shù)
最大桶長(zhǎng)
平均桶長(zhǎng)
桶使用率%
            

            
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
            
	
            


            
	    
    




            



            


            

	
            
		
		
            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            
		
            
		
				
		
		
		
            
		
            			
		
		
		
		
            
		
            
			
		
            
		
            
			
		
            
		
            
			
            網(wǎng)站導(dǎo)航:
			博客園  
			IT新聞  
			BlogJava  			
			博問  
			Chat2DB  
			管理
			
            		
		
            
		
            
			
				

            


            

            		
		
            
	
            	

            



            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



久久久精品一区二区三区|
亚洲狠狠婷婷综合久久久久|
美女写真久久影院|
久久精品亚洲男人的天堂|
久久99精品国产麻豆不卡|
久久亚洲国产精品五月天婷|
色播久久人人爽人人爽人人片AV|
久久精品无码一区二区WWW|
久久久久无码精品国产不卡|
久久精品国产福利国产秒|
精品无码人妻久久久久久|
久久久久高潮综合影院|
亚洲精品高清久久|
亚洲国产精品无码久久久不卡|
欧美一区二区精品久久|
精品国产乱码久久久久软件|
 久久综合九色综合久99|
久久久久亚洲AV成人网人人网站|
亚洲乱亚洲乱淫久久|
亚洲va中文字幕无码久久|
久久精品国产亚洲一区二区三区|
久久精品国产亚洲AV忘忧草18|
超级碰久久免费公开视频|
色欲久久久天天天综合网精品|
欧美久久亚洲精品|
久久精品?ⅴ无码中文字幕|
国内精品久久久人妻中文字幕|
老男人久久青草av高清|
久久天天日天天操综合伊人av|
久久99热国产这有精品|
国产精品久久午夜夜伦鲁鲁|
精品久久久久久国产|
九九精品久久久久久噜噜|
久久久久久极精品久久久
|
久久精品无码一区二区app|
乱亲女H秽乱长久久久|
7777精品伊人久久久大香线蕉|
精品久久综合1区2区3区激情|
国产 亚洲 欧美 另类 久久|
久久se精品一区精品二区|
久久福利青草精品资源站免费|