最近学习了hash表,还去网上找了些资料来看。网上比较推崇的一个hash运用就是mpq,暴雪公司的一个算法。具体请看下面链接:
十一、从头到尾彻底解析Hash表算法
MPQ技术内幕
之前,研究了这个hash用法,有点认识;今天,照着抄写了一边,发现了另外的一些认识,主要是针对下面的这个hash函数:
下面这个函数是初始化hash表cryptTable:
void prepareCryptTable() { unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i; //分成5行*100列,一列一列进行初始化;在代码中,cryptTable初始化大小为0x500. 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 ); } } }
下面这个函数是通过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; } return seed1; }
如代码中表红的,暴雪的hash计算,首先是初始化了表 cryptTable;然后在这个函数中引用了这张表中的数据来进行hash计算。
其中,ch是字符值,最大为一个字节;dwHasType左移8位,那么就是第二字节(即填充高8bit)。那么,就是说cryptTable的大小是两个字节大小,最大为unsigned short(表再大,取不到这个这个位置的值,没有意义)。那么,dwHasType取值也要注意了,一定不能比cryptTable大小的高8bit值大(或者说,dwHasType<<8 超出cryptTable范围)