值得一提的是,在解决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。
- #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;
- }
相关推荐
在暴雪的Hash算法中,使用了一个经典的字符串Hash公式,能够快速地生成哈希值。该算法的核心思想是使用一个循环来计算字符串的哈希值,循环中使用了两个种子数seed1和seed2,通过对字符串的每个字符进行toupper操作...
在计算机科学领域中,排序算法是一种基本的算法,它可以将数据按照一定的顺序排列,以便更好地存储、检索和处理数据。排序算法的速度和效率对程序的性能有着至关重要的影响。 1.冒泡排序算法 冒泡排序算法是一种...
### 暴雪哈希算法源码解析与应用 #### 一、暴雪哈希算法...对于想要深入了解哈希算法原理及其实现的新手而言,暴雪哈希算法不仅具有很高的学习价值,还能够帮助开发者理解如何在实际项目中应用哈希算法解决具体问题。
综上所述,暴雪哈希算法以其独特的设计理念和高效的冲突解决策略,在哈希算法领域独树一帜。通过学习和理解这种算法,开发者不仅可以提升自身在数据处理和存储方面的技能,还能从中获得启发,设计出更适合特定应用...
### 暴雪哈希算法详解 ...通过合理的哈希函数设计和冲突解决策略,可以极大地提高数据的查询效率。对于开发者而言,深入理解并掌握暴雪哈希算法的工作原理及其应用场景,将有助于提升软件系统的整体性能。
3. **冲突处理**:解决冲突的方法有多种,包括链地址法(使用链表)、开放寻址法等。本文重点关注的是一种更高级的解决方案——使用多个散列值。 #### Blizzard的多散列值技术 Blizzard的解决方案不仅仅是使用一个...
函数名:HashString 功能:计算字符串的哈希值 参数:lpszString:字符串的地址 dwHashType:哈希值类型 dwHashType = 0时计算的哈希值用于确定字符串在哈希表中的位置; dwHashType = 1,dwHashType = 2时计算的...
哈希表(Hash Table)是一种数据结构,它...暴雪的哈希表实现提供了关于如何构建高效哈希表的一个实例,它不仅包括哈希函数的设计,还有对冲突解决策略的考虑,这对于理解和优化自己的哈希表实现具有重要的参考价值。