文章目录
一、性能分析二、各类hash函数代码
一、性能分析
常用的字符串Hash函数还有ELFHash,APHash等等,都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数,这些函数几乎不可能找到碰撞。
常用字符串哈希函数有BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等等。对于以上几种哈希函数,进行了一个小小的评测。 其中数据1为100000个字母和数字组成的随机串哈希冲突个数。 数据2为100000个有意义的英文句子哈希冲突个数。 数据3为数据1的哈希值与1000003(大素数)求模后存储到线性表中冲突的个数。 数据4为数据1的哈希值与10000019(更大素数)求模后存储到线性表中冲突的个数。
经过比较,得出以上平均得分。平均数为平方平均数。可以发现,BKDRHash无论是在实际效果还是编码实现中,效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差,但得分相似,其算法本质是相似的。 在信息修竞赛中,要本着易于编码调试的原则,个人认为BKDRHash是最适合记忆和使用的。
二、各类hash函数代码
unsigned int SDBMHash(char *str
)
{
unsigned int hash
= 0;
while (*str
)
{
hash
= (*str
++) + (hash
<< 6) + (hash
<< 16) - hash
;
}
return (hash
& 0x7FFFFFFF);
}
unsigned int RSHash(char *str
)
{
unsigned int b
= 378551;
unsigned int a
= 63689;
unsigned int hash
= 0;
while (*str
)
{
hash
= hash
* a
+ (*str
++);
a
*= b
;
}
return (hash
& 0x7FFFFFFF);
}
unsigned int JSHash(char *str
)
{
unsigned int hash
= 1315423911;
while (*str
)
{
hash
^= ((hash
<< 5) + (*str
++) + (hash
>> 2));
}
return (hash
& 0x7FFFFFFF);
}
unsigned int PJWHash(char *str
)
{
unsigned int BitsInUnignedInt
= (unsigned int)(sizeof(unsigned int) * 8);
unsigned int ThreeQuarters
= (unsigned int)((BitsInUnignedInt
* 3) / 4);
unsigned int OneEighth
= (unsigned int)(BitsInUnignedInt
/ 8);
unsigned int HighBits
= (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt
- OneEighth
);
unsigned int hash
= 0;
unsigned int test
= 0;
while (*str
)
{
hash
= (hash
<< OneEighth
) + (*str
++);
if ((test
= hash
& HighBits
) != 0)
{
hash
= ((hash
^ (test
>> ThreeQuarters
)) & (~HighBits
));
}
}
return (hash
& 0x7FFFFFFF);
}
unsigned int ELFHash(char *str
)
{
unsigned int hash
= 0;
unsigned int x
= 0;
while (*str
)
{
hash
= (hash
<< 4) + (*str
++);
if ((x
= hash
& 0xF0000000L) != 0)
{
hash
^= (x
>> 24);
hash
&= ~x
;
}
}
return (hash
& 0x7FFFFFFF);
}
unsigned int BKDRHash(char *str
)
{
unsigned int seed
= 131;
unsigned int hash
= 0;
while (*str
)
{
hash
= hash
* seed
+ (*str
++);
}
return (hash
& 0x7FFFFFFF);
}
unsigned int DJBHash(char *str
)
{
unsigned int hash
= 5381;
while (*str
)
{
hash
+= (hash
<< 5) + (*str
++);
}
return (hash
& 0x7FFFFFFF);
}
unsigned int APHash(char *str
)
{
unsigned int hash
= 0;
int i
;
for (i
=0; *str
; i
++)
{
if ((i
& 1) == 0)
{
hash
^= ((hash
<< 7) ^ (*str
++) ^ (hash
>> 3));
}
else
{
hash
^= (~((hash
<< 11) ^ (*str
++) ^ (hash
>> 5)));
}
}
return (hash
& 0x7FFFFFFF);
}
关注公众号"小败日记",搬砖过程遇到的问题,大家一起探讨,资源共享