Author: FreeKnight
Hash表本身是很容易理解的，它本身是一个固定大小的数组，数组的每个元素是一个链表的头指针。
我们对需要插入的元素，根据Hash算法算出一个对应的key，然后填充到对应的链表内做为尾节点。
遍历的时候，我们先对需查找的元素计算其Key，直接通过数组找到其所在链表，此时仅对其所在链表进行遍历即可。
但是，我们可以发现Hash表有以下问题。
1：若Hash算法得到的值范围很大，那么，表数组会比较大，是无谓的内存浪费。
2：若Hash算法得到的值范围很小，Key重复就会很高，遍历时查找的链表节点就太多，无法体现效率。
所以合适的Hash算法是Hash表性能的关键。
根据各种数学家的检测（这里，俺不管为啥……）哈希表尺寸最好使用质数，而实际上Hash表若使用动态的HashKey则会更加合适。我们从MPQ Hash里得到这些HashKey。
17，37,79,163,331,673,1361,2729,5471,10949,21911,43853,87719,175447,350899,701819,1403641,2807303,5614657,11229331,22458671,44917381,89834777,179669557,359339171,718678369,1437356741,2147483647。
当我们的元素数量为哈希表数组2倍时，我们就扩大一次哈希Key即可实现动态Hash，适用范围更大。
哈希算法有几个比较经典的。因为时间关系不再解释和说明。
//=====================================================
简单的比较均匀分布的Hash：
//=====================================================
unsigned long getHashIndex( const char *key, int nTableLength )
{
unsigned long nHash = 0;
while (*key)
{
nHash = (nHash<<5) + nHash + *key++;
}
return ( nHash % nTableLength );
}
//=====================================================
略复杂的MPQ哈希:
//=====================================================
以下的函数生成一个长度为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 );
}
}
}
//=====================================================
Blizzard的"One-Way Hash"算法,高效经典。
//=====================================================
unsigned long HashString( char *lpszFileName, unsigned long dwHashType )
{
unsigned char *key = (unsigned char *)lpszFileName;
unsigned long seed1 = 0x7FED7FED;
unsigned long seed2 = 0xEEEEEEEE;
int ch;
while( *key != 0 )
{
ch = toupper(*key++);
seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);
seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;
}
}
看代码时候要定时……OMG，又3点半