002514 宝馨科技股票:转载：测试了一下hash函数的性 — Windows Live

今天对3个hash函数进行了一些测试，把结果贴上，以便日后查看：
测试的3个函数分别为Paul Hsieh的SuperFastHash，Bob JenKin的hash函数和暴雪公司用于MPQ包编码的hash函数（函数见附）。这几个hash都是可以用于构造hash表的字符串hash函数。
1。速度性能：
测试环境为P4 3.20GHz双核CPU ＋ 512内存，分别让以上3个函数对256 byte大小的数据运算hash值5百万次，以下是3个函数的平均执行时间
SuperFastHash   ：1.0310s （Run 5000000 times）
BobJenKin'sHash ：1.2500s （Run 5000000 times）
BLZ'MPQ Hash    ：2.6870s （Run 5000000 times）
为了对比，用一些常用的hash运算在相同条件下的结果：
CRC32           ：3.7340s
OneAtATimeHash  ：5.3440s
AlphaNumHash    ：4.3750s
FNV Hash        ：4.4680s
从结果来看，快速hash的确速度是最快的。暴雪的MPQ hash稍慢，但和常用的hash函数比，这3个函数还是很快的。
2。hash值重复率
使用了46710个不同字符串的字典，对hash函数的值做了简单的统计：
暴雪hash：
hash值重复发生次数为：1
桶数量：2719
最大的桶大小为：33
最小的桶大小为：5
理论平均桶大小为：17.1162
-----------------------------
被分配到0个元素的桶个数是： 0
被分配到1个元素的桶个数是： 0
被分配到2个元素的桶个数是： 0
被分配到3个元素的桶个数是： 0
被分配到4个元素的桶个数是： 0
被分配到5个元素的桶个数是： 1
被分配到6个元素的桶个数是： 4
被分配到7个元素的桶个数是： 15
被分配到8个元素的桶个数是： 14
被分配到9个元素的桶个数是： 33
被分配到10个元素的桶个数是： 67
被分配到11个元素的桶个数是： 89
被分配到12个元素的桶个数是： 139
被分配到13个元素的桶个数是： 162
被分配到14个元素的桶个数是： 222
被分配到15个元素的桶个数是： 286
被分配到16个元素的桶个数是： 240
被分配到17个元素的桶个数是： 236
被分配到18个元素的桶个数是： 240
被分配到19个元素的桶个数是： 208
被分配到20个元素的桶个数是： 189
被分配到21个元素的桶个数是： 167
被分配到22个元素的桶个数是： 133
被分配到23个元素的桶个数是： 96
被分配到24个元素的桶个数是： 69
被分配到25个元素的桶个数是： 47
被分配到26个元素的桶个数是： 27
被分配到27个元素的桶个数是： 20
被分配到28个元素的桶个数是： 10
被分配到29个元素的桶个数是： 7
被分配到30个元素的桶个数是： 5
被分配到31个元素的桶个数是： 2
被分配到32个元素的桶个数是： 0
被分配到33个元素的桶个数是： 1
被分配到34个元素的桶个数是： 0
被分配到35个元素的桶个数是： 0
被分配到36个元素的桶个数是： 0
被分配到37个元素的桶个数是： 0
被分配到38个元素的桶个数是： 0
被分配到39个元素的桶个数是： 0
被分配到40个元素的桶个数是： 0
Bob JenKin Hash：
hash值重复发生次数为：1
桶数量：2719
最大的桶大小为：33
最小的桶大小为：5
理论平均桶大小为：17.1162
-----------------------------
被分配到0个元素的桶个数是： 0
被分配到1个元素的桶个数是： 0
被分配到2个元素的桶个数是： 0
被分配到3个元素的桶个数是： 0
被分配到4个元素的桶个数是： 0
被分配到5个元素的桶个数是： 2
被分配到6个元素的桶个数是： 3
被分配到7个元素的桶个数是： 3
被分配到8个元素的桶个数是： 18
被分配到9个元素的桶个数是： 29
被分配到10个元素的桶个数是： 55
被分配到11个元素的桶个数是： 91
被分配到12个元素的桶个数是： 133
被分配到13个元素的桶个数是： 174
被分配到14个元素的桶个数是： 220
被分配到15个元素的桶个数是： 266
被分配到16个元素的桶个数是： 265
被分配到17个元素的桶个数是： 231
被分配到18个元素的桶个数是： 254
被分配到19个元素的桶个数是： 268
被分配到20个元素的桶个数是： 199
被分配到21个元素的桶个数是： 155
被分配到22个元素的桶个数是： 95
被分配到23个元素的桶个数是： 82
被分配到24个元素的桶个数是： 69
被分配到25个元素的桶个数是： 49
被分配到26个元素的桶个数是： 30
被分配到27个元素的桶个数是： 17
被分配到28个元素的桶个数是： 7
被分配到29个元素的桶个数是： 7
被分配到30个元素的桶个数是： 4
被分配到31个元素的桶个数是： 1
被分配到32个元素的桶个数是： 1
被分配到33个元素的桶个数是： 1
被分配到34个元素的桶个数是： 0
被分配到35个元素的桶个数是： 0
被分配到36个元素的桶个数是： 0
被分配到37个元素的桶个数是： 0
被分配到38个元素的桶个数是： 0
被分配到39个元素的桶个数是： 0
被分配到40个元素的桶个数是： 0
SuperFastHash：
hash值碰撞发生次数为：238
桶数量：2719
最大的桶大小为：32
最小的桶大小为：5
理论平均桶大小为：17.1162
-----------------------------
被分配到0个元素的桶个数是： 0
被分配到1个元素的桶个数是： 0
被分配到2个元素的桶个数是： 0
被分配到3个元素的桶个数是： 0
被分配到4个元素的桶个数是： 0
被分配到5个元素的桶个数是： 1
被分配到6个元素的桶个数是： 2
被分配到7个元素的桶个数是： 8
被分配到8个元素的桶个数是： 16
被分配到9个元素的桶个数是： 29
被分配到10个元素的桶个数是： 59
被分配到11个元素的桶个数是： 99
被分配到12个元素的桶个数是： 138
被分配到13个元素的桶个数是： 197
被分配到14个元素的桶个数是： 217
被分配到15个元素的桶个数是： 241
被分配到16个元素的桶个数是： 247
被分配到17个元素的桶个数是： 257
被分配到18个元素的桶个数是： 256
被分配到19个元素的桶个数是： 213
被分配到20个元素的桶个数是： 202
被分配到21个元素的桶个数是： 149
被分配到22个元素的桶个数是： 113
被分配到23个元素的桶个数是： 92
被分配到24个元素的桶个数是： 66
被分配到25个元素的桶个数是： 52
被分配到26个元素的桶个数是： 29
被分配到27个元素的桶个数是： 18
被分配到28个元素的桶个数是： 9
被分配到29个元素的桶个数是： 4
被分配到30个元素的桶个数是： 7
被分配到31个元素的桶个数是： 6
被分配到32个元素的桶个数是： 2
被分配到33个元素的桶个数是： 0
被分配到34个元素的桶个数是： 0
被分配到35个元素的桶个数是： 0
被分配到36个元素的桶个数是： 0
被分配到37个元素的桶个数是： 0
被分配到38个元素的桶个数是： 0
被分配到39个元素的桶个数是： 0
被分配到40个元素的桶个数是： 0
以上3个测试的结果用Excel制表：

从结果来看SuperFastHash虽然运算速度是最快的，但是他的重复率真的是惨不忍睹。而分配的均匀性，3个函数相差不多。在实际的hash表应用中，由于hash都要mod表大小以映射到表上，因此虽然SuperFastHash的重复率很高，但是经mod表大小后实际的分布也和其他2种hash函数相差无几，而其高速度的优势反使之性能略高。所以在用作字符串hash表分配时 SuperFastHash是不错的选择。
而暴雪的MPQ hash不仅要进行字符串的分配，还要作为文件名的代替品进行文件标识，所以对hash函数的重复率要求尽可能的小。而这个hash也恰恰满足这种要求（46710个字符串只有1次重复），暴雪在MPQ文件中用2个这种hash的值作为文件名识别，发生值重复的概率几乎可以忽略。
附：（部分代码）
1。暴雪MPQ hash函数：
使用前要先调用函数prepareCryptTable()初始化编码表。
DWORD cryptTable[0x500];//编码表
void prepareCryptTable()
{
DWORD seed = 0x00100001, index1 = 0, index2 = 0, i;
for( index1 = 0; index1<0x100; index1++ )
{
for( index2 = index1, i = 0; i < 5; i++, index2 += 0x100 )
{
DWORD temp1, temp2;
seed = (seed * 125 + 3) % 0x2AAAAB;
temp1 = (seed & 0xFFFF) << 0x10;
seed = (seed * 125 + 3) % 0x2AAAAB;
temp2 = (seed & 0xFFFF);
cryptTable[index2] = ( temp1 | temp2 );
}
}
}
DWORD HashString( const char *lpszName, DWORD dwHashType, int len )
{
unsigned char *key  = (unsigned char *)lpszName;
DWORD seed1 = 0x7FED7FED;
DWORD seed2 = 0xEEEEEEEE;
int ch;
for(;len > 0; len--)
{
ch = *key++;
seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);
seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;
}
return seed1;
}
2。Bob JenKin Hash：
#define get32bits(d) (*((const uint32_t *) (d)))
#define mix(a,b,c) \
{ \
a -= b; a -= c; a ^= (c>>13); \
b -= c; b -= a; b ^= (a<<8); \
c -= a; c -= b; c ^= (b>>13); \
a -= b; a -= c; a ^= (c>>12);  \
b -= c; b -= a; b ^= (a<<16); \
c -= a; c -= b; c ^= (b>>5); \
a -= b; a -= c; a ^= (c>>3);  \
b -= c; b -= a; b ^= (a<<10); \
c -= a; c -= b; c ^= (b>>15); \
}
static uint32_t hashBobJenkinsUpdate(const char * k, int length, unsigned int initval)
{
register ub4 a,b,c,len;
len = length;
a = b = 0x9e3779b9;
c = initval;
while (len >= 12)
{
a += get32bits (k);
b += get32bits (k+4);
c += get32bits (k+8);
mix(a,b,c);
k += 12; len -= 12;
}
c += length;
switch(len)
{
case 11: c+=((ub4)k[10]<<24);
case 10: c+=((ub4)k[9]<<16);
case 9 : c+=((ub4)k[8]<<8);
case 8 : b+=((ub4)k[7]<<24);
case 7 : b+=((ub4)k[6]<<16);
case 6 : b+=((ub4)k[5]<<8);
case 5 : b+=k[4];
case 4 : a+=((ub4)k[3]<<24);
case 3 : a+=((ub4)k[2]<<16);
case 2 : a+=((ub4)k[1]<<8);
case 1 : a+=k[0];
/* case 0: nothing left to add */
}
mix(a,b,c);
return c;
}
3。SuperFastHash：
#define get16bits(d) (*((const UINT16 *) (d)))
DWORD SuperFastHash (const char * data, int len)
{
UINT32 hash = len, tmp;
INT32 rem;
if (len <= 0 || data == NULL) return 0;
rem = len & 3;
len >>= 2;
/* Main loop */
for (;len > 0; len--) {
hash  += get16bits (data);
tmp    = (get16bits (data+2) << 11) ^ hash;
hash   = (hash << 16) ^ tmp;
data  += 2*sizeof (UINT16);
hash  += hash >> 11;
}
/* Handle end cases */
switch (rem) {
case 3: hash += get16bits (data);
hash ^= hash << 16;
hash ^= data[sizeof (UINT16)] << 18;
hash += hash >> 11;
break;
case 2: hash += get16bits (data);
hash ^= hash << 11;
hash += hash >> 17;
break;
case 1: hash += *data;
hash ^= hash << 10;
hash += hash >> 1;
}
/* Force "avalanching" of final 127 bits */
hash ^= hash << 3;
hash += hash >> 5;
hash ^= hash << 4;
hash += hash >> 17;
hash ^= hash << 25;
hash += hash >> 6;
return hash;
}