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

下載本文檔

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

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

2、60;       HashAlgo.h  3. / Purpose:     使用魔獸Hash算法，實現(xiàn)索引表的填充和查找功能。  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. / 測試宏定義，正式使用時關(guān)閉  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 )/ 創(chuàng)建指定大小的哈希索引表，不帶參數(shù)的構(gòu)造函數(shù)創(chuàng)建默認大小的哈希索引表  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、;  / 對哈希索引表預(yù)處理  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. ;   二、類實現(xiàn)文件 cpp:nogutter view plaincopyprint?1. /  2. / Name:        HashAlgo.cpp  3. / Purpose:     使

22、用魔獸Hash算法，實現(xiàn)索引表的填充和查找功能。  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. / 預(yù)處理  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. / 通過傳入字符串，將相應(yīng)的表項散列到索引表相應(yīng)位置中去  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. / 設(shè)置哈希索引表長  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. / 測試參數(shù)設(shè)定宏  14. #define TESTNUM 32  15.   16. #include <iostream>  17. #include <

54、;fstream>  18. #include "HashAlgo.h"  19.   20. using namespace std;  21.   22. /  23. / 測試主函數(shù)開始  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 << "散列結(jié)果一：成

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

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

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

60、;   cout << "散列結(jié)果二：失敗！" << 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. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論