crazy-coody
	 
	
		
          
		
          
			
			
			
		
          
		
          	
	          		

          

          
	

          

          


	
          
	
          
		
				
				
          日歷
          
			
          
			
          
				
          
	
          
		
          <2025年7月>
          
	
          日一二三四五六
          293012345
          6789101112
          13141516171819
          20212223242526
          272829303112
          3456789
          

          		
			
          
			
          
				
				

          統計
          
	
            
		
          • 隨筆 - 2
		
          • 文章 - 4
		
          • 評論 - 0
		
          • 引用 - 0
	
            • 

          
				

          導航
          

				

          常用鏈接
          


          留言簿
          


		
          隨筆分類
          
		
				
			
	
		
          隨筆檔案
          
		
				
			
	
		
          文章檔案
          
		
				
			
	




          搜索
          

            
	
          • 
		
          •  
	
            • 

          


          最新評論
	
          

          
	

          


          閱讀排行榜
          



          評論排行榜
          


				
				
           
          
		          		
		
				
					

          
	
	
           原文如下：（原文地址：http://blog.csdn.net/eaglewood2005/archive/2009/07/30/4394583.aspx ） 
          

           
          



          
     近期由于需要，研究了魔獸文件打包管理器的相關算法，重點對其文件索引表的生成和查找進行了研究：采用哈希表進行，在沖突方面的處理方面，采用線性探測再散列。在添加和查找過程中進行了三次哈希，第一個哈希值用來查找，后兩個哈希值用來校驗，這樣可以大大減少沖突的幾率。 
          

                這里對其進行了簡單的封裝，擴展時，僅僅需要對結構體進行擴展即可。更為詳細的說明，參考代碼：【轉載請保留版權，謝謝】
          

          一、類聲明頭文件
          

          /////////////////////////////////////////////////////////////////////////////    
          
// Name:        HashAlgo.h    
          
// Purpose:     使用魔獸Hash算法，實現索引表的填充和查找功能。    
          
// Author:      陳相禮    
          
// Modified by:    
          
// Created:     07/30/09    
          
// RCS-ID:      $Id: treetest.h 43021 2009-07-30 16:36:51Z VZ $    
          
// Copyright:   (C) Copyright 2009, TSong Corporation, All Rights Reserved.    
          
// Licence:         
          
/////////////////////////////////////////////////////////////////////////////    
          
   
          
#define MAXFILENAME 255     // 最大文件名長度    
          
#define MAXTABLELEN 1024    // 默認哈希索引表大小    
          
   
          
//////////////////////////////////////////////////////////////////////////    
          
// 測試宏定義，正式使用時關閉    
          
#define DEBUGTEST 1    
          
   
          
//////////////////////////////////////////////////////////////////////////    
          
// 哈希索引表定義    
          
typedef   struct    
          
{   
          
    long  nHashA;   
          
    long  nHashB;   
          
    bool  bExists;   
          
    char  test_filename[MAXFILENAME];   
          
    // ......    
          
} MPQHASHTABLE;   
          
   
          
//////////////////////////////////////////////////////////////////////////    
          
// 對哈希索引表的算法進行封裝    
          
class  CHashAlgo   
          
{   
          
public :   
          
   
          
#if DEBUGTEST    
          
    long   testid;    // 測試之用    
          
#endif    
          
   
          
    CHashAlgo( const   long  nTableLength = MAXTABLELEN ) // 創建指定大小的哈希索引表，不帶參數的構造函數創建默認大小的哈希索引表    
          
    {   
          
        prepareCryptTable();   
          
        m_tablelength = nTableLength;   
          
           
          
        m_HashIndexTable = new  MPQHASHTABLE[nTableLength];   
          
        for  (  int  i = 0; i < nTableLength; i++ )   
          
        {   
          
            m_HashIndexTable[i].nHashA = -1;   
          
            m_HashIndexTable[i].nHashB = -1;   
          
            m_HashIndexTable[i].bExists = false ;   
          
            m_HashIndexTable[i].test_filename[0] = '\0' ;   
          
        }           
          
    }   
          
   
          
    void  prepareCryptTable();                                                // 對哈希索引表預處理    
          
   
          
    unsigned long  HashString( char  *lpszFileName, unsigned  long  dwHashType);  // 求取哈希值        
          
    long  GetHashTablePos(  char  *lpszString );                                // 得到在定長表中的位置    
          
    bool  SetHashTable(  char  *lpszString );                                   // 將字符串散列到哈希表中    
          
   
          
    unsigned long  GetTableLength( void );   
          
    void  SetTableLength(  const  unsigned  long  nLength );   
          
   
          
    ~CHashAlgo()   
          
    {   
          
        if  ( NULL != m_HashIndexTable )   
          
        {   
          
            delete  []m_HashIndexTable;   
          
            m_HashIndexTable = NULL;   
          
            m_tablelength = 0;   
          
        }   
          
    }   
          
protected :   
          
   
          
private :   
          
    unsigned long  cryptTable[0x500];   
          
    unsigned long  m_tablelength;     // 哈希索引表長度    
          
    MPQHASHTABLE *m_HashIndexTable;   
          
};   
          

          view plaincopy to clipboardprint?
          
/////////////////////////////////////////////////////////////////////////////   
          
// Name:        HashAlgo.h   
          
// Purpose:     使用魔獸Hash算法，實現索引表的填充和查找功能。   
          
// Author:      陳相禮   
          
// Modified by:   
          
// Created:     07/30/09   
          
// RCS-ID:      $Id: treetest.h 43021 2009-07-30 16:36:51Z VZ $   
          
// Copyright:   (C) Copyright 2009, TSong Corporation, All Rights Reserved.   
          
// Licence:        
          
/////////////////////////////////////////////////////////////////////////////   
          
#define MAXFILENAME 255     // 最大文件名長度   
          
#define MAXTABLELEN 1024    // 默認哈希索引表大小   
          
//////////////////////////////////////////////////////////////////////////   
          
// 測試宏定義，正式使用時關閉   
          
#define DEBUGTEST 1   
          
//////////////////////////////////////////////////////////////////////////   
          
// 哈希索引表定義   
          
typedef struct  
          
{   
          
    long nHashA;   
          
    long nHashB;   
          
    bool bExists;   
          
    char test_filename[MAXFILENAME];   
          
    // ......   
          
} MPQHASHTABLE;   
          
//////////////////////////////////////////////////////////////////////////   
          
// 對哈希索引表的算法進行封裝   
          
class CHashAlgo   
          
{   
          
public:   
          
#if DEBUGTEST   
          
    long  testid;   // 測試之用   
          
#endif   
          
    CHashAlgo( const long nTableLength = MAXTABLELEN )// 創建指定大小的哈希索引表，不帶參數的構造函數創建默認大小的哈希索引表   
          
    {   
          
        prepareCryptTable();   
          
        m_tablelength = nTableLength;   
          
           
          
        m_HashIndexTable = new MPQHASHTABLE[nTableLength];   
          
        for ( int i = 0; i < nTableLength; i++ )   
          
        {   
          
            m_HashIndexTable[i].nHashA = -1;   
          
            m_HashIndexTable[i].nHashB = -1;   
          
            m_HashIndexTable[i].bExists = false;   
          
            m_HashIndexTable[i].test_filename[0] = '\0';   
          
        }           
          
    }   
          
    void prepareCryptTable();                                               // 對哈希索引表預處理   
          
    unsigned long HashString(char *lpszFileName, unsigned long dwHashType); // 求取哈希值       
          
    long GetHashTablePos( char *lpszString );                               // 得到在定長表中的位置   
          
    bool SetHashTable( char *lpszString );                                  // 將字符串散列到哈希表中   
          
    unsigned long GetTableLength(void);   
          
    void SetTableLength( const unsigned long nLength );   
          
    ~CHashAlgo()   
          
    {   
          
        if ( NULL != m_HashIndexTable )   
          
        {   
          
            delete []m_HashIndexTable;   
          
            m_HashIndexTable = NULL;   
          
            m_tablelength = 0;   
          
        }   
          
    }   
          
protected:   
          
private:   
          
    unsigned long cryptTable[0x500];   
          
    unsigned long m_tablelength;    // 哈希索引表長度   
          
    MPQHASHTABLE *m_HashIndexTable;   
          
};  
          
/////////////////////////////////////////////////////////////////////////////
          
// Name:        HashAlgo.h
          
// Purpose:     使用魔獸Hash算法，實現索引表的填充和查找功能。
          
// Author:      陳相禮
          
// Modified by:
          
// Created:     07/30/09
          
// RCS-ID:      $Id: treetest.h 43021 2009-07-30 16:36:51Z VZ $
          
// Copyright:   (C) Copyright 2009, TSong Corporation, All Rights Reserved.
          
// Licence:     
          
/////////////////////////////////////////////////////////////////////////////
          
#define MAXFILENAME 255     // 最大文件名長度
          
#define MAXTABLELEN 1024    // 默認哈希索引表大小
          
//////////////////////////////////////////////////////////////////////////
          
// 測試宏定義，正式使用時關閉
          
#define DEBUGTEST 1
          
//////////////////////////////////////////////////////////////////////////
          
// 哈希索引表定義
          
typedef struct
          
{
          
    long nHashA;
          
    long nHashB;
          
    bool bExists;
          
    char test_filename[MAXFILENAME];
          
    // ......
          
} MPQHASHTABLE;
          
//////////////////////////////////////////////////////////////////////////
          
// 對哈希索引表的算法進行封裝
          
class CHashAlgo
          
{
          
public:
          
#if DEBUGTEST
          
    long  testid;   // 測試之用
          
#endif
          
    CHashAlgo( const long nTableLength = MAXTABLELEN )// 創建指定大小的哈希索引表，不帶參數的構造函數創建默認大小的哈希索引表
          
    {
          
        prepareCryptTable();
          
        m_tablelength = nTableLength;
          
        
          
        m_HashIndexTable = new MPQHASHTABLE[nTableLength];
          
        for ( int i = 0; i < nTableLength; i++ )
          
        {
          
            m_HashIndexTable[i].nHashA = -1;
          
            m_HashIndexTable[i].nHashB = -1;
          
            m_HashIndexTable[i].bExists = false;
          
            m_HashIndexTable[i].test_filename[0] = '\0';
          
        }        
          
    }
          
    void prepareCryptTable();                                               // 對哈希索引表預處理
          
    unsigned long HashString(char *lpszFileName, unsigned long dwHashType); // 求取哈希值    
          
    long GetHashTablePos( char *lpszString );                               // 得到在定長表中的位置
          
    bool SetHashTable( char *lpszString );                                  // 將字符串散列到哈希表中
          
    unsigned long GetTableLength(void);
          
    void SetTableLength( const unsigned long nLength );
          
    ~CHashAlgo()
          
    {
          
        if ( NULL != m_HashIndexTable )
          
        {
          
            delete []m_HashIndexTable;
          
            m_HashIndexTable = NULL;
          
            m_tablelength = 0;
          
        }
          
    }
          
protected:
          
private:
          
    unsigned long cryptTable[0x500];
          
    unsigned long m_tablelength;    // 哈希索引表長度
          
    MPQHASHTABLE *m_HashIndexTable;
          
}; 
          

          二、類實現文件
          

          /////////////////////////////////////////////////////////////////////////////    
          
// Name:        HashAlgo.cpp    
          
// Purpose:     使用魔獸Hash算法，實現索引表的填充和查找功能。    
          
// Author:      陳相禮    
          
// Modified by:    
          
// Created:     07/30/09    
          
// RCS-ID:      $Id: treetest.h 43021 2009-07-30 16:36:51Z VZ $    
          
// Copyright:   (C) Copyright 2009, TSong Corporation, All Rights Reserved.    
          
// Licence:         
          
/////////////////////////////////////////////////////////////////////////////    
          
   
          
#include "windows.h"    
          
#include "HashAlgo.h"    
          
   
          
//////////////////////////////////////////////////////////////////////////    
          
// 預處理    
          
void  CHashAlgo::prepareCryptTable()   
          
{    
          
    unsigned long  seed = 0x00100001, index1 = 0, index2 = 0, i;   
          
   
          
    for ( index1 = 0; index1 < 0x100; index1++ )   
          
    {    
          
        for ( index2 = index1, i = 0; i < 5; i++, index2 += 0x100 )   
          
        {    
          
            unsigned long  temp1, temp2;   
          
            seed = (seed * 125 + 3) % 0x2AAAAB;   
          
            temp1 = (seed & 0xFFFF) << 0x10;   
          
            seed = (seed * 125 + 3) % 0x2AAAAB;   
          
            temp2 = (seed & 0xFFFF);   
          
            cryptTable[index2] = ( temp1 | temp2 );    
          
        }    
          
    }    
          
}   
          
   
          
//////////////////////////////////////////////////////////////////////////    
          
// 求取哈希值    
          
unsigned long  CHashAlgo::HashString( char  *lpszFileName, unsigned  long  dwHashType)   
          
{    
          
    unsigned char  *key = (unsigned  char  *)lpszFileName;   
          
    unsigned long  seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;   
          
    int  ch;   
          
   
          
    while (*key != 0)   
          
    {    
          
        ch = toupper(*key++);   
          
   
          
        seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);   
          
        seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;    
          
    }   
          
    return  seed1;    
          
}   
          
   
          
//////////////////////////////////////////////////////////////////////////    
          
// 得到在定長表中的位置    
          
long  CHashAlgo::GetHashTablePos( char  *lpszString)   
          
   
          
{    
          
    const  unsigned  long  HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;   
          
    unsigned long  nHash = HashString(lpszString, HASH_OFFSET);   
          
    unsigned long  nHashA = HashString(lpszString, HASH_A);   
          
    unsigned long  nHashB = HashString(lpszString, HASH_B);   
          
    unsigned long  nHashStart = nHash % m_tablelength,   
          
        nHashPos = nHashStart;   
          
   
          
    while  ( m_HashIndexTable[nHashPos].bExists)   
          
    {    
          
        if  (m_HashIndexTable[nHashPos].nHashA == nHashA && m_HashIndexTable[nHashPos].nHashB == nHash)    
          
            return  nHashPos;    
          
        else     
          
            nHashPos = (nHashPos + 1) % m_tablelength;   
          
   
          
        if  (nHashPos == nHashStart)    
          
            break ;    
          
    }   
          
   
          
    return  -1;  //沒有找到    
          
}   
          
//////////////////////////////////////////////////////////////////////////    
          
// 通過傳入字符串，將相應的表項散列到索引表相應位置中去    
          
bool  CHashAlgo::SetHashTable(  char  *lpszString )   
          
{   
          
    const  unsigned  long  HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;   
          
    unsigned long  nHash = HashString(lpszString, HASH_OFFSET);   
          
    unsigned long  nHashA = HashString(lpszString, HASH_A);   
          
    unsigned long  nHashB = HashString(lpszString, HASH_B);   
          
    unsigned long  nHashStart = nHash % m_tablelength,   
          
        nHashPos = nHashStart;   
          
   
          
    while  ( m_HashIndexTable[nHashPos].bExists)   
          
    {    
          
        nHashPos = (nHashPos + 1) % m_tablelength;   
          
        if  (nHashPos == nHashStart)    
          
        {   
          
   
          
#if DEBUGTEST    
          
            testid = -1;   
          
#endif    
          
   
          
            return   false ;    
          
        }   
          
    }   
          
    m_HashIndexTable[nHashPos].bExists = true ;   
          
    m_HashIndexTable[nHashPos].nHashA = nHashA;   
          
    m_HashIndexTable[nHashPos].nHashB = nHash;   
          
    strcpy( m_HashIndexTable[nHashPos].test_filename, lpszString );   
          
   
          
#if DEBUGTEST    
          
    testid = nHashPos;   
          
#endif    
          
   
          
    return   true ;   
          
}   
          
   
          
//////////////////////////////////////////////////////////////////////////    
          
// 取得哈希索引表長    
          
unsigned long  CHashAlgo::GetTableLength( void )   
          
{   
          
    return  m_tablelength;   
          
}   
          
   
          
//////////////////////////////////////////////////////////////////////////    
          
// 設置哈希索引表長    
          
void  CHashAlgo::SetTableLength(  const  unsigned  long  nLength )   
          
{   
          
    m_tablelength = nLength;   
          
    return ;   
          
}   
          

          view plaincopy to clipboardprint?
          
/////////////////////////////////////////////////////////////////////////////   
          
// Name:        HashAlgo.cpp   
          
// Purpose:     使用魔獸Hash算法，實現索引表的填充和查找功能。   
          
// Author:      陳相禮   
          
// Modified by:   
          
// Created:     07/30/09   
          
// RCS-ID:      $Id: treetest.h 43021 2009-07-30 16:36:51Z VZ $   
          
// Copyright:   (C) Copyright 2009, TSong Corporation, All Rights Reserved.   
          
// Licence:        
          
/////////////////////////////////////////////////////////////////////////////   
          
#include "windows.h"   
          
#include "HashAlgo.h"   
          
//////////////////////////////////////////////////////////////////////////   
          
// 預處理   
          
void CHashAlgo::prepareCryptTable()   
          
{    
          
    unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i;   
          
    for( index1 = 0; index1 < 0x100; index1++ )   
          
    {    
          
        for( index2 = index1, i = 0; i < 5; i++, index2 += 0x100 )   
          
        {    
          
            unsigned long temp1, temp2;   
          
            seed = (seed * 125 + 3) % 0x2AAAAB;   
          
            temp1 = (seed & 0xFFFF) << 0x10;   
          
            seed = (seed * 125 + 3) % 0x2AAAAB;   
          
            temp2 = (seed & 0xFFFF);   
          
            cryptTable[index2] = ( temp1 | temp2 );    
          
        }    
          
    }    
          
}   
          
//////////////////////////////////////////////////////////////////////////   
          
// 求取哈希值   
          
unsigned long CHashAlgo::HashString(char *lpszFileName, unsigned long dwHashType)   
          
{    
          
    unsigned char *key = (unsigned char *)lpszFileName;   
          
    unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;   
          
    int ch;   
          
    while(*key != 0)   
          
    {    
          
        ch = toupper(*key++);   
          
        seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);   
          
        seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;    
          
    }   
          
    return seed1;    
          
}   
          
//////////////////////////////////////////////////////////////////////////   
          
// 得到在定長表中的位置   
          
long CHashAlgo::GetHashTablePos(char *lpszString)   
          
{    
          
    const unsigned long HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;   
          
    unsigned long nHash = HashString(lpszString, HASH_OFFSET);   
          
    unsigned long nHashA = HashString(lpszString, HASH_A);   
          
    unsigned long nHashB = HashString(lpszString, HASH_B);   
          
    unsigned long nHashStart = nHash % m_tablelength,   
          
        nHashPos = nHashStart;   
          
    while ( m_HashIndexTable[nHashPos].bExists)   
          
    {    
          
        if (m_HashIndexTable[nHashPos].nHashA == nHashA && m_HashIndexTable[nHashPos].nHashB == nHash)    
          
            return nHashPos;    
          
        else    
          
            nHashPos = (nHashPos + 1) % m_tablelength;   
          
        if (nHashPos == nHashStart)    
          
            break;    
          
    }   
          
    return -1; //沒有找到   
          
}   
          
//////////////////////////////////////////////////////////////////////////   
          
// 通過傳入字符串，將相應的表項散列到索引表相應位置中去   
          
bool CHashAlgo::SetHashTable( char *lpszString )   
          
{   
          
    const unsigned long HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;   
          
    unsigned long nHash = HashString(lpszString, HASH_OFFSET);   
          
    unsigned long nHashA = HashString(lpszString, HASH_A);   
          
    unsigned long nHashB = HashString(lpszString, HASH_B);   
          
    unsigned long nHashStart = nHash % m_tablelength,   
          
        nHashPos = nHashStart;   
          
    while ( m_HashIndexTable[nHashPos].bExists)   
          
    {    
          
        nHashPos = (nHashPos + 1) % m_tablelength;   
          
        if (nHashPos == nHashStart)    
          
        {   
          
#if DEBUGTEST   
          
            testid = -1;   
          
#endif   
          
            return false;    
          
        }   
          
    }   
          
    m_HashIndexTable[nHashPos].bExists = true;   
          
    m_HashIndexTable[nHashPos].nHashA = nHashA;   
          
    m_HashIndexTable[nHashPos].nHashB = nHash;   
          
    strcpy( m_HashIndexTable[nHashPos].test_filename, lpszString );   
          
#if DEBUGTEST   
          
    testid = nHashPos;   
          
#endif   
          
    return true;   
          
}   
          
//////////////////////////////////////////////////////////////////////////   
          
// 取得哈希索引表長   
          
unsigned long CHashAlgo::GetTableLength(void)   
          
{   
          
    return m_tablelength;   
          
}   
          
//////////////////////////////////////////////////////////////////////////   
          
// 設置哈希索引表長   
          
void CHashAlgo::SetTableLength( const unsigned long nLength )   
          
{   
          
    m_tablelength = nLength;   
          
    return;   
          
}  
          
/////////////////////////////////////////////////////////////////////////////
          
// Name:        HashAlgo.cpp
          
// Purpose:     使用魔獸Hash算法，實現索引表的填充和查找功能。
          
// Author:      陳相禮
          
// Modified by:
          
// Created:     07/30/09
          
// RCS-ID:      $Id: treetest.h 43021 2009-07-30 16:36:51Z VZ $
          
// Copyright:   (C) Copyright 2009, TSong Corporation, All Rights Reserved.
          
// Licence:     
          
/////////////////////////////////////////////////////////////////////////////
          
#include "windows.h"
          
#include "HashAlgo.h"
          
//////////////////////////////////////////////////////////////////////////
          
// 預處理
          
void CHashAlgo::prepareCryptTable()
          
{ 
          
    unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i;
          
    for( index1 = 0; index1 < 0x100; index1++ )
          
    { 
          
        for( index2 = index1, i = 0; i < 5; i++, index2 += 0x100 )
          
        { 
          
            unsigned long temp1, temp2;
          
            seed = (seed * 125 + 3) % 0x2AAAAB;
          
            temp1 = (seed & 0xFFFF) << 0x10;
          
            seed = (seed * 125 + 3) % 0x2AAAAB;
          
            temp2 = (seed & 0xFFFF);
          
            cryptTable[index2] = ( temp1 | temp2 ); 
          
        } 
          
    } 
          
}
          
//////////////////////////////////////////////////////////////////////////
          
// 求取哈希值
          
unsigned long CHashAlgo::HashString(char *lpszFileName, unsigned long dwHashType)
          
{ 
          
    unsigned char *key = (unsigned char *)lpszFileName;
          
    unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;
          
    int ch;
          
    while(*key != 0)
          
    { 
          
        ch = toupper(*key++);
          
        seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);
          
        seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3; 
          
    }
          
    return seed1; 
          
}
          
//////////////////////////////////////////////////////////////////////////
          
// 得到在定長表中的位置
          
long CHashAlgo::GetHashTablePos(char *lpszString)
          
{ 
          
    const unsigned long HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;
          
    unsigned long nHash = HashString(lpszString, HASH_OFFSET);
          
    unsigned long nHashA = HashString(lpszString, HASH_A);
          
    unsigned long nHashB = HashString(lpszString, HASH_B);
          
    unsigned long nHashStart = nHash % m_tablelength,
          
        nHashPos = nHashStart;
          
    while ( m_HashIndexTable[nHashPos].bExists)
          
    { 
          
        if (m_HashIndexTable[nHashPos].nHashA == nHashA && m_HashIndexTable[nHashPos].nHashB == nHash) 
          
            return nHashPos; 
          
        else 
          
            nHashPos = (nHashPos + 1) % m_tablelength;
          
        if (nHashPos == nHashStart) 
          
            break; 
          
    }
          
    return -1; //沒有找到
          
}
          
//////////////////////////////////////////////////////////////////////////
          
// 通過傳入字符串，將相應的表項散列到索引表相應位置中去
          
bool CHashAlgo::SetHashTable( char *lpszString )
          
{
          
    const unsigned long HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;
          
    unsigned long nHash = HashString(lpszString, HASH_OFFSET);
          
    unsigned long nHashA = HashString(lpszString, HASH_A);
          
    unsigned long nHashB = HashString(lpszString, HASH_B);
          
    unsigned long nHashStart = nHash % m_tablelength,
          
        nHashPos = nHashStart;
          
    while ( m_HashIndexTable[nHashPos].bExists)
          
    { 
          
        nHashPos = (nHashPos + 1) % m_tablelength;
          
        if (nHashPos == nHashStart) 
          
        {
          
#if DEBUGTEST
          
            testid = -1;
          
#endif
          
            return false; 
          
        }
          
    }
          
    m_HashIndexTable[nHashPos].bExists = true;
          
    m_HashIndexTable[nHashPos].nHashA = nHashA;
          
    m_HashIndexTable[nHashPos].nHashB = nHash;
          
    strcpy( m_HashIndexTable[nHashPos].test_filename, lpszString );
          
#if DEBUGTEST
          
    testid = nHashPos;
          
#endif
          
    return true;
          
}
          
//////////////////////////////////////////////////////////////////////////
          
// 取得哈希索引表長
          
unsigned long CHashAlgo::GetTableLength(void)
          
{
          
    return m_tablelength;
          
}
          
//////////////////////////////////////////////////////////////////////////
          
// 設置哈希索引表長
          
void CHashAlgo::SetTableLength( const unsigned long nLength )
          
{
          
    m_tablelength = nLength;
          
    return;
          
}
          
 
          

          三、測試主文件
          

          /////////////////////////////////////////////////////////////////////////////    
          
// Name:        DebugMain.cpp    
          
// Purpose:     測試Hash算法封裝的類，完成索引表的填充和查找功能的測試。    
          
// Author:      陳相禮    
          
// Modified by:    
          
// Created:     07/30/09    
          
// RCS-ID:      $Id: treetest.h 43021 2009-07-30 16:36:51Z VZ $    
          
// Copyright:   (C) Copyright 2009, TSong Corporation, All Rights Reserved.    
          
// Licence:         
          
/////////////////////////////////////////////////////////////////////////////    
          
   
          
//////////////////////////////////////////////////////////////////////////    
          
// 測試參數設定宏    
          
#define TESTNUM 32    
          
   
          
#include <iostream>    
          
#include <fstream>    
          
#include "HashAlgo.h"    
          
   
          
using   namespace  std;   
          
   
          
//////////////////////////////////////////////////////////////////////////    
          
// 測試主函數開始    
          
int  main(  int  argc,  char  **argv )   
          
{   
          
    CHashAlgo hash_test( TESTNUM );   
          
   
          
    cout << "取得初始化散列索引表長為："  << hash_test.GetTableLength() << endl;   
          
   
          
    bool  is_success = hash_test.SetHashTable(  "test"  );   
          
    if  ( is_success )   
          
    {   
          
        cout << "散列結果一：成功！"  << endl;   
          
    }   
          
    else    
          
    {   
          
        cout << "散列結果一：失敗！"  << endl;   
          
    }   
          
       
          
    is_success = hash_test.SetHashTable( "測試"  );   
          
    if  ( is_success )   
          
    {   
          
        cout << "散列結果二：成功！"  << endl;   
          
    }   
          
    else    
          
    {   
          
        cout << "散列結果二：失敗！"  << endl;   
          
    }   
          
   
          
    long  pos = hash_test.GetHashTablePos(  "test"  );   
          
    cout << "查找測試字符串：\"test\" 的散列位置："  << pos << endl;   
          
    pos = hash_test.GetHashTablePos( "測試"  );   
          
    cout << "查找測試字符串：“測試” 的散列位置："  << pos << endl;   
          
   
          
    //////////////////////////////////////////////////////////////////////////    
          
    // 散列測試    
          
    for  (  int  i = 0; i < TESTNUM; i++ )   
          
    {   
          
        char  buff[32];   
          
        sprintf(buff, "abcdefg%d." , i);   
          
        is_success = hash_test.SetHashTable(buff);   
          
        is_success ? cout << buff << "散列結果：成功！位置："  << hash_test.testid << endl : cout << buff <<  "散列結果：失敗！"  << endl;         
          
    }   
          
    system( "pause"  );   
          
    //////////////////////////////////////////////////////////////////////////    
          
    // 查找測試    
          
    for  (  int  i = 0; i < TESTNUM; i++ )   
          
    {   
          
        char  buff[32];   
          
        sprintf(buff, "abcdefg%d." , i);   
          
        pos = hash_test.GetHashTablePos( buff );   
          
        pos != -1 ?  cout << "查找測試字符串：" << buff << " 的散列位置："  << pos << endl : cout << buff <<  "存在沖突！"  << endl;      
          
    }   
          
   
          
    system( "pause"  );   
          
    return  0;   
          
}  
          

           
          

          本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/do2jiang/archive/2010/05/07/5565166.aspx
          

	
          
		posted on 2010-12-01 10:36 coody 閱讀(746) 評論(0)  編輯  收藏  
	
          

          
	
	





          
	    
    




          





          


          

	
          
		
          
				
		
	
		
          
		
		
          只有注冊用戶登錄后才能發表評論。
          
		
          
			
		
          
			
		
          
		
		
          
		


          

		          		
		
          
		
          			
		
		
		
		
          
		
          
		
		
          
		
          
			網站導航:
		
		
          
		
          
			
		
          	
		
          
			 
		
          
		
          
			
		
          
		
          
			
				
		
          		
	
          	

          



          

				
				
           
          	
		          		
	
          
	
          


		


          

          
	

          

          
	Copyright © coody
	Powered by: 博客園	模板提供：滬江博客
	

          



	

	
          

    







          
        
	




主站蜘蛛池模板：
泗阳县|
宾川县|
靖边县|
古田县|
卫辉市|
都安|
富顺县|
太原市|
公安县|
乌鲁木齐市|
安溪县|
阳江市|
自治县|
汽车|
永和县|
绥滨县|
甘孜县|
温宿县|
宜川县|
廉江市|
陇南市|
金堂县|
新蔡县|
惠安县|
海盐县|
天气|
偃师市|
游戏|
上高县|
莎车县|
明溪县|
巫溪县|
霸州市|
河源市|
麻江县|
苏尼特右旗|
都安|
富蕴县|
饶河县|
榆树市|
扬中市|