作者：BYVoid 
來源：https://www.byvoid.com/zhs/blog/string-hash-compare


哈希表是項目中最常用的的數據結構，如數據庫索引、map、緩存等地方。關於哈希表這種數據結構，一個最關鍵的問題是如何設計一個優秀的哈希函數，下文是一些經典的字符串哈希函數的性能測試比較及其相應的C語言實現。大家可以在項目中根據實際場景選擇合適的直接使用。

hash函數的性能測試比較

常用字符串哈希函數有BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等。對於以上幾種哈希函數，我對其進行了一個小小的評測。


各種字符串Hash函數比較


其中：

數據1：爲100000個字母和數字組成的隨機串哈希衝突個數。

數據2：爲100000個有意義的英文句子哈希衝突個數。

數據3：爲數據1的哈希值與1000003(大素數)求模後存儲到線性表中衝突的個數。

數據4：爲數據1的哈希值與10000019(更大素數)求模後存儲到線性表中衝突的個數。

經過比較，得出以上平均得分。平均數爲平方平均數。可以發現，BKDRHash無論是在實際效果還是編碼實現中，效果都是最突出的。APHash也是較爲優秀的算法。DJBHash,JSHash,RSHash與SDBMHash各有千秋。PJWHash與ELFHash效果最差，但得分相似，其算法本質是相似的。

幾種經典hash函數的實現

下面給出各種哈希函數的C語言程序實現代碼，避免大家在項目中重複造輪子。

// 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);
}


//SDBMHash
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);
}
// 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);
}


// DJB Hash Function
unsigned int DJBHash(char *str)
{
 unsigned int hash = 5381; 
 
 while (*str)
 {
 hash += (hash << 5) + (*str++);
 } 
 return (hash & 0x7FFFFFFF);
}
相关文章