摘要：
＝0）7｛8ch＝toupper；9种子1＝cryptTable[+ch]^；10种子2＝ch+种子1+种子2++3；11｝12返回种子1；13} 暴雪的算法非常有效。它被称为“One WayHash”。例如，字符串“unitneurallacriter.grp”是0xA26067F3。strcmp）5returnnHashPos；6else7返回-1；//Errorvalue8}请参阅此，我认为每个人都在思考一个非常严重的问题：“如果哈希表中两个字符串的对应位置相同呢？然而，暴雪程序员使用的方法是一种更复杂的方法。现在回到数据结构，暴雪的哈希表不使用链接列表，而是使用“转发”“方法来解决问题。请查看此算法：1intGetHashTablePos2｛3consintHASH_OFFSET=0，HASH_A=1，HASH_B=2；4intnHash=HashString；5intnHashA=HashString，6intnHashB=HashString；7intnHashStart=nHash%nTableSize，nHashPos=nHashStart；8while9｛10if11returnnHashPos；12else13nHashPos=%nTableSize；14if15break；16｝17return-1；//错误值18｝1。”。计算字符串2的三个哈希值。看看哈希表3中的这个位置。哈希表中的此位置是否为空？
暴雪公司有个经典的字符串的hash公式
先提一个简单的问题，假如有一个庞大的字符串数组，然后给你一个单独的字符串，让你从这个数组中查找是否有这个字符串并找到它，你会怎么做？
有一个方法最简单，老老实实从头查到尾，一个一个比较，直到找到为止，我想只要学过程序设计的人都能把这样一个程序作出来，但要是有程序员把这样的程序交给用户，我只能用无语来评价，或许它真的能工作，但也只能如此了。
最合适的算法自然是使用HashTable（哈希表），先介绍介绍其中的基本知识，所谓Hash，一般是一个整数，通过某种算法，可以把一个字符串"压缩" 成一个整数，这个数称为Hash，当然，无论如何，一个32位整数是无法对应回一个字符串的，但在程序中，两个字符串计算出的Hash值相等的可能非常小，下面看看在MPQ中的Hash算法
1 unsigned long HashString(char *lpszFileName, unsigned long dwHashType) 2 { 3 unsigned char *key = (unsigned char *)lpszFileName; 4 unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE; 5 int ch; 6 while(*key != 0) 7 { 8 ch = toupper(*key++ ); 9 seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2); 10 seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3; 11 } 12 return seed1; 13 }
Blizzard的这个算法是非常高效的，被称为"One-Way Hash"，举个例子，字符串"unitneutralacritter.grp"通过这个算法得到的结果是0xA26067F3。
是不是把第一个算法改进一下，改成逐个比较字符串的Hash值就可以了呢，答案是，远远不够，要想得到最快的算法，就不能进行逐个的比较，通常是构造一个哈希表(Hash Table)来解决问题，哈希表是一个大数组，这个数组的容量根据程序的要求来定义，例如1024，每一个Hash值通过取模运算 (mod)对应到数组中的一个位置，这样，只要比较这个字符串的哈希值对应的位置又没有被占用，就可以得到最后的结果了，想想这是什么速度？是的，是最快的O(1)，现在仔细看看这个算法吧
1 int GetHashTablePos(char *lpszString, SOMESTRUCTURE *lpTable, int nTableSize) 2 { 3 int nHash = HashString(lpszString), nHashPos = nHash % nTableSize; 4 if (lpTable[nHashPos].bExists && !strcmp(lpTable[nHashPos].pString, lpszString)) 5 return nHashPos; 6 else 7 return -1; //Error value 8 }
看到此，我想大家都在想一个很严重的问题："假如两个字符串在哈希表中对应的位置相同怎么办？",究竟一个数组容量是有限的，这种可能性很大。解决该问题的方法很多，我首先想到的就是用"链表",感谢大学里学的数据结构教会了这个百试百灵的法宝，我碰到的很多算法都可以转化成链表来解决，只要在哈希表的每个入口挂一个链表，保存所有对应的字符串就OK了。
事情到此似乎有了完美的结局，假如是把问题独自交给我解决，此时我可能就要开始定义数据结构然后写代码了。然而Blizzard的程序员使用的方法则是更精妙的方法。基本原理就是：他们在哈希表中不是用一个哈希值而是用三个哈希值来校验字符串。
中国有句古话"再一再二不能再三再四"，看来Blizzard也深得此话的精髓，假如说两个不同的字符串经过一个哈希算法得到的入口点一致有可能，但用三个不同的哈希算法算出的入口点都一致，那几乎可以肯定是不可能的事了，这个几率是1:18889465931478580854784，大概是10的 22.3次方分之一，对一个游戏程序来说足够安全了。
现在再回到数据结构上，Blizzard使用的哈希表没有使用链表，而采用"顺延"的方式来解决问题，看看这个算法：
1 int GetHashTablePos(char *lpszString, MPQHASHTABLE *lpTable, int nTableSize) 2 { 3 const int HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2; 4 int nHash = HashString(lpszString, HASH_OFFSET); 5 int nHashA = HashString(lpszString, HASH_A); 6 int nHashB = HashString(lpszString, HASH_B); 7 int nHashStart = nHash % nTableSize, nHashPos = nHashStart; 8 while (lpTable[nHashPos].bExists) 9 { 10 if (lpTable[nHashPos].nHashA == nHashA && lpTable[nHashPos].nHashB == nHashB) 11 return nHashPos; 12 else 13 nHashPos = (nHashPos + 1) % nTableSize; 14 if (nHashPos == nHashStart) 15 break; 16 } 17 return -1; //Error value 18 }
1. 计算出字符串的三个哈希值（一个用来确定位置，另外两个用来校验)
2. 察看哈希表中的这个位置
3. 哈希表中这个位置为空吗？假如为空，则肯定该字符串不存在，返回
4. 假如存在，则检查其他两个哈希值是否也匹配，假如匹配，则表示找到了该字符串，返回
5. 移到下一个位置，假如已经越界，则表示没有找到，返回
6. 看看是不是又回到了原来的位置，假如是，则返回没找到
7. 回到3
怎么样，很简单的算法吧，但确实是天才的idea, 其实最优秀的算法往往是简单有效的算法。
附上完整的算法代码：
1 /*********************************StringHash.h*********************************/ 2 3 #pragma once 4 5 #define MAXTABLELEN 1024 // 默认哈希索引表大小 6 ////////////////////////////////////////////////////////////////////////// 7 // 哈希索引表定义 8 typedef struct _HASHTABLE 9 { 10 long nHashA; 11 long nHashB; 12 bool bExists; 13 }HASHTABLE, *PHASHTABLE ; 14 15 class StringHash 16 { 17 public: 18 StringHash(const long nTableLength = MAXTABLELEN); 19 ~StringHash(void); 20 private: 21 unsigned long cryptTable[0x500]; 22 unsigned long m_tablelength; // 哈希索引表长度 23 HASHTABLE *m_HashIndexTable; 24 private: 25 void InitCryptTable(); // 对哈希索引表预处理 26 unsigned long HashString(const string& lpszString, unsigned long dwHashType); // 求取哈希值 27 public: 28 bool Hash(string url); 29 unsigned long Hashed(string url); // 检测url是否被hash过 30 }; 31 32 33 34 /*********************************StringHash.cpp*********************************/ 35 36 #include "StdAfx.h" 37 #include "StringHash.h" 38 39 StringHash::StringHash(const long nTableLength /*= MAXTABLELEN*/) 40 { 41 InitCryptTable(); 42 m_tablelength = nTableLength; 43 //初始化hash表 44 m_HashIndexTable = new HASHTABLE[nTableLength]; 45 for ( int i = 0; i < nTableLength; i++ ) 46 { 47 m_HashIndexTable[i].nHashA = -1; 48 m_HashIndexTable[i].nHashB = -1; 49 m_HashIndexTable[i].bExists = false; 50 } 51 } 52 53 StringHash::~StringHash(void) 54 { 55 //清理内存 56 if ( NULL != m_HashIndexTable ) 57 { 58 delete []m_HashIndexTable; 59 m_HashIndexTable = NULL; 60 m_tablelength = 0; 61 } 62 } 63 64 /************************************************************************/ 65 /*函数名：InitCryptTable 66 /*功 能：对哈希索引表预处理 67 /*返回值：无 68 /************************************************************************/ 69 void StringHash::InitCryptTable() 70 { 71 unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i; 72 73 for( index1 = 0; index1 < 0x100; index1++ ) 74 { 75 for( index2 = index1, i = 0; i < 5; i++, index2 += 0x100 ) 76 { 77 unsigned long temp1, temp2; 78 seed = (seed * 125 + 3) % 0x2AAAAB; 79 temp1 = (seed & 0xFFFF) << 0x10; 80 seed = (seed * 125 + 3) % 0x2AAAAB; 81 temp2 = (seed & 0xFFFF); 82 cryptTable[index2] = ( temp1 | temp2 ); 83 } 84 } 85 } 86 87 /************************************************************************/ 88 /*函数名：HashString 89 /*功 能：求取哈希值 90 /*返回值：返回hash值 91 /************************************************************************/ 92 unsigned long StringHash::HashString(const string& lpszString, unsigned long dwHashType) 93 { 94 unsigned char *key = (unsigned char *)(const_cast<char*>(lpszString.c_str())); 95 unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE; 96 int ch; 97 98 while(*key != 0) 99 { 100 ch = toupper(*key++); 101 102 seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2); 103 seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3; 104 } 105 return seed1; 106 } 107 108 /************************************************************************/ 109 /*函数名：Hashed 110 /*功 能：检测一个字符串是否被hash过 111 /*返回值：如果存在，返回位置；否则，返回-1 112 /************************************************************************/ 113 unsigned long StringHash::Hashed(string lpszString) 114 115 { 116 const unsigned long HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2; 117 //不同的字符串三次hash还会碰撞的几率无限接近于不可能 118 unsigned long nHash = HashString(lpszString, HASH_OFFSET); 119 unsigned long nHashA = HashString(lpszString, HASH_A); 120 unsigned long nHashB = HashString(lpszString, HASH_B); 121 unsigned long nHashStart = nHash % m_tablelength, 122 nHashPos = nHashStart; 123 124 while ( m_HashIndexTable[nHashPos].bExists) 125 { 126 if (m_HashIndexTable[nHashPos].nHashA == nHashA && m_HashIndexTable[nHashPos].nHashB == nHashB) 127 return nHashPos; 128 else 129 nHashPos = (nHashPos + 1) % m_tablelength; 130 131 if (nHashPos == nHashStart) 132 break; 133 } 134 135 return -1; //没有找到 136 } 137 138 /************************************************************************/ 139 /*函数名：Hash 140 /*功 能：hash一个字符串 141 /*返回值：成功，返回true；失败，返回false 142 /************************************************************************/ 143 bool StringHash::Hash(string lpszString) 144 { 145 const unsigned long HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2; 146 unsigned long nHash = HashString(lpszString, HASH_OFFSET); 147 unsigned long nHashA = HashString(lpszString, HASH_A); 148 unsigned long nHashB = HashString(lpszString, HASH_B); 149 unsigned long nHashStart = nHash % m_tablelength, 150 nHashPos = nHashStart; 151 152 while ( m_HashIndexTable[nHashPos].bExists) 153 { 154 nHashPos = (nHashPos + 1) % m_tablelength; 155 if (nHashPos == nHashStart) //一个轮回 156 { 157 //hash表中没有空余的位置了,无法完成hash 158 return false; 159 } 160 } 161 m_HashIndexTable[nHashPos].bExists = true; 162 m_HashIndexTable[nHashPos].nHashA = nHashA; 163 m_HashIndexTable[nHashPos].nHashB = nHashB; 164 165 return true; 166 }