Hash冲突的解决--暴雪的Hash算法

值得一提的是，在解决Hash冲突的时候，搞的焦头烂额，结果今天上午在自己的博客内的一篇文章（十一、从头到尾彻底解析Hash表算法）内找到了解决办法：网上流传甚广的暴雪的Hash算法。 OK，接下来，咱们回顾下暴雪的hash表算法：

“接下来，咱们来具体分析一下一个最快的Hash表算法。
我们由一个简单的问题逐步入手：有一个庞大的字符串数组，然后给你一个单独的字符串，让你从这个数组中查找是否有这个字符串并找到它，你会怎么做？
有一个方法最简单，老老实实从头查到尾，一个一个比较，直到找到为止，我想只要学过程序设计的人都能把这样一个程序作出来，但要是有程序员把这样的程序交给用户，我只能用无语来评价，或许它真的能工作，但...也只能如此了。
最合适的算法自然是使用HashTable（哈希表），先介绍介绍其中的基本知识，所谓Hash，一般是一个整数，通过某种算法，可以把一个字符串"压缩" 成一个整数。当然，无论如何，一个32位整数是无法对应回一个字符串的，但在程序中，两个字符串计算出的Hash值相等的可能非常小，下面看看在MPQ中的Hash算法：
    函数prepareCryptTable以下的函数生成一个长度为0x500（合10进制数：1280）的cryptTable[0x500]

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.   
12.             seed = (seed * 125 + 3) % 0x2AAAAB;  
13.             temp1 = (seed & 0xFFFF) << 0x10;  
14.   
15.             seed = (seed * 125 + 3) % 0x2AAAAB;  
16.             temp2 = (seed & 0xFFFF);  
17.   
18.             cryptTable[index2] = ( temp1 | temp2 );   
19.         }   
20.     }   
21. }   

    函数HashString以下函数计算lpszFileName 字符串的hash值，其中dwHashType 为hash的类型，

 

1. //函数HashString以下函数计算lpszFileName 字符串的hash值，其中dwHashType 为hash的类型，  
2. unsigned long HashString(const char *lpszkeyName, unsigned long dwHashType )  
3. {  
4.     unsigned char *key  = (unsigned char *)lpszkeyName;  
5.     unsigned long seed1 = 0x7FED7FED;  
6.     unsigned long seed2 = 0xEEEEEEEE;  
7.     int ch;  
8.   
9.     while( *key != 0 )  
10.     {  
11.         ch = *key++;  
12.         seed1 = cryptTable[(dwHashType<<8) + ch] ^ (seed1 + seed2);  
13.         seed2 = ch + seed1 + seed2 + (seed2<<5) + 3;  
14.     }  
15.     return seed1;  
16. }  

 

    Blizzard的这个算法是非常高效的，被称为"One-Way Hash"( A one-way hash is a an algorithm that is constructed in such a way that deriving the original string (set of strings, actually) is virtually impossible)。举个例子，字符串"unitneutralacritter.grp"通过这个算法得到的结果是0xA26067F3。
　是不是把第一个算法改进一下，改成逐个比较字符串的Hash值就可以了呢，答案是，远远不够，要想得到最快的算法，就不能进行逐个的比较，通常是构造一个哈希表(Hash Table)来解决问题，哈希表是一个大数组，这个数组的容量根据程序的要求来定义，
     例如1024，每一个Hash值通过取模运算 (mod) 对应到数组中的一个位置，这样，只要比较这个字符串的哈希值对应的位置有没有被占用，就可以得到最后的结果了，想想这是什么速度？是的，是最快的O(1)，现在仔细看看这个算法吧：

1. typedef struct  
2. {  
3.     int nHashA;  
4.     int nHashB;  
5.     char bExists;  
6.    ......  
7. } SOMESTRUCTRUE;  
8. //一种可能的结构体定义？  

    函数GetHashTablePos下述函数为在Hash表中查找是否存在目标字符串，有则返回要查找字符串的Hash值，无则，return -1.

1. //函数GetHashTablePos下述函数为在Hash表中查找是否存在目标字符串，有则返回要查找字符串的Hash值，无则，return -1.  
2. int GetHashTablePos( har *lpszString, SOMESTRUCTURE *lpTable )   
3. //lpszString要在Hash表中查找的字符串，lpTable为存储字符串Hash值的Hash表。  
4. {   
5.     int nHash = HashString(lpszString);  //调用上述函数HashString，返回要查找字符串lpszString的Hash值。  
6.     int nHashPos = nHash % nTableSize;  
7.    
8.     if ( lpTable[nHashPos].bExists  &&  !strcmp( lpTable[nHashPos].pString, lpszString ) )   
9.     {  //如果找到的Hash值在表中存在，且要查找的字符串与表中对应位置的字符串相同，  
10.         return nHashPos;    //返回找到的Hash值  
11.     }   
12.     else  
13.     {  
14.         return -1;    
15.     }   
16. }  

    看到此，我想大家都在想一个很严重的问题：“如果两个字符串在哈希表中对应的位置相同怎么办？”,毕竟一个数组容量是有限的，这种可能性很大。解决该问题 的方法很多，我首先想到的就是用“链表”,感谢大学里学的数据结构教会了这个百试百灵的法宝，我遇到的很多算法都可以转化成链表来解决，只要在哈希表的每 个入口挂一个链表，保存所有对应的字符串就OK了。事情到此似乎有了完美的结局，如果是把问题独自交给我解决，此时我可能就要开始定义数据结构然后写代码 了。
    然而Blizzard的程序员使用的方法则是更精妙的方法。基本原理就是：他们在哈希表中不是用一个哈希值而是用三个哈希值来校验字符串。”

    “MPQ 使用文件名哈希表来跟踪内部的所有文件。但是这个表的格式与正常的哈希表有一些不同。首先，它没有使用哈希作为下标，把实际的文件名存储在表中用于验证， 实际上它根本就没有存储文件名。而是使用了3种不同的哈希：一个用于哈希表的下标，两个用于验证。这两个验证哈希替代了实际文件名。
    当然了，这样仍然会出现2个不同的文件名哈希到3个同样的哈希。但是这种情况发生的概率平均是：1:18889465931478580854784，这 个概率对于任何人来说应该都是足够小的。现在再回到数据结构上，Blizzard使用的哈希表没有使用链表，而采用"顺延"的方式来解决问题。”下面，咱们来看看这个网上流传甚广的暴雪hash算法：
    函数GetHashTablePos中，lpszString 为要在hash表中查找的字符串；lpTable 为存储字符串hash值的hash表；nTableSize 为hash表的长度： 

1. //函数GetHashTablePos中，lpszString 为要在hash表中查找的字符串；lpTable 为存储字符串hash值的hash表；nTableSize 为hash表的长度：   
2. int GetHashTablePos( char *lpszString, MPQHASHTABLE *lpTable, int nTableSize )  
3. {  
4.     const int  HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;  
5.    
6.     int  nHash = HashString( lpszString, HASH_OFFSET );  
7.     int  nHashA = HashString( lpszString, HASH_A );  
8.     int  nHashB = HashString( lpszString, HASH_B );  
9.     int  nHashStart = nHash % nTableSize;  
10.     int  nHashPos = nHashStart;  
11.    
12.     while ( lpTable[nHashPos].bExists )  
13.    {  
14. //     如果仅仅是判断在该表中时候存在这个字符串，就比较这两个hash值就可以了，不用对结构体中的字符串进行比较。  
15. //         这样会加快运行的速度？减少hash表占用的空间？这种方法一般应用在什么场合？  
16.         if ( 　 lpTable[nHashPos].nHashA == nHashA  
17.         &&  lpTable[nHashPos].nHashB == nHashB )  
18.        {  
19.             return nHashPos;  
20.        }  
21.        else  
22.        {  
23.             nHashPos = (nHashPos + 1) % nTableSize;  
24.        }  
25.    
26.         if (nHashPos == nHashStart)  
27.               break;  
28.     }  
29.      return -1;  
30. }  

    上述程序解释：

1. 计算出字符串的三个哈希值（一个用来确定位置，另外两个用来校验)
2. 察看哈希表中的这个位置
3. 哈希表中这个位置为空吗？如果为空，则肯定该字符串不存在，返回-1。
4. 如果存在，则检查其他两个哈希值是否也匹配，如果匹配，则表示找到了该字符串，返回其Hash值。
5. 移到下一个位置，如果已经移到了表的末尾，则反绕到表的开始位置起继续查询　
6. 看看是不是又回到了原来的位置，如果是，则返回没找到
7. 回到3。

下面用一个静态数组做一个简单模拟（没有处理hash冲突）：

#include <stdio.h>
#define HASH_TABLE_SIZE 13 // 哈希表的大小应是个质数
struct mapping
{
  void *key;
  void *data;
} hash_table[HASH_TABLE_SIZE];

unsigned int
RSHash (char *str)
{
  unsigned int b = 378551;
  unsigned int a = 63689;
  unsigned int hash =      0  ;

  while (*str)
    {
      hash = hash * a + (*str++);
      a *= b;
    }
  return (hash & 0x7FFFFFFF);
}

int main ()
{
  char *str = "we are the world!";
  char *filename = "myfile.txt";
  unsigned int hash_offset;
  // 初始化哈希表
  memset (hash_table, 0x0, sizeof (hash_table));

  // 将字符串插入哈希表 .
  hash_offset = RSHash (str) % HASH_TABLE_SIZE;
  hash_table[hash_offset].key = str;
  hash_table[hash_offset].data = filename;

  // 查找 str 是否存在于 hash_table.
  hash_offset = RSHash (str) % HASH_TABLE_SIZE;
  if (hash_table[hash_offset].key)
        printf ("string '%s' exists in the file %s./n", str, hash_table[hash_offset].data);
  else
        printf ("string '%s' does not exist./n", str);

return 0;
}

• 下面是一个类的封装：
• 代码  
•   
• 一、类声明头文件  
• /////////////////////////////////////////////////////////////////////////////  
• // 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( constlong 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.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  
•     
•             returnfalse;      
•         }     
•     }     
•     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  
•     
•     returntrue;     
• }     
•     
• //////////////////////////////////////////////////////////////////////////     
• // 取得哈希索引表长     
• unsigned long CHashAlgo::GetTableLength(void)     
• {     
•     return m_tablelength;     
• }     
•     
• //////////////////////////////////////////////////////////////////////////     
• // 设置哈希索引表长     
• void CHashAlgo::SetTableLength( const unsigned long nLength )     
• {     
•     m_tablelength = nLength;     
•     return;     
• }    
•   
• 三、测试主文件  
• view plaincopy to clipboardprint?  
• /////////////////////////////////////////////////////////////////////////////     
• // 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"     
•     
• usingnamespace 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" );     
•     return0;     
• }