各种字符串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);

}