暴雪hash算法封裝及測試源碼jluzc_第1頁
暴雪hash算法封裝及測試源碼jluzc_第2頁
暴雪hash算法封裝及測試源碼jluzc_第3頁
暴雪hash算法封裝及測試源碼jluzc_第4頁
暴雪hash算法封裝及測試源碼jluzc_第5頁
已閱讀5頁，還剩3頁未讀， 繼續免費閱讀

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、魔獸哈希算法封裝和測試      近期由于需要，研究了魔獸文件打包管理器的相關算法，重點對其文件索引表的生成和查找進行了研究：采用哈希表進行，在沖突方面的處理方面，采用線性探測再散列。在添加和查找過程中進行了三次哈希，第一個哈希值用來查找，后兩個哈希值用來校驗，這樣可以大大減少沖突的幾率。      這里對其進行了簡單的封裝，擴展時，僅僅需要對結構體進行擴展即可。更為詳細的說明，參考代碼：  一、類聲明頭文件1. /  2. / Name:

2、60;       HashAlgo.h  3. / Purpose:     使用魔獸Hash算法，實現索引表的填充和查找功能。  4. / Author:      jluzc  5. / Modified by:  6. / Created:   

3、60; 07/30/09  7. / RCS-ID:      $Id: treetest.h 43021 2012-07-30 16:36:51Z VZ $  8. / Copyright:   (C) Copyright 2009, TSong Corporation, All Rights Reserv

4、ed.  9. / Licence:       10. /  11.   12. #define MAXFILENAME 255     / 最大文件名長度  13. #define MAXTABLELEN 1024    / 默認哈希索引表大小  14.  

5、; 15. /  16. / 測試宏定義，正式使用時關閉  17. #define DEBUGTEST 1  18.   19. /  20. / 哈希索引表定義  21. typedef struct  22.   23.     long nHashA;  24.    &#

6、160;long nHashB;  25.     bool bExists;  26.     char test_filenameMAXFILENAME;  27.     / .  28.  MPQHASHTABLE;  29.   30. /  31. / 對哈希索引表的

7、算法進行封裝  32. class CHashAlgo  33.   34. public:  35.   36. #if DEBUGTEST  37.     long  testid;   / 測試之用  38. #endif  39.   40.     

8、;CHashAlgo( const long nTableLength = MAXTABLELEN )/ 創建指定大小的哈希索引表，不帶參數的構造函數創建默認大小的哈希索引表  41.       42.         prepareCryptTable();  43.       &#

9、160; m_tablelength = nTableLength;  44.           45.         m_HashIndexTable = new MPQHASHTABLEnTableLength;  46.        &#

10、160;for ( int i = 0; i < nTableLength; i+ )  47.           48.             m_HashIndexTablei.nHashA = -1;  

11、49.             m_HashIndexTablei.nHashB = -1;  50.             m_HashIndexTablei.bExists = false;  51.       

12、      m_HashIndexTablei.test_filename0 = '/0'  52.                   53.       54.   55.     

13、;void prepareCryptTable();                                             

14、;  / 對哈希索引表預處理  56.   57.     unsigned long HashString(char *lpszFileName, unsigned long dwHashType); / 求取哈希值      58.     long GetHashTablePos( 

15、char *lpszString );                               / 得到在定長表中的位置  59.     bool SetHashTable( 

16、;char *lpszString );                                  / 將字符串散列到哈希表中  60.   61.   

17、0; unsigned long GetTableLength(void);  62.     void SetTableLength( const unsigned long nLength );  63.   64.     CHashAlgo()  65.       66. 

18、60;       if ( NULL != m_HashIndexTable )  67.           68.             delete m_HashIndexTable;  69. &#

19、160;           m_HashIndexTable = NULL;  70.             m_tablelength = 0;  71.           72.

20、      73. protected:  74.   75. private:  76.     unsigned long cryptTable0x500;  77.     unsigned long m_tablelength;    / 哈希索引表長度  78

21、.     MPQHASHTABLE *m_HashIndexTable;  79. ;   二、類實現文件 cpp:nogutter view plaincopyprint?1. /  2. / Name:        HashAlgo.cpp  3. / Purpose:     使

22、用魔獸Hash算法，實現索引表的填充和查找功能。  4. / Author:      陳相禮  5. / Modified by:  6. / Created:     07/30/09  7. / RCS-ID:      $Id: treetest.h 43021 

23、;2009-07-30 16:36:51Z VZ $  8. / Copyright:   (C) Copyright 2009, TSong Corporation, All Rights Reserved.  9. / Licence:       10. /  11.   12. #inclu

24、de "windows.h"  13. #include "HashAlgo.h"  14.   15. /  16. / 預處理  17. void CHashAlgo:prepareCryptTable()  18.    19.     unsigned long seed = 0x

25、00100001, index1 = 0, index2 = 0, i;  20.   21.     for( index1 = 0; index1 < 0x100; index1+ )  22.        23.     &#

26、160;   for( index2 = index1, i = 0; i < 5; i+, index2 += 0x100 )  24.            25.           &#

27、160; unsigned long temp1, temp2;  26.             seed = (seed * 125 + 3) % 0x2AAAAB;  27.            

28、60;temp1 = (seed & 0xFFFF) << 0x10;  28.             seed = (seed * 125 + 3) % 0x2AAAAB;  29.        

29、0;    temp2 = (seed & 0xFFFF);  30.             cryptTableindex2 = ( temp1 | temp2 );   31.         &

30、#160;  32.        33.   34.   35. /  36. / 求取哈希值  37. unsigned long CHashAlgo:HashString(char *lpszFileName, unsigned long dwHashType)  38.    39.  &#

31、160;  unsigned char *key = (unsigned char *)lpszFileName;  40.     unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;  41.     int ch;  42.  &

32、#160;43.     while(*key != 0)  44.        45.         ch = toupper(*key+);  46.   47.         seed1 = cry

33、ptTable(dwHashType << 8) + ch  (seed1 + seed2);  48.         seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;   49.  

34、60;    50.     return seed1;   51.   52.   53. /  54. / 得到在定長表中的位置  55. long CHashAlgo:GetHashTablePos(char *lpszString)  56.   57.    58.   

35、;  const unsigned long HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;  59.     unsigned long nHash = HashString(lpszString, HASH_OFFSET);  60.     unsigned&

36、#160;long nHashA = HashString(lpszString, HASH_A);  61.     unsigned long nHashB = HashString(lpszString, HASH_B);  62.     unsigned long nHashStart = nHash % m_tabl

37、elength,  63.         nHashPos = nHashStart;  64.   65.     while ( m_HashIndexTablenHashPos.bExists)  66.        67.     

38、60;   if (m_HashIndexTablenHashPos.nHashA = nHashA && m_HashIndexTablenHashPos.nHashB = nHashB)   68.             return nHashPos;   69.  

39、0;      else   70.             nHashPos = (nHashPos + 1) % m_tablelength;  71.   72.         if (nHa

40、shPos = nHashStart)   73.             break;   74.       75.   76.     return -1; /沒有找到  77.   78. / 

41、0;79. / 通過傳入字符串，將相應的表項散列到索引表相應位置中去  80. bool CHashAlgo:SetHashTable( char *lpszString )  81.   82.     const unsigned long HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2; &

42、#160;83.     unsigned long nHash = HashString(lpszString, HASH_OFFSET);  84.     unsigned long nHashA = HashString(lpszString, HASH_A);  85.     unsigned long n

43、HashB = HashString(lpszString, HASH_B);  86.     unsigned long nHashStart = nHash % m_tablelength,  87.         nHashPos = nHashStart;  88.   89.

44、     while ( m_HashIndexTablenHashPos.bExists)  90.        91.         nHashPos = (nHashPos + 1) % m_tablelength;  92.     &#

45、160;   if (nHashPos = nHashStart)   93.           94.   95. #if DEBUGTEST  96.             testid = -1; &

46、#160;97. #endif  98.   99.             return false;   100.           101.       102.     m_HashInde

47、xTablenHashPos.bExists = true;  103.     m_HashIndexTablenHashPos.nHashA = nHashA;  104.     m_HashIndexTablenHashPos.nHashB = nHashB;  105.     strcpy( m_HashIndexTablenHashP

48、os.test_filename, lpszString );  106.   107. #if DEBUGTEST  108.     testid = nHashPos;  109. #endif  110.   111.     return true;  112.   113.  

49、 114. /  115. / 取得哈希索引表長  116. unsigned long CHashAlgo:GetTableLength(void)  117.   118.     return m_tablelength;  119.   120.   121. /  122. / 設置哈希索引表長  123.

50、void CHashAlgo:SetTableLength( const unsigned long nLength )  124.   125.     m_tablelength = nLength;  126.     return;  127.    三、測試主文件 1. /  2. /&#

51、160;Name:        DebugMain.cpp  3. / Purpose:     測試Hash算法封裝的類，完成索引表的填充和查找功能的測試。  4. / Author:      陳相禮  5. / Modified by:  6. / Created:

52、60;    07/30/09  7. / RCS-ID:      $Id: treetest.h 43021 2009-07-30 16:36:51Z VZ $  8. / Copyright:   (C) Copyright 2009, TSong Corporation, All 

53、Rights Reserved.  9. / Licence:       10. /  11.   12. /  13. / 測試參數設定宏  14. #define TESTNUM 32  15.   16. #include <iostream>  17. #include <

54、;fstream>  18. #include "HashAlgo.h"  19.   20. using namespace std;  21.   22. /  23. / 測試主函數開始  24. int main( int argc, char *argv )  25.   26. &

55、#160;   CHashAlgo hash_test( TESTNUM );  27.   28.     cout << "取得初始化散列索引表長為：" << hash_test.GetTableLength() << endl;  29.   30.     

56、;bool is_success = hash_test.SetHashTable( "test" );  31.     if ( is_success )  32.       33.         cout << "散列結果一：成

57、功！" << endl;  34.       35.     else  36.       37.         cout << "散列結果一：失敗！" << endl; 

58、60;38.       39.       40.     is_success = hash_test.SetHashTable( "測試" );  41.     if ( is_success )  42.     

59、60; 43.         cout << "散列結果二：成功！" << endl;  44.       45.     else  46.       47.      

60、;   cout << "散列結果二：失敗！" << endl;  48.       49.   50.     long pos = hash_test.GetHashTablePos( "test" );  51.    

61、; cout << "查找測試字符串：/"test/" 的散列位置：" << pos << endl;  52.     pos = hash_test.GetHashTablePos( "測試" );  53.     cout << "查找測試字符串：“測試” 的散列位置：" << pos << endl;  54.   55.     /  56.     / 散列測試  57.     for ( int&#

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論