程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 各種Hash函數沖突率分析

各種Hash函數沖突率分析

編輯：C++入門知識

字符串Hash函數對比
今天根據自己的理解重新整理了一下幾個字符串hash函數，使用了模板，使其支持寬字符串，代碼如下:
[cpp]
/// @brief BKDR Hash Function
/// @detail 本算法由於在Brian Kernighan與Dennis Ritchie的《The C Programming Language》一書被展示而得名，是一種簡單快捷的hash算法，也是Java目前采用的字符串的Hash算法（累乘因子為31）。
template<class T>
size_t BKDRHash(const T *str)
{
    register size_t hash = 0;
    while (size_t ch = (size_t)*str++)
    {
        hash = hash * 131 + ch;   // 也可以乘以31、131、1313、13131、131313..
        // 有人說將乘法分解為位運算及加減法可以提高效率，如將上式表達為：hash = hash << 7 + hash << 1 + hash + ch;
        // 但其實在Intel平台上，CPU內部對二者的處理效率都是差不多的，
        // 我分別進行了100億次的上述兩種運算，發現二者時間差距基本為0（如果是Debug版，分解成位運算後的耗時還要高1/3）；
        // 在ARM這類RISC系統上沒有測試過，由於ARM內部使用Booth's Algorithm來模擬32位整數乘法運算，它的效率與乘數有關：
        // 當乘數8-31位都為1或0時，需要1個時鐘周期
        // 當乘數16-31位都為1或0時，需要2個時鐘周期
        // 當乘數24-31位都為1或0時，需要3個時鐘周期
        // 否則，需要4個時鐘周期
        // 因此，雖然我沒有實際測試，但是我依然認為二者效率上差別不大
    }
    return hash;
}
/// @brief SDBM Hash Function
/// @detail 本算法是由於在開源項目SDBM（一種簡單的數據庫引擎）中被應用而得名，它與BKDRHash思想一致，只是種子不同而已。
template<class T>
size_t SDBMHash(const T *str)
{
    register size_t hash = 0;
    while (size_t ch = (size_t)*str++)
    {
        hash = 65599 * hash + ch;
        //hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;
    }
    return hash;
}
/// @brief RS Hash Function
/// @detail 因Robert Sedgwicks在其《Algorithms in C》一書中展示而得名。
template<class T>
size_t RSHash(const T *str)
{
    register size_t hash = 0;
    size_t magic = 63689;
    while (size_t ch = (size_t)*str++)
    {
        hash = hash * magic + ch;
        magic *= 378551;
    }
    return hash;
}
/// @brief AP Hash Function
/// @detail 由Arash Partow發明的一種hash算法。
template<class T>
size_t APHash(const T *str)
{
    register size_t hash = 0;
    size_t ch;
    for (long i = 0; ch = (size_t)*str++; i++)
    {
        if ((i & 1) == 0)
        {
            hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
        }
        else
        {
            hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
        }
    }
    return hash;
}
/// @brief JS Hash Function
/// 由Justin Sobel發明的一種hash算法。
template<class T>
size_t JSHash(const T *str)
{
    if(!*str)        // 這是由本人添加，以保證空字符串返回哈希值0
        return 0;
    register size_t hash = 1315423911;
    while (size_t ch = (size_t)*str++)
    {
        hash ^= ((hash << 5) + ch + (hash >> 2));
    }
    return hash;
}
/// @brief DEK Function
/// @detail 本算法是由於Donald E. Knuth在《Art Of Computer Programming Volume 3》中展示而得名。
template<class T>
size_t DEKHash(const T* str)
{
    if(!*str)        // 這是由本人添加，以保證空字符串返回哈希值0
        return 0;
    register size_t hash = 1315423911;
    while (size_t ch = (size_t)*str++)
    {
        hash = ((hash << 5) ^ (hash >> 27)) ^ ch;
    }
    return hash;
}
/// @brief FNV Hash Function
/// @detail Unix system系統中使用的一種著名hash算法，後來微軟也在其hash_map中實現。
template<class T>
size_t FNVHash(const T* str)
{
    if(!*str)   // 這是由本人添加，以保證空字符串返回哈希值0
        return 0;
    register size_t hash = 2166136261;
    while (size_t ch = (size_t)*str++)
    {
        hash *= 16777619;
        hash ^= ch;
    }
    return hash;
}
/// @brief DJB Hash Function
/// @detail 由Daniel J. Bernstein教授發明的一種hash算法。
template<class T>
size_t DJBHash(const T *str)
{
    if(!*str)   // 這是由本人添加，以保證空字符串返回哈希值0
        return 0;
    register size_t hash = 5381;
    while (size_t ch = (size_t)*str++)
    {
        hash += (hash << 5) + ch;
    }
    return hash;
}
/// @brief DJB Hash Function 2
/// @detail 由Daniel J. Bernstein 發明的另一種hash算法。
template<class T>
size_t DJB2Hash(const T *str)
{
    if(!*str)   // 這是由本人添加，以保證空字符串返回哈希值0
        return 0;
    register size_t hash = 5381;
    while (size_t ch = (size_t)*str++)
    {
        hash = hash * 33 ^ ch;
    }
    return hash;
}
/// @brief PJW Hash Function
/// @detail 本算法是基於AT&T貝爾實驗室的Peter J. Weinberger的論文而發明的一種hash算法。
template<class T>
size_t PJWHash(const T *str)
{
    static const size_t TotalBits       = sizeof(size_t) * 8;
    static const size_t ThreeQuarters   = (TotalBits * 3) / 4;
    static const size_t OneEighth       = TotalBits / 8;
    static const size_t HighBits        = ((size_t)-1) << (TotalBits - OneEighth);

    register size_t hash = 0;
    size_t magic = 0;
    while (size_t ch = (size_t)*str++)
    {
        hash = (hash << OneEighth) + ch;
        if ((magic = hash & HighBits) != 0)
        {
            hash = ((hash ^ (magic >> ThreeQuarters)) & (~HighBits));
        }
    }
    return hash;
}
/// @brief ELF Hash Function
/// @detail 由於在Unix的Extended Library Function被附帶而得名的一種hash算法，它其實就是PJW Hash的變形。
template<class T>
size_t ELFHash(const T *str)
{
    static const size_t TotalBits       = sizeof(size_t) * 8;
    static const size_t ThreeQuarters   = (TotalBits * 3) / 4;
    static const size_t OneEighth       = TotalBits / 8;
    static const size_t HighBits        = ((size_t)-1) << (TotalBits - OneEighth);
    register size_t hash = 0;
    size_t magic = 0;
    while (size_t ch = (size_t)*str++)
    {
        hash = (hash << OneEighth) + ch;
        if ((magic = hash & HighBits) != 0)
        {
            hash ^= (magic >> ThreeQuarters);
            hash &= ~magic;
        }
    }
    return hash;
}

/// @brief BKDR Hash Function
/// @detail 本算法由於在Brian Kernighan與Dennis Ritchie的《The C Programming Language》一書被展示而得名，是一種簡單快捷的hash算法，也是Java目前采用的字符串的Hash算法（累乘因子為31）。
template<class T>
size_t BKDRHash(const T *str)
{
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
{
  hash = hash * 131 + ch;   // 也可以乘以31、131、1313、13131、131313..
  // 有人說將乘法分解為位運算及加減法可以提高效率，如將上式表達為：hash = hash << 7 + hash << 1 + hash + ch;
  // 但其實在Intel平台上，CPU內部對二者的處理效率都是差不多的，
  // 我分別進行了100億次的上述兩種運算，發現二者時間差距基本為0（如果是Debug版，分解成位運算後的耗時還要高1/3）；
  // 在ARM這類RISC系統上沒有測試過，由於ARM內部使用Booth's Algorithm來模擬32位整數乘法運算，它的效率與乘數有關：
  // 當乘數8-31位都為1或0時，需要1個時鐘周期
  // 當乘數16-31位都為1或0時，需要2個時鐘周期
  // 當乘數24-31位都為1或0時，需要3個時鐘周期
  // 否則，需要4個時鐘周期
  // 因此，雖然我沒有實際測試，但是我依然認為二者效率上差別不大
}
return hash;
}
/// @brief SDBM Hash Function
/// @detail 本算法是由於在開源項目SDBM（一種簡單的數據庫引擎）中被應用而得名，它與BKDRHash思想一致，只是種子不同而已。
template<class T>
size_t SDBMHash(const T *str)
{
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
{
  hash = 65599 * hash + ch;
  //hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;
}
return hash;
}
/// @brief RS Hash Function
/// @detail 因Robert Sedgwicks在其《Algorithms in C》一書中展示而得名。
template<class T>
size_t RSHash(const T *str)
{
register size_t hash = 0;
size_t magic = 63689;
while (size_t ch = (size_t)*str++)
{
  hash = hash * magic + ch;
  magic *= 378551;
}
return hash;
}
/// @brief AP Hash Function
/// @detail 由Arash Partow發明的一種hash算法。
template<class T>
size_t APHash(const T *str)
{
register size_t hash = 0;
size_t ch;
for (long i = 0; ch = (size_t)*str++; i++)
{
  if ((i & 1) == 0)
  {
   hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
  }
  else
  {
   hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
  }
}
return hash;
}
/// @brief JS Hash Function
/// 由Justin Sobel發明的一種hash算法。
template<class T>
size_t JSHash(const T *str)
{
if(!*str)   // 這是由本人添加，以保證空字符串返回哈希值0
  return 0;
register size_t hash = 1315423911;
while (size_t ch = (size_t)*str++)
{
  hash ^= ((hash << 5) + ch + (hash >> 2));
}
return hash;
}
/// @brief DEK Function
/// @detail 本算法是由於Donald E. Knuth在《Art Of Computer Programming Volume 3》中展示而得名。
template<class T>
size_t DEKHash(const T* str)
{
if(!*str)   // 這是由本人添加，以保證空字符串返回哈希值0
  return 0;
register size_t hash = 1315423911;
while (size_t ch = (size_t)*str++)
{
  hash = ((hash << 5) ^ (hash >> 27)) ^ ch;
}
return hash;
}
/// @brief FNV Hash Function
/// @detail Unix system系統中使用的一種著名hash算法，後來微軟也在其hash_map中實現。
template<class T>
size_t FNVHash(const T* str)
{
if(!*str) // 這是由本人添加，以保證空字符串返回哈希值0
  return 0;
register size_t hash = 2166136261;
while (size_t ch = (size_t)*str++)
{
  hash *= 16777619;
  hash ^= ch;
}
return hash;
}
/// @brief DJB Hash Function
/// @detail 由Daniel J. Bernstein教授發明的一種hash算法。
template<class T>
size_t DJBHash(const T *str)
{
if(!*str) // 這是由本人添加，以保證空字符串返回哈希值0
  return 0;
register size_t hash = 5381;
while (size_t ch = (size_t)*str++)
{
  hash += (hash << 5) + ch;
}
return hash;
}
/// @brief DJB Hash Function 2
/// @detail 由Daniel J. Bernstein 發明的另一種hash算法。
template<class T>
size_t DJB2Hash(const T *str)
{
if(!*str) // 這是由本人添加，以保證空字符串返回哈希值0
  return 0;
register size_t hash = 5381;
while (size_t ch = (size_t)*str++)
{
  hash = hash * 33 ^ ch;
}
return hash;
}
/// @brief PJW Hash Function
/// @detail 本算法是基於AT&T貝爾實驗室的Peter J. Weinberger的論文而發明的一種hash算法。
template<class T>
size_t PJWHash(const T *str)
{
static const size_t TotalBits  = sizeof(size_t) * 8;
static const size_t ThreeQuarters = (TotalBits * 3) / 4;
static const size_t OneEighth  = TotalBits / 8;
static const size_t HighBits  = ((size_t)-1) << (TotalBits - OneEighth);

register size_t hash = 0;
size_t magic = 0;
while (size_t ch = (size_t)*str++)
{
  hash = (hash << OneEighth) + ch;
  if ((magic = hash & HighBits) != 0)
  {
   hash = ((hash ^ (magic >> ThreeQuarters)) & (~HighBits));
  }
}
return hash;
}
/// @brief ELF Hash Function
/// @detail 由於在Unix的Extended Library Function被附帶而得名的一種hash算法，它其實就是PJW Hash的變形。
template<class T>
size_t ELFHash(const T *str)
{
static const size_t TotalBits  = sizeof(size_t) * 8;
static const size_t ThreeQuarters = (TotalBits * 3) / 4;
static const size_t OneEighth  = TotalBits / 8;
static const size_t HighBits  = ((size_t)-1) << (TotalBits - OneEighth);
register size_t hash = 0;
size_t magic = 0;
while (size_t ch = (size_t)*str++)
{
  hash = (hash << OneEighth) + ch;
  if ((magic = hash & HighBits) != 0)
  {
   hash ^= (magic >> ThreeQuarters);
   hash &= ~magic;
  }
}
return hash;
}
我對這些hash的散列質量及效率作了一個簡單測試，測試結果如下：

測試1：對100000個由大小寫字母與數字隨機的ANSI字符串（無重復，每個字符串最大長度不超過64字符）進行散列：

字符串函數沖突數除1000003取余後的沖突數
BKDRHash
0 4826
SDBMHash
2 4814
RSHash
2 4886
APHash
0 4846
ELFHash
1515 6120
JSHash
779 5587
DEKHash
863 5643
FNVHash
2 4872
DJBHash
832 5645
DJB2Hash
695 5309
PJWHash
1515 6120

測試2：對100000個由任意UNICODE組成隨機字符串（無重復，每個字符串最大長度不超過64字符）進行散列：

字符串函數沖突數除1000003取余後的沖突數
BKDRHash
3 4710
SDBMHash
3 4904
RSHash
3 4822
APHash
2 4891
ELFHash
16 4869
JSHash
3 4812
DEKHash
1 4755
FNVHash
1 4803
DJBHash
1 4749
DJB2Hash
2 4817
PJWHash
16 4869

測試3：對1000000個隨機ANSI字符串（無重復，每個字符串最大長度不超過64字符）進行散列：

字符串函數耗時（毫秒）
BKDRHash
109
SDBMHash
109
RSHash
124
APHash
187
ELFHash
249
JSHash
172
DEKHash
140
FNVHash
125
DJBHash
125
DJB2Hash
125
PJWHash
234

結論：也許是我的樣本存在一些特殊性，在對ASCII碼字符串進行散列時，PJW與ELF Hash（它們其實是同一種算法）無論是質量還是效率，都相當糟糕；例如："b5"與“aE"，這兩個字符串按照PJW散列出來的hash值就是一樣的。另外，其它幾種依靠異或來散列的哈希函數，如：JS/DEK/DJB Hash，在對字母與數字組成的字符串的散列效果也不怎麼好。相對而言，還是BKDR與SDBM這類簡單的Hash效率與效果更好。

其他：

作者：icefireelf

常用的字符串Hash函數還有ELFHash，APHash等等，都是十分簡單有效的方法。這些函數使用位運算使得每一個字符都對最後的函數值產生影響。另外還有以MD5和SHA1為代表的雜湊函數，這些函數幾乎不可能找到碰撞。

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

Hash函數數據1 數據2 數據3 數據4 數據1得分數據2得分數據3得分數據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

其中數據1為100000個字母和數字組成的隨機串哈希沖突個數。數據2為100000個有意義的英文句子哈希沖突個數。數據3為數據1的哈希值與 1000003(大素數)求模後存儲到線性表中沖突的個數。數據4為數據1的哈希值與10000019(更大素數)求模後存儲到線性表中沖突的個數。

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

[cpp]
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);
}