各种字符串Hash函数比较

哈希表是项目中最常用的的数据结构,如数据库索引、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);

}

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180209B0532E00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动