Hash算法说明

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点半。