参考文章：《Inside MoPaQ》chapter two
适用场合：存在一个庞大的字符串数组，给定一个字符串，判断其是否在字符串数组中；
主要思想：
1、分配一段大小为(MAXMPQHASHTABLELEN * sizeof(MPQHASHTABLE))的堆空间作为哈希表；
MPQHASHTABLE定义如下：
typedef struct {
long nHashA;
long nHashB;
unsigned int bExists;
}MPQHASHTABLE;
2、将字符串存入哈希表时，为每个字符串计算三个哈希值，nHash， nHashA， nHashB， nHash用于确定字符串在哈希表中的位置，nHashA，nHashB用于验证字符串，当>2个字符串的nHash值相等时，顺延存入下一个可用的位置；
代码实现：
1 #include "blizzard_hash.h"
2
3 static void InitCryptTable()
4 {
5 unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i;
6
7 for (index1 = 0; index1 < 0x100; index1++)
8 {
9 for (index2 = index1, i = 0; i < 5; i++, index2 += 0x100)
10 {
11 unsigned long temp1, temp2;
12 seed = (seed * 125 + 3) % 0x2AAAAB;
13 temp1 = (seed & 0xFFFF) << 0x10;
14 seed = (seed * 125 + 3) % 0x2AAAAB;
15 temp2 = (seed & 0xFFFF);
16 cryptTable[index2] = (temp1 | temp2);
17 }
18 }
19 }
20
21 /*
22 函数名:HashString
23 功能:计算字符串的哈希值
24 参数:lpszString:字符串的地址
25 dwHashType:哈希值类型
26 dwHashType = 0时计算的哈希值用于确定字符串在哈希表中的位置；
27 dwHashType = 1，dwHashType = 2时计算的哈希值用于验证字符串
28 返回值:字符串的哈希值
29 */
30 unsigned long HashString(char *lpszString, unsigned long dwHashType)
31 {
32 unsigned char *key = (unsigned char *)lpszString;
33 unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;
34 int ch;
35
36 while(*key != 0)
37 {
38 ch = toupper(*key++);
39
40 seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);
41 seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;
42 }
43 return seed1;
44 }
45
46 /*
47 函数名:MPQHashTableInit
48 功能:初始化哈希表
49 参数:*ppHashTable:返回分配的哈希表的地址
50 nTableLength:哈希表的长度
51 返回值:0:失败
52 1:成功
53 */
54 unsigned int MPQHashTableInit(char **ppHashTable, long nTableLength)
55 {
56 long i = 0;
57 char *p = NULL;
58 MPQHASHTABLE *_pHashTable = NULL;
59
60 InitCryptTable();
61
62 p = malloc(nTableLength * sizeof(MPQHASHTABLE));
63 if (p == NULL)
64 {
65 printf("%s, %d: malloc failed!\n", __FUNCTION__, __LINE__);
66 return 0;
67 }
68 *ppHashTable = p;
69 _pHashTable = (MPQHASHTABLE *)p;
70
71 for (i = 0; i < nTableLength; i++)
72 {
73 (_pHashTable + i)->nHashA = -1;
74 (_pHashTable + i)->nHashB = -1;
75 (_pHashTable + i)->bExists = 0;
76 }
77
78 return 1;
79 }
80
81 /*
82 函数名:MPQHashTableFree
83 功能:释放哈希表
84 参数:pHashTable:哈希表的地址
85 返回值:无
86 */
87 void MPQHashTableFree(char *pHashTable)
88 {
89 if (pHashTable != NULL)
90 {
91 free(pHashTable);
92 pHashTable = NULL;
93 }
94 }
95
96 /*
97 函数名:MPQHashTableAdd
98 功能:将字符串的信息加入哈希表
99 参数:lpszString:字符串的地址
100 pHashTable:哈希表的地址
101 返回值:0:失败
102 1:成功
103 */
104 unsigned int MPQHashTableAdd(char *lpszString, char *pHashTable)
105 {
106 const unsigned long HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;
107 unsigned long nHash = HashString(lpszString, HASH_OFFSET);
108 unsigned long nHashA = HashString(lpszString, HASH_A);
109 unsigned long nHashB = HashString(lpszString, HASH_B);
110 unsigned long nHashStart = nHash % MAXMPQHASHTABLELEN;
111 unsigned long nHashPos = nHashStart;
112 MPQHASHTABLE *_pHashTable = (MPQHASHTABLE *)pHashTable;
113
114 while ((_pHashTable + nHashPos)->bExists)
115 {
116 nHashPos = (nHashPos + 1) % MAXMPQHASHTABLELEN;
117
118 if (nHashPos == nHashStart)
119 {
120 return 0;
121 }
122 }
123
124 (_pHashTable + nHashPos)->nHashA = nHashA;
125 (_pHashTable + nHashPos)->nHashB = nHashB;
126 (_pHashTable + nHashPos)->bExists = 1;
127
128 return 1;
129 }
130
131 /*
132 函数名:MPQHashTableIsExist
133 功能:判断某字符串在哈希表中是否存在
134 参数:lpszString:字符串的地址
135 pHashTable:哈希表的地址
136 返回值:-1:不存在
137 nHashPos 该字符串在哈希表中的索引值
138 */
139 long MPQHashTableIsExist(char *lpszString, char *pHashTable)
140 {
141 const unsigned long HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;
142 unsigned long nHash = HashString(lpszString, HASH_OFFSET);
143 unsigned long nHashA = HashString(lpszString, HASH_A);
144 unsigned long nHashB = HashString(lpszString, HASH_B);
145 unsigned long nHashStart = nHash % MAXMPQHASHTABLELEN;
146 unsigned long nHashPos = nHashStart;
147 MPQHASHTABLE *_pHashTable = (MPQHASHTABLE *)pHashTable;
148
149 while ((_pHashTable + nHashPos)->bExists)
150 {
151 if (((_pHashTable + nHashPos)->nHashA == nHashA) &&
152 ((_pHashTable + nHashPos)->nHashB == nHashB))
153 {
154 return nHashPos;
155 }
156 else
157 {
158 nHashPos = (nHashPos +1) % MAXMPQHASHTABLELEN;
159 }
160 if (nHashPos == nHashStart)
161 {
162 break;
163 }
164 }
165 return -1;
166 }
附件：暴雪哈希算法代码