常用的字符串Hash函數(shù)還有ELFHash，APHash等等，都是十分簡(jiǎn)單有效的方法。這些函數(shù)使用位運(yùn)算使得每一個(gè)字符都對(duì)最后的函數(shù)值產(chǎn)生影響。另外還有以MD5和SHA1為代表的雜湊函數(shù)，這些函數(shù)幾乎不可能找到碰撞。
常用字符串哈希函數(shù)有BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等。對(duì)于以上幾種哈希函數(shù)，我對(duì)其進(jìn)行了一個(gè)小小的評(píng)測(cè)。
| Hash函數(shù) | 數(shù)據(jù)1 | 數(shù)據(jù)2 | 數(shù)據(jù)3 | 數(shù)據(jù)4 | 數(shù)據(jù)1得分 | 數(shù)據(jù)2得分 | 數(shù)據(jù)3得分 | 數(shù)據(jù)4得分 | 平均分 |
| BKDRHash | 2 | 0 | 4774 | 481 | 96.55 | 100 | 90.95 | 82.05 | 92.64 |
| APHash | 2 | 3 | 4754 | 493 | 96.55 | 88.46 | 100 | 51.28 | 86.28 |
| DJBHash | 2 | 2 | 4975 | 474 | 96.55 | 92.31 | 0 | 100 | 83.43 |
| JSHash | 1 | 4 | 4761 | 506 | 100 | 84.62 | 96.83 | 17.95 | 81.94 |
| RSHash | 1 | 0 | 4861 | 505 | 100 | 100 | 51.58 | 20.51 | 75.96 |
| SDBMHash | 3 | 2 | 4849 | 504 | 93.1 | 92.31 | 57.01 | 23.08 | 72.41 |
| PJWHash | 30 | 26 | 4878 | 513 | 0 | 0 | 43.89 | 0 | 21.95 |
| ELFHash | 30 | 26 | 4878 | 513 | 0 | 0 | 43.89 | 0 | 21.95 |
其中數(shù)據(jù)1為100000個(gè)字母和數(shù)字組成的隨機(jī)串哈希沖突個(gè)數(shù)。數(shù)據(jù)2為100000個(gè)有意義的英文句子哈希沖突個(gè)數(shù)。數(shù)據(jù)3為數(shù)據(jù)1的哈希值與1000003(大素?cái)?shù))求模后存儲(chǔ)到線(xiàn)性表中沖突的個(gè)數(shù)。數(shù)據(jù)4為數(shù)據(jù)1的哈希值與10000019(更大素?cái)?shù))求模后存儲(chǔ)到線(xiàn)性表中沖突的個(gè)數(shù)。
經(jīng)過(guò)比較，得出以上平均得分。平均數(shù)為平方平均數(shù)。可以發(fā)現(xiàn)，BKDRHash無(wú)論是在實(shí)際效果還是編碼實(shí)現(xiàn)中，效果都是最突出的。APHash也是較為優(yōu)秀的算法。DJBHash,JSHash,RSHash與SDBMHash各有千秋。PJWHash與ELFHash效果最差，但得分相似，其算法本質(zhì)是相似的。
在信息修競(jìng)賽中，要本著易于編碼調(diào)試的原則，個(gè)人認(rèn)為BKDRHash是最適合記憶和使用的。
BYVoid原創(chuàng)，歡迎建議、交流、批評(píng)和指正。
附：各種哈希函數(shù)的C語(yǔ)言程序代碼unsigned int SDBMHash(char *str)
{
unsigned int hash = 0;
while (*str)
{
// equivalent to: hash = 65599*hash + (*str++);
hash = (*str++) + (hash << 6) + (hash << 16) - hash;
}
return (hash & 0x7FFFFFFF);
}
// RS Hash Function
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);
}
// JS Hash Function
unsigned int JSHash(char *str)
{
unsigned int hash = 1315423911;
while (*str)
{
hash ^= ((hash << 5) + (*str++) + (hash >> 2));
}
return (hash & 0x7FFFFFFF);
}
// P. J. Weinberger Hash Function
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);
}
// ELF Hash Function
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);
}
// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0;
while (*str)
{
hash = hash * seed + (*str++);
}
return (hash & 0x7FFFFFFF);
}
// DJB Hash Function
unsigned int DJBHash(char *str)
{
unsigned int hash = 5381;
while (*str)
{
hash += (hash << 5) + (*str++);
}
return (hash & 0x7FFFFFFF);
}
// AP Hash Function
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);
}