叶子的小屋

暴雪公司有个经典的字符串的hash公式(转)

2013-12-1 admin 转载

《暴雪公司有个经典的字符串的 hash 公式》
打造最快的 Hash 表 ( 和 Blizzard 的对话 )
開元最近学习了一下 Blizzard 的 MPQ 文件格式，颇有一些心得，其中一条就是对 HastTable 的理解，很想写出来给大家共享，感谢 Justin Olbrantz 的文章《 Inside MoPaQ 》，大多认识来源于此。
先提一个简单的问题，如果有一个庞大的字符串数组，然后给你一个单独的字符串，让你从这个数组中查找是否有这个字符串并找到它，你会怎么做？
有一个方法最简单，老老实实从头查到尾，一个一个比较，直到找到为止，我想只要学过程序设计的人都能把这样一个程序作出来，但要是有程序员把这样的程序交给用户，我只能用无语来评价，或许它真的能工作，但 ... 也只能如此了。
最合适的算法自然是使用 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 < < 8) + 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
怎么样，很简单的算法吧，但确实是天才的 idea, 其实最优秀的算法往往是简单有效的算法，
Blizzard 被称为最卓越的游戏制作公司，不愧于此。

 

用一个静态数组给你简单模拟一下 :
#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;
}

这个没有哈希冲突处理 , 可以自己实现一下

标签: 算法