哈希表是项目中最常用的的数据结构,如数据库索引、map、缓存等地方。关于哈希表这种数据结构,一个最关键的问题是如何设计一个优秀的哈希函数,下文是一些经典的字符串哈希函数的性能测试比较及其相应的C语言实现。大家可以在项目中根据实际场景选择合适的直接使用。
hash函数的性能测试比较
常用字符串哈希函数有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效果最差,但得分相似,其算法本质是相似的。
几种经典hash函数的实现
下面给出各种哈希函数的C语言程序实现代码,避免大家在项目中重复造轮子。
// BKDR Hash Function
unsignedintBKDRHash(char*str)
{ unsignedintseed=131;// 31 131 1313 13131 131313 etc..unsignedinthash=;
while(*str) { hash=hash*seed+(*str++); }
return(hash&0x7FFFFFFF);
}
//SDBMHash
unsignedintSDBMHash(char*str)
{ unsignedinthash=;
while(*str) {
// equivalent to: hash = 65599*hash + (*str++);hash=(*str++)+(hash
return(hash&0x7FFFFFFF);
}
// RS Hash Function
unsignedintRSHash(char*str)
{ unsignedintb=378551; unsignedinta=63689; unsignedinthash=;
while(*str) { hash=hash*a+(*str++); a*=b; }
return(hash&0x7FFFFFFF);
}
// ELF Hash Function
unsignedintELFHash(char*str)
{ unsignedinthash=; unsignedintx=;
while(*str) { hash=(hash
if((x=hash&0xF0000000L)!=) { hash^=(x>>24); hash&=~x; } }
return(hash&0x7FFFFFFF);
}
// DJB Hash Function
unsignedintDJBHash(char*str)
{ unsignedinthash=5381;
while(*str) { hash+=(hash
return(hash&0x7FFFFFFF);
}
领取专属 10元无门槛券
私享最新 技术干货