Hash沖突的解決--暴雪的Hash算法

值得一提的是，在解決Hash沖突的時候，搞的焦頭爛額，結果今天上午在自己的部落格内的一篇文章（十一、從頭到尾徹底解析Hash表算法）内找到了解決辦法：網上流傳甚廣的暴雪的Hash算法。 OK，接下來，咱們回顧下暴雪的hash表算法：

“接下來，咱們來具體分析一下一個最快的Hash表算法。

我們由一個簡單的問題逐漸入手：有一個龐大的字元串數組，然後給你一個單獨的字元串，讓你從這個數組中查找是否有這個字元串并找到它，你會怎麼做？

有一個方法最簡單，老老實實從頭查到尾，一個一個比較，直到找到為止，我想隻要學過程式設計的人都能把這樣一個程式作出來，但要是有程式員把這樣的程式交給使用者，我隻能用無語來評價，或許它真的能工作，但...也隻能如此了。

最合适的算法自然是使用HashTable（哈希表），先介紹介紹其中的基本知識，所謂Hash，一般是一個整數，通過某種算法，可以把一個字元串"壓縮" 成一個整數。當然，無論如何，一個32位整數是無法對應回一個字元串的，但在程式中，兩個字元串計算出的Hash值相等的可能非常小，下面看看在MPQ中的Hash算法：

函數prepareCryptTable以下的函數生成一個長度為0x500（合10進制數：1280）的cryptTable[0x500]

//函數prepareCryptTable以下的函數生成一個長度為0x500（合10進制數：1280）的cryptTable[0x500]
void 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 );
}
}
}

函數HashString以下函數計算lpszFileName 字元串的hash值，其中dwHashType 為hash的類型，

//函數HashString以下函數計算lpszFileName 字元串的hash值，其中dwHashType 為hash的類型，
unsigned long HashString(const char *lpszkeyName, unsigned long dwHashType )
{
unsigned char *key = (unsigned char *)lpszkeyName;
unsigned long seed1 = 0x7FED7FED;
unsigned long seed2 = 0xEEEEEEEE;
int ch;
while( *key != 0 )
{
ch = *key++;
seed1 = cryptTable[(dwHashType<<8) + ch] ^ (seed1 + seed2);
seed2 = ch + seed1 + seed2 + (seed2<<5) + 3;
}
return seed1;
}

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)，現在仔細看看這個算法吧：

typedef struct
{
int nHashA;
int nHashB;
char bExists;
......
} SOMESTRUCTRUE;
//一種可能的結構體定義？

函數GetHashTablePos下述函數為在Hash表中查找是否存在目标字元串，有則傳回要查找字元串的Hash值，無則，return -1.

//函數GetHashTablePos下述函數為在Hash表中查找是否存在目标字元串，有則傳回要查找字元串的Hash值，無則，return -1.
int GetHashTablePos( har *lpszString, SOMESTRUCTURE *lpTable )
//lpszString要在Hash表中查找的字元串，lpTable為存儲字元串Hash值的Hash表。
{
int nHash = HashString(lpszString); //調用上述函數HashString，傳回要查找字元串lpszString的Hash值。
int nHashPos = nHash % nTableSize;
if ( lpTable[nHashPos].bExists && !strcmp( lpTable[nHashPos].pString, lpszString ) )
{ //如果找到的Hash值在表中存在，且要查找的字元串與表中對應位置的字元串相同，
return nHashPos; //傳回找到的Hash值
}
else
{
return -1;
}
}

看到此，我想大家都在想一個很嚴重的問題：“如果兩個字元串在哈希表中對應的位置相同怎麼辦？”,畢竟一個數組容量是有限的，這種可能性很大。解決該問題的方法很多，我首先想到的就是用“連結清單”,感謝大學裡學的資料結構教會了這個百試百靈的法寶，我遇到的很多算法都可以轉化成連結清單來解決，隻要在哈希表的每個入口挂一個連結清單，儲存所有對應的字元串就OK了。事情到此似乎有了完美的結局，如果是把問題獨自交給我解決，此時我可能就要開始定義資料結構然後寫代碼了。

然而Blizzard的程式員使用的方法則是更精妙的方法。基本原理就是：他們在哈希表中不是用一個哈希值而是用三個哈希值來校驗字元串。”

“MPQ 使用檔案名哈希表來跟蹤内部的所有檔案。但是這個表的格式與正常的哈希表有一些不同。首先，它沒有使用哈希作為下标，把實際的檔案名存儲在表中用于驗證，實際上它根本就沒有存儲檔案名。而是使用了3種不同的哈希：一個用于哈希表的下标，兩個用于驗證。這兩個驗證哈希替代了實際檔案名。

當然了，這樣仍然會出現2個不同的檔案名哈希到3個同樣的哈希。但是這種情況發生的機率平均是：1:18889465931478580854784，這個機率對于任何人來說應該都是足夠小的。現在再回到資料結構上，Blizzard使用的哈希表沒有使用連結清單，而采用"順延"的方式來解決問題。”下面，咱們來看看這個網上流傳甚廣的暴雪hash算法：

函數GetHashTablePos中，lpszString 為要在hash表中查找的字元串；lpTable 為存儲字元串hash值的hash表；nTableSize 為hash表的長度：

//函數GetHashTablePos中，lpszString 為要在hash表中查找的字元串；lpTable 為存儲字元串hash值的hash表；nTableSize 為hash表的長度：
int GetHashTablePos( char *lpszString, MPQHASHTABLE *lpTable, int nTableSize )
{
const int HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;
int nHash = HashString( lpszString, HASH_OFFSET );
int nHashA = HashString( lpszString, HASH_A );
int nHashB = HashString( lpszString, HASH_B );
int nHashStart = nHash % nTableSize;
int nHashPos = nHashStart;
while ( lpTable[nHashPos].bExists )
{
// 如果僅僅是判斷在該表中時候存在這個字元串，就比較這兩個hash值就可以了，不用對結構體中的字元串進行比較。
// 這樣會加快運作的速度？減少hash表占用的空間？這種方法一般應用在什麼場合？
if ( 　 lpTable[nHashPos].nHashA == nHashA
&& lpTable[nHashPos].nHashB == nHashB )
{
return nHashPos;
}
else
{
nHashPos = (nHashPos + 1) % nTableSize;
}
if (nHashPos == nHashStart)
break;
}
return -1;
}

上述程式解釋：

計算出字元串的三個哈希值（一個用來确定位置，另外兩個用來校驗)
察看哈希表中的這個位置
哈希表中這個位置為空嗎？如果為空，則肯定該字元串不存在，傳回-1。
如果存在，則檢查其他兩個哈希值是否也比對，如果比對，則表示找到了該字元串，傳回其Hash值。
移到下一個位置，如果已經移到了表的末尾，則反繞到表的開始位置起繼續查詢　
看看是不是又回到了原來的位置，如果是，則傳回沒找到
回到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 $
// 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 $
// 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 $
// 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;
}

Hash沖突的解決--暴雪的Hash算法

繼續閱讀

C#實作MD5加密（32位md5加密和16位md5加密）

餓了麼 java開發面試經驗2017

hash位址_Hash算法基礎

java面試技巧一Java面試的十個小技巧❗️許多Java程式員要面臨着面試的各種問題，而也有許多學院将要去進行面試，在

Java 并發包中的進階同步工具 + 面試題Java 并發包中的進階同步工具

Unity3d+C#：Dictionary源碼與使用注意（轉）

Hash算法解決沖突的方法

各種字元串Hash函數比較及各種Hash算法代碼大全

HashMap底層分析_計算hash值

HashMap源碼重點分析

hash算法_redis系列之——一緻性hash算法

劍指Offer_矩形覆寫_10

相似資料檢測算法彙總

Java 面試（一） | Java基礎部分Java面試基礎部分Java面試面向對象部分Java面試異常處理部分Java面試常用API部分Java面試IO部分Java面試集合部分

劍指Offer_二進制中1的個數_11

java 四種數組排序方法