学步园

string的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;
}

string的获取hash表位置的函数：

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), nHashA = HashString(lpszString, HASH_A), nHashB = HashString(lpszString, HASH_B), 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
}

string加密算法：

void EncryptBlock(void *lpvBlock, int nBlockLen, char *lpszPassword)
{
int nPWLen = strlen(lpszPassword), nCount = 0;
char *lpsPassBuff = (char *)_alloca(nPWLen);

memcpy(lpsPassBuff, lpszPassword, nPWLen);

for (int nChar = 0; nCount < nBlockLen; nCount++)
{
char cPW = lpsPassBuff[nCount];

lpvBlock[nChar] ^= cPW;

lpsPassBuff[nCount] = cPW + 13;

nCount = (nCount + 1) % nPWLen;
}

return;
}

大小为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);
}
}
}

解密算法：

void DecryptBlock(void *block, long length, unsigned long key)
{
unsigned long seed = 0xEEEEEEEE, unsigned long ch;
unsigned long *castBlock = (unsigned long *)block;

// Round to longs
length >>= 2;

while(length-- > 0)
{
seed += stormBuffer[0x400 + (key & 0xFF)];
ch = *castBlock ^ (key + seed);

key = ((~key << 0x15) + 0x11111111) | (key >> 0x0B);
seed = ch + seed + (seed << 5) + 3;
*castBlock++ = ch;
}
}

哈希表的数组是定长的，如果太大，则浪费，如果太小，体现不出效率。合适的数组大小是哈希表的性能的关键。哈希表的尺寸最好是一个质数。当然，根据不同的数据量，会有不同的哈希表的大小。对于数据量时多时少的应用，最好的设计是使用动态可变尺寸的哈希表，那么如果你发现哈希表尺寸太小了，比如其中的元素是哈希表尺寸的2倍时，我们就需要扩大哈希表尺寸，一般是扩大一倍。

下面是哈希表尺寸大小的可能取值：

     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

常用的比较简单的hash函数：

/*key为一个字符串，nTableLength为哈希表的长度
*该函数得到的hash值分布比较均匀*/
unsigned long getHashIndex( const char *key, int nTableLength )
{
    unsigned long nHash = 0;
   
    while (*key)
    {
        nHash = (nHash<<5) + nHash + *key++;
    }
        
    return ( nHash % nTableLength );
}

hash函数的构造方法及冲突解决方法：

http://baike.baidu.com/link?url=jSaI8jmlrhVlWEkNs_HP4VjUsKp_-97tLZp0aTNP_Z7VxppiT0my_kDq71JLeRm5

大神们的hash算法代码：

http://blog.csdn.net/mycomputerxiaomei/article/details/7641221