暴雪公司有个经典的字符串的hash公式
先提一个简单的问题,假如有一个庞大的字符串数组,然后给你一个单独的字符串,让你从这个数组中查找是否有这个字符串并找到它,你会怎么做?
有一个方法最简单,老老实实从头查到尾,一个一个比较,直到找到为止,我想只要学过程序设计的人都能把这样一个程序作出来,但要是有程序员把这样的程序交给用户,我只能用无语来评价,或许它真的能工作,但...也只能如此了。
最合适的算法自然是使用HashTable(哈希表),先介绍介绍其中的基本知识,所谓Hash,一般是一个整数,通过某种算法,可以把一个字符串"压缩" 成一个整数,这个数称为Hash,当然,无论如何,一个32位整数是无法对应回一个字符串的,但在程序中,两个字符串计算出的Hash值相等的可能非常小,下面看看在MPQ中的Hash算法
unsigned long 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 < <
ch] ^ (seed1 seed2);
seed2 = ch seed1 seed2 (seed2 < < 5) 3;
}
return seed1;
}
Blizzard的这个算法是非常高效的,被称为"One-Way Hash",举个例子,字符串"unitneutralacritter.grp"通过这个算法得到的结果是0xA26067F3。
是不是把第一个算法改进一下,改成逐个比较字符串的Hash值就可以了呢,答案是,远远不够,要想得到最快的算法,就不能进行逐个的比较,通常是构造一个哈希表(Hash Table)来解决问题,哈希表是一个大数组,这个数组的容量根据程序的要求来定义,例如1024,每一个Hash值通过取模运算 (mod)对应到数组中的一个位置,这样,只要比较这个字符串的哈希值对应的位置又没有被占用,就可以得到最后的结果了,想想这是什么速度?是的,是最快的O(1),现在仔细看看这个算法吧
int GetHashTablePos(char *lpszString, SOMESTRUCTURE *lpTable, int nTableSize)
{
int nHash = HashString(lpszString), nHashPos = nHash % nTableSize;
if (lpTable[nHashPos].bExists && !strcmp(lpTable[nHashPos].pString, lpszString))
return nHashPos;
else
return -1; //Error value
}
看到此,我想大家都在想一个很严重的问题:"假如两个字符串在哈希表中对应的位置相同怎么办?",究竟一个数组容量是有限的,这种可能性很大。解决该问题的方法很多,我首先想到的就是用"链表",感谢大学里学的数据结构教会了这个百试百灵的法宝,我碰到的很多算法都可以转化成链表来解决,只要在哈希表的每个入口挂一个链表,保存所有对应的字符串就OK了。
事情到此似乎有了完美的结局,假如是把问题独自交给我解决,此时我可能就要开始定义数据结构然后写代码了。然而Blizzard的程序员使用的方法则是更精妙的方法。基本原理就是:他们在哈希表中不是用一个哈希值而是用三个哈希值来校验字符串。
中国有句古话"再一再二不能再三再四",看来Blizzard也深得此话的精髓,假如说两个不同的字符串经过一个哈希算法得到的入口点一致有可能,但用三个不同的哈希算法算出的入口点都一致,那几乎可以肯定是不可能的事了,这个几率是1:18889465931478580854784,大概是10的 22.3次方分之一,对一个游戏程序来说足够安全了。
现在再回到数据结构上,Blizzard使用的哈希表没有使用链表,而采用"顺延"的方式来解决问题,看看这个算法:
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, nHashPos = nHashStart;
while (lpTable[nHashPos].bExists)
{
if (lpTable[nHashPos].nHashA == nHashA && lpTable[nHashPos].nHashB == nHashB)
return nHashPos;
else
nHashPos = (nHashPos 1) % nTableSize;
if (nHashPos == nHashStart)
break;
}
return -1; //Error value
}
1. 计算出字符串的三个哈希值(一个用来确定位置,另外两个用来校验)
2. 察看哈希表中的这个位置
3. 哈希表中这个位置为空吗?假如为空,则肯定该字符串不存在,返回
4. 假如存在,则检查其他两个哈希值是否也匹配,假如匹配,则表示找到了该字符串,返回
5. 移到下一个位置,假如已经越界,则表示没有找到,返回
6. 看看是不是又回到了原来的位置,假如是,则返回没找到
7. 回到3
分享到:
相关推荐
最快的排序算法 java实现哈希算法-Java–哈希算法–最快的实现,排序算法数据结构
最快的排序算法 javahash实现-Java-哈希算法-最快的实现,排序算法数据结构
暴雪公司有个经典的字符串的hash公式,对于新手来说绝对有学习价值
The book is based on Stanford Computer Science course CS246: Mining Massive Datasets (and CS345A: Data Mining). The book, like the course, is designed at the undergraduate computer science level with...
哈希表--链表 哈希表--链表 哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表
完善后发布。仅限科学研究,不能用于商业应用
最合适的算法自然是使用HashTable(哈希表),先介绍介绍其中的基本知识,所谓Hash,一般是一个整数,通过某种算法,可以把一个字符串"压缩" 成一个整数,这个数称为Hash,当然,无论如何,一个32位整数是无法对应回...
这是传说中异常强悍的暴雪公司研究的哈希算法,采用三个哈希表来防止冲突,代码简练自成一体,无论是思想还是代码风格都非常值得大家学习!
第1章 哈希和哈希表-2020.08.19 第1章 哈希和哈希表-2020.08.19 第1章 哈希和哈希表-2020.08.19 第1章 哈希和哈希表-2020.08.19 第1章 哈希和哈希表-2020.08.19
参考网上博客的感知哈希算法的理论知识,实现基本的感知哈希算法,内有几张图片用来测试,程序可参考。
针对分布式存储系统中如何实现数据在物理存储上的均匀分布和高效定位的问题,对多种哈希算法展开研究,提出了衡量分布式存储系统哈希算法优劣的标准;从散列分布性、哈希冲突和计算效率等多个维度对这些哈希算法进行...
弱哈希算法签名的SSL证书(CVE-2004-2761)。 远程服务使用SSL证书链,该证书链已使用加密弱哈希算法(例如MD2、MD4、MD5或SHA1)签名。这些签名算法很容易受到碰撞攻击。攻击者可以利用这一点生成另一个具有相同数字...
xxHash-极快的哈希算法xxHash是一种极快的哈希算法,以RAM速度限制运行。 它成功完成了SMHasher测试套件的测试套件,该套件评估h的碰撞,扩散和随机性xxHash-极快哈希算法xxHash是一种极快哈希算法,在RAM速度限制下...
最快的排序算法 最快的内容查找算法-----暴雪的Hash算法,排序算法数据结构
基于python与哈希算法实现图像去重
哈希表 哈希表_使用C++实现的哈希表_HashTable
哈希表 哈希表_使用Java开发的哈希表_HashTable
HACH哈希SC-200通用控制器中文操作说明书.pdf
大数据-算法-哈希函数设计.pdf
Android的感知哈希算法