加载中…
个人资料
微博
  • 博客等级：
  • 博客积分：
  • 博客访问：
  • 关注人气：
  • 获赠金笔：0支
  • 赠出金笔：0支
  • 荣誉徽章：
正文 字体大小：大 中 小

不重复Hash编码

(2012-12-07 03:05:38)
标签：

杂谈

 分类： 公司面试

有了上面的暴雪Hash算法。咱们的问题便可解决了。不过，有两点必须先提醒读者：1、Hash表起初要初始化；2、暴雪的Hash算法对于查询那样处理可以，但对插入就不能那么解决。

    关键主体代码如下：

 

  1. //函数prepareCryptTable以下的函数生成一个长度为0x500（合10进制数：1280）的cryptTable[0x500]  
  2. void prepareCryptTable()  
  3. {  
  4.     unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i;  
  5.   
  6.     for( index1 = 0; index1 <0x100; index1++ )  
  7.     {  
  8.         for( index2 = index1, i = 0; i < 5; i++, index2 += 0x100)  
  9.         {  
  10.             unsigned long temp1, temp2;  
  11.             seed = (seed * 125 + 3) % 0x2AAAAB;  
  12.             temp1 = (seed & 0xFFFF)<<0x10;  
  13.             seed = (seed * 125 + 3) % 0x2AAAAB;  
  14.             temp2 = (seed & 0xFFFF);  
  15.             cryptTable[index2] = ( temp1 | temp2 );  
  16.         }  
  17.     }  
  18. }  
  19.   
  20. //函数HashString以下函数计算lpszFileName 字符串的hash值，其中dwHashType 为hash的类型，  
  21. unsigned long HashString(const char *lpszkeyName, unsigned long dwHashType )  
  22. {  
  23.     unsigned char *key  = (unsigned char *)lpszkeyName;  
  24.     unsigned long seed1 = 0x7FED7FED;  
  25.     unsigned long seed2 = 0xEEEEEEEE;  
  26.     int ch;  
  27.   
  28.     while( *key != 0 )  
  29.     {  
  30.         ch = *key++;  
  31.         seed1 = cryptTable[(dwHashType<<8) + ch] ^ (seed1 + seed2);  
  32.         seed2 = ch + seed1 + seed2 + (seed2<<5) + 3;  
  33.     }  
  34.     return seed1;  
  35. }  
  36.   
  37. /////////////////////////////////////////////////////////////////////  
  38. //function: 哈希词典 编码  
  39. //parameter:  
  40. //author: lei.zhou  
  41. //time: 2011-12-14  
  42. /////////////////////////////////////////////////////////////////////  
  43. MPQHASHTABLE TestHashTable[nTableSize];  
  44. int TestHashCTable[nTableSize];  
  45. int TestHashDTable[nTableSize];  
  46. key_list test_data[nTableSize];  
  47.   
  48. //直接调用上面的hashstring，nHashPos就是对应的HASH值。  
  49. int insert_string(const char *string_in)  
  50. {  
  51.     const int HASH_OFFSET = 0, HASH_C = 1, HASH_D = 2;  
  52.     unsigned int nHash = HashString(string_in, HASH_OFFSET);  
  53.     unsigned int nHashC = HashString(string_in, HASH_C);  
  54.     unsigned int nHashD = HashString(string_in, HASH_D);  
  55.     unsigned int nHashStart = nHash % nTableSize;  
  56.     unsigned int nHashPos = nHashStart;  
  57.     int ln, ires = 0;  
  58.   
  59.     while (TestHashTable[nHashPos].bExists)  
  60.     {  
  61. //      if (TestHashCTable[nHashPos]  == (int) nHashC && TestHashDTable[nHashPos] == (int) nHashD)  
  62. //          break;  
  63. //      //...  
  64. //      else  
  65.         //如之前所提示读者的那般，暴雪的Hash算法对于查询那样处理可以，但对插入就不能那么解决  
  66.             nHashPos = (nHashPos + 1) % nTableSize;  
  67.   
  68.         if (nHashPos == nHashStart)  
  69.             break;  
  70.     }  
  71.   
  72.     ln = strlen(string_in);  
  73.     if (!TestHashTable[nHashPos].bExists && (ln < nMaxStrLen))  
  74.     {   
  75.         TestHashCTable[nHashPos] = nHashC;  
  76.         TestHashDTable[nHashPos] = nHashD;  
  77.   
  78.         test_data[nHashPos] = (KEYNODE *) malloc (sizeof(KEYNODE) * 1);  
  79.         if(test_data[nHashPos] == NULL)  
  80.         {  
  81.             printf("10000 EMS ERROR !!!!\n");  
  82.             return 0;  
  83.         }  
  84.   
  85.         test_data[nHashPos]->pkey = (char *)malloc(ln+1);  
  86.         if(test_data[nHashPos]->pkey == NULL)  
  87.         {  
  88.             printf("10000 EMS ERROR !!!!\n");  
  89.             return 0;  
  90.         }  
  91.   
  92.         memset(test_data[nHashPos]->pkey, 0, ln+1);  
  93.         strncpy(test_data[nHashPos]->pkey, string_in, ln);  
  94.         *((test_data[nHashPos]->pkey)+ln) = 0;  
  95.         test_data[nHashPos]->weight = nHashPos;  
  96.   
  97.         TestHashTable[nHashPos].bExists = 1;  
  98.     }  
  99.     else  
  100.     {  
  101.         if(TestHashTable[nHashPos].bExists)  
  102.             printf("30000 in the hash table %s !!!\n", string_in);  
  103.         else  
  104.             printf("90000 strkey error !!!\n");  
  105.     }  
  106.     return nHashPos;  
  107. }  

 

    接下来要读取索引文件big_index对其中的关键词进行编码（为了简单起见，直接一行一行扫描读写，没有跳过行数了）：

 

  1. void bigIndex_hash(const char *docpath, const char *hashpath)  
  2. {  
  3.     FILE *fr, *fw;  
  4.     int len;  
  5.     char *pbuf, *p;  
  6.     char dockey[TERM_MAX_LENG];  
  7.   
  8.     if(docpath == NULL || *docpath == '\0')  
  9.         return;  
  10.   
  11.     if(hashpath == NULL || *hashpath == '\0')  
  12.         return;  
  13.   
  14.     fr = fopen(docpath, "rb");  //读取文件docpath  
  15.     fw = fopen(hashpath, "wb");  
  16.     if(fr == NULL || fw == NULL)  
  17.     {  
  18.         printf("open read or write file error!\n");  
  19.         return;  
  20.     }  
  21.   
  22.     pbuf = (char*)malloc(BUFF_MAX_LENG);  
  23.     if(pbuf == NULL)  
  24.     {  
  25.         fclose(fr);  
  26.         return ;  
  27.     }  
  28.   
  29.     memset(pbuf, 0, BUFF_MAX_LENG);  
  30.   
  31.     while(fgets(pbuf, BUFF_MAX_LENG, fr))  
  32.     {  
  33.         len = GetRealString(pbuf);  
  34.         if(len <= 1)  
  35.             continue;  
  36.         p = strstr(pbuf, "#####");    
  37.         if(p != NULL)  
  38.             continue;  
  39.   
  40.         p = strstr(pbuf, "  ");  
  41.         if (p == NULL)  
  42.         {  
  43.             printf("file contents error!");  
  44.         }  
  45.   
  46.         len = p - pbuf;  
  47.         dockey[0] = 0;  
  48.         strncpy(dockey, pbuf, len);  
  49.   
  50.         dockey[len] = 0;        
  51.   
  52.         int num = insert_string(dockey);   
  53.   
  54.         dockey[len] = ' ';  
  55.         dockey[len+1] = '\0';  
  56.         char str[20];  
  57.         itoa(num, str, 10);  
  58.   
  59.         strcat(dockey, str);  
  60.         dockey[len+strlen(str)+1] = '\0';  
  61.         fprintf (fw, "%s\n", dockey);  
  62.   
  63.     }  
  64.     free(pbuf);  
  65.     fclose(fr);  
  66.     fclose(fw);  
  67. }  

 

    主函数已经很简单了，如下：

 

  1. int main()  
  2. {  
  3.     prepareCryptTable();  //Hash表起初要初始化  
  4.   
  5.     //现在要把整个big_index文件插入hash表，以取得编码结果  
  6.     bigIndex_hash("big_index.txt", "hashpath.txt");  
  7.     system("pause");  
  8.   
  9.     return 0;  
  10. }  

 

 

    程序运行后生成的hashpath.txt文件如下：

http://hi.csdn.net/attachment/201112/20/0_1324361461I3c3.gif

    如上所示，采取暴雪的Hash算法并在插入的时候做适当处理，当再次对上文中的索引文件big_index进行Hash编码后，冲突问题已经得到初步解决。当然，还有待更进一步更深入的测试。

后续添上数目索引1~10000...

    后来又为上述文件中的关键词编了码一个计数的内码，不过，奇怪的是，同样的代码，在Dev C++ 与VS2010上运行结果却不同（左边dev上计数从"1"开始，VS上计数从“1994014002”开始），如下图所示：

http://hi.csdn.net/attachment/201112/22/0_1324551921UHKU.gif

    在上面的bigIndex_hashcode函数的基础上，修改如下，即可得到上面的效果：

 

  1. void bigIndex_hashcode(const char *in_file_path, const char *out_file_path)  
  2. {  
  3.     FILE *fr, *fw;  
  4.     int len, value;  
  5.     char *pbuf, *pleft, *p;  
  6.     char keyvalue[TERM_MAX_LENG], str[WORD_MAX_LENG];  
  7.   
  8.     if(in_file_path == NULL || *in_file_path == '\0') {  
  9.         printf("input file path error!\n");  
  10.         return;  
  11.     }  
  12.   
  13.     if(out_file_path == NULL || *out_file_path == '\0') {  
  14.         printf("output file path error!\n");  
  15.         return;  
  16.     }  
  17.   
  18.     fr = fopen(in_file_path, "r");  //读取in_file_path路径文件  
  19.     fw = fopen(out_file_path, "w");  
  20.   
  21.     if(fr == NULL || fw == NULL)  
  22.     {  
  23.         printf("open read or write file error!\n");  
  24.         return;  
  25.     }  
  26.   
  27.     pbuf = (char*)malloc(BUFF_MAX_LENG);  
  28.     pleft = (char*)malloc(BUFF_MAX_LENG);  
  29.     if(pbuf == NULL || pleft == NULL)  
  30.     {  
  31.         printf("allocate memory error!");  
  32.         fclose(fr);  
  33.         return ;  
  34.     }  
  35.   
  36.     memset(pbuf, 0, BUFF_MAX_LENG);  
  37.   
  38.     int offset = 1;  
  39.     while(fgets(pbuf, BUFF_MAX_LENG, fr))  
  40.     {  
  41.         if (--offset > 0)  
  42.             continue;  
  43.   
  44.         if(GetRealString(pbuf) <= 1)  
  45.             continue;  
  46.   
  47.         p = strstr(pbuf, "#####");    
  48.         if(p != NULL)  
  49.             continue;  
  50.   
  51.         p = strstr(pbuf, "  ");  
  52.         if (p == NULL)  
  53.         {  
  54.             printf("file contents error!");  
  55.         }  
  56.   
  57.         len = p - pbuf;  
  58.   
  59.         // 确定跳过行数  
  60.         strcpy(pleft, p+1);   
  61.         offset = atoi(pleft) + 1;  
  62.   
  63.         strncpy(keyvalue, pbuf, len);    
  64.         keyvalue[len] = '\0';  
  65.         value = insert_string(keyvalue);  
  66.   
  67.         if (value != -1) {  
  68.   
  69.             // key value中插入空格  
  70.             keyvalue[len] = ' ';  
  71.             keyvalue[len+1] = '\0';  
  72.   
  73.             itoa(value, str, 10);  
  74.             strcat(keyvalue, str);  
  75.   
  76.             keyvalue[len+strlen(str)+1] = ' ';  
  77.             keyvalue[len+strlen(str)+2] = '\0';  
  78.   
  79.             keysize++;  
  80.             itoa(keysize, str, 10);  
  81.             strcat(keyvalue, str);  
  82.   
  83.             // 将key value写入文件  
  84.             fprintf (fw, "%s\n", keyvalue);  
  85.   
  86.         }  
  87.     }  
  88.     free(pbuf);  
  89.     fclose(fr);  
  90.     fclose(fw);  
  91. }  

 

小结

    本文有一点值得一提的是，在此前的这篇文章（十一、从头到尾彻底解析Hash表算法）之中，只是对Hash表及暴雪的Hash算法有过学习和了解，但尚未真正运用过它，而今在本章中体现，证明还是之前写的文章，及之前对Hash表等算法的学习还是有一定作用的。同时，也顺便对暴雪的Hash函数算是做了个测试，其的确能解决一般的冲突性问题，创造这个算法的人不简单呐。

喜欢

0

阅读┊ 收藏 ┊ 喜欢▼ ┊打印┊举报/Report
  

新浪BLOG意见反馈留言板　欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

Copyright © 1996 - 2022 SINA Corporation, All Rights Reserved

新浪公司 版权所有