字符串的哈希函数

我使用 Dan Bernstein 的 djb2 取得了不错的成绩。

unsigned long
hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

---

首先，您通常不希望对哈希表使用加密哈希。按照加密标准来说非常快的算法，按照哈希表标准来说仍然非常慢。

其次，您要确保输入的每一位都可以/将影响结果。一种简单的方法是将当前结果旋转一些位，然后将当前哈希码与当前字节进行异或。重复直到到达字符串的末尾。请注意，您通常也不希望旋转是字节大小的偶数倍。

例如，假设 8 位字节的常见情况，您可能会旋转 5 位：

int hash(char const *input) { 
    int result = 0x55555555;

    while (*input) { 
        result ^= *input++;
        result = rol(result, 5);
    }
}

编辑：另请注意，10000 个插槽很少是哈希表大小的好选择。您通常需要以下两件事之一：您要么想要一个素数作为大小（确保某些类型的哈希分辨率的正确性所需），要么是 2 的幂（因此可以通过简单的方法将值减小到正确的范围位掩码）。

---

Wikipedia shows 一个很好的字符串散列函数，称为 Jenkins One At A Time Hash。它还引用了此哈希的改进版本。

uint32_t jenkins_one_at_a_time_hash(char *key, size_t len)
{
    uint32_t hash, i;
    for(hash = i = 0; i < len; ++i)
    {
        hash += key[i];
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}

---

有许多现有的 C 哈希表实现，从 C 标准库 hcreate/hdestroy/hsearch 到 APR 和 glib 中的那些，它们还提供预构建的哈希函数。我强烈建议使用那些而不是发明自己的哈希表或哈希函数；它们已针对常见用例进行了大量优化。

但是，如果您的数据集是静态的，那么您最好的解决方案可能是使用 perfect hash。 gperf 将为您生成给定数据集的完美哈希。

---

djb2 对 this 466k english dictionary 有 317 次冲突，而 MurmurHash 对 64 位散列没有，而对 32 位散列有 21 个（对于 466k 随机 32 位散列，预计大约有 25 个）。如果可用，我的建议是使用 MurmurHash，它非常快，因为它一次需要几个字节。但是，如果您需要一个简单而简短的哈希函数来复制并粘贴到您的项目中，我建议您使用 murmurs 一次一个字节的版本：

uint32_t inline MurmurOAAT32 ( const char * key)
{
  uint32_t h(3323198485ul);
  for (;*key;++key) {
    h ^= *key;
    h *= 0x5bd1e995;
    h ^= h >> 15;
  }
  return h;
}

uint64_t inline MurmurOAAT64 ( const char * key)
{
  uint64_t h(525201411107845655ull);
  for (;*key;++key) {
    h ^= *key;
    h *= 0x5bd1e9955bd1e995;
    h ^= h >> 47;
  }
  return h;
}

简而言之，哈希表的最佳大小是尽可能大，同时仍适合内存。因为我们通常不知道或不想查看我们有多少可用内存，甚至可能会发生变化，所以最佳哈希表大小大约是要存储在表中的预期元素数量的 2 倍。分配比这更多的东西会使你的哈希表更快，但回报会迅速递减，让你的哈希表小于这个值会使它成倍地变慢。这是因为哈希表存在非线性 trade-off between space and time complexity，最佳负载因子为 2-sqrt(2) = 0.58... 显然。

---

djb2 不错

尽管 djb2 和 presented on stackoverflow by cnicutar 几乎可以肯定更好，但我认为也值得展示 K&R 散列：

其中一个 K&R 散列很糟糕，一个可能非常好：

显然是一个糟糕的哈希算法，如 K&R 第 1 版（来源）unsigned long hash(unsigned char *str) { unsigned int hash = 0;诠释 c;而 (c = *str++) 哈希 += c;返回哈希；可能是一个相当不错的哈希算法，如 K&R 第 2 版中所述（我在本书的第 144 页验证了）；注意：如果您计划在哈希算法之外进行模数调整到您的数组长度，请务必从 return 语句中删除 % HASHSIZE。另外，我建议您将 return 和“hashval”类型设为 unsigned long，甚至更好：uint32_t 或 uint64_t，而不是简单的 unsigned (int)。 unsigned hash(char *s) { unsigned hashval; for (hashval = 0; *s != '\0'; s++) hashval = *s + 31*hashval;返回哈希值 % HASHSIZE； }

请注意，从这两种算法中可以清楚地看出，第一版哈希如此糟糕的一个原因是因为它没有考虑字符串字符 order，因此 hash("ab") 将因此返回与 {2 相同的值}。这 不是 所以对于第 2 版散列，但是，它会（好多了！）为这些字符串返回两个不同的值。

std::unordered_map<> 模板容器哈希表使用的 GCC C++11 哈希函数非常出色。

用于 unordered_map（哈希表模板）和 unordered_set（哈希集模板）的 GCC C++11 哈希函数如下所示。

这是对使用什么是 GCC C++11 哈希函数的问题的部分回答，说明 GCC 使用 Austin Appleby (http://murmurhash.googlepages.com/) 的“MurmurHashUnaligned2”实现。

在文件“gcc/libstdc++-v3/libsupc++/hash_bytes.cc”中，在这里（https://github.com/gcc-mirror/gcc/blob/master/libstdc++-v3/libsupc++/hash_bytes.cc），我发现实施。例如，这是“32 位 size_t”返回值的值（2017 年 8 月 11 日提取）：

代码：

// Implementation of Murmur hash for 32-bit size_t.
size_t _Hash_bytes(const void* ptr, size_t len, size_t seed)
{
  const size_t m = 0x5bd1e995;
  size_t hash = seed ^ len;
  const char* buf = static_cast<const char*>(ptr);

  // Mix 4 bytes at a time into the hash.
  while (len >= 4)
  {
    size_t k = unaligned_load(buf);
    k *= m;
    k ^= k >> 24;
    k *= m;
    hash *= m;
    hash ^= k;
    buf += 4;
    len -= 4;
  }

  // Handle the last few bytes of the input array.
  switch (len)
  {
    case 3:
      hash ^= static_cast<unsigned char>(buf[2]) << 16;
      [[gnu::fallthrough]];
    case 2:
      hash ^= static_cast<unsigned char>(buf[1]) << 8;
      [[gnu::fallthrough]];
    case 1:
      hash ^= static_cast<unsigned char>(buf[0]);
      hash *= m;
  };

  // Do a few final mixes of the hash.
  hash ^= hash >> 13;
  hash *= m;
  hash ^= hash >> 15;
  return hash;
}

Austin Appleby 的 MurmerHash3 是最好的！这甚至比他上面使用的 gcc C++11 std::unordered_map<> 哈希也有所改进。

不仅是所有这些中最好的，而且奥斯汀将 MurmerHash3 发布到公共领域。在此处查看我的其他答案：What is the default hash function used in C++ std::unordered_map?。

也可以看看

要试用和测试的其他哈希表算法：http://www.cse.yorku.ca/~oz/hash.html。那里提到的哈希算法：djb2 sdbm loss loss (K&R 1st edition)

---

我想验证卞小宁的回答，可惜他没有贴出他的代码。所以我实现了一个小测试套件，并在 466K English words 列表上运行了不同的小散列函数，以查看每个的冲突数量：

Hash function      |     Collisions | Time (words) | Time (file)
=================================================================
CRC32              |    23 (0.005%) |      112 ms  |      38 ms
MurmurOAAT         |    26 (0.006%) |       86 ms  |      10 ms
FNV hash           |    32 (0.007%) |       87 ms  |       7 ms
Jenkins OAAT       |    36 (0.008%) |       90 ms  |       8 ms
DJB2 hash          |   344 (0.074%) |       87 ms  |       5 ms
K&R V2             |   356 (0.076%) |       86 ms  |       5 ms
Coffin             |   763 (0.164%) |       86 ms  |       4 ms
x17 hash           |  2242 (0.481%) |       87 ms  |       7 ms
-----------------------------------------------------------------
MurmurHash3_x86_32 |    19 (0.004%) |       90 ms  |       3 ms

我包括了两者的时间：单独对所有单词进行哈希处理，并对所有英语单词的整个文件进行一次哈希处理。我还在测试中加入了一个更复杂的 MurmurHash3_x86_32 以供参考。

结论：

在 Intel x86-64 架构上使用流行的 DJB2 哈希函数来处理字符串几乎没有意义。因为它比类似的函数（MurmurOAAT、FNV 和 Jenkins OAAT）具有更多的冲突，同时具有非常相似的吞吐量。 Bernstein 的 DJB2 在短弦上表现特别差。示例冲突：Liz/MHz、Bon/COM、Rey/SEX。

测试代码：

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#define MAXLINE 2048
#define SEED    0x12345678

uint32_t DJB2_hash(const uint8_t *str)
{
    uint32_t hash = 5381;
    uint8_t c;
    while ((c = *str++))
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    return hash;
}

uint32_t FNV(const void* key, int len, uint32_t h)
{
    // Source: https://github.com/aappleby/smhasher/blob/master/src/Hashes.cpp
    h ^= 2166136261UL;
    const uint8_t* data = (const uint8_t*)key;
    for(int i = 0; i < len; i++)
    {
        h ^= data[i];
        h *= 16777619;
    }
    return h;
}

uint32_t MurmurOAAT_32(const char* str, uint32_t h)
{
    // One-byte-at-a-time hash based on Murmur's mix
    // Source: https://github.com/aappleby/smhasher/blob/master/src/Hashes.cpp
    for (; *str; ++str) {
        h ^= *str;
        h *= 0x5bd1e995;
        h ^= h >> 15;
    }
    return h;
}

uint32_t KR_v2_hash(const char *s)
{
    // Source: https://stackoverflow.com/a/45641002/5407270
    uint32_t hashval = 0;
    for (hashval = 0; *s != '\0'; s++)
        hashval = *s + 31*hashval;
    return hashval;
}

uint32_t Jenkins_one_at_a_time_hash(const char *str, size_t len)
{
    uint32_t hash, i;
    for(hash = i = 0; i < len; ++i)
    {
        hash += str[i];
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}

uint32_t crc32b(const uint8_t *str) {
    // Source: https://stackoverflow.com/a/21001712
    unsigned int byte, crc, mask;
    int i = 0, j;
    crc = 0xFFFFFFFF;
    while (str[i] != 0) {
        byte = str[i];
        crc = crc ^ byte;
        for (j = 7; j >= 0; j--) {
            mask = -(crc & 1);
            crc = (crc >> 1) ^ (0xEDB88320 & mask);
        }
        i = i + 1;
    }
    return ~crc;
}

inline uint32_t _rotl32(uint32_t x, int32_t bits)
{
    return x<<bits | x>>(32-bits);      // C idiom: will be optimized to a single operation
}

uint32_t Coffin_hash(char const *input) { 
    // Source: https://stackoverflow.com/a/7666668/5407270
    uint32_t result = 0x55555555;
    while (*input) { 
        result ^= *input++;
        result = _rotl32(result, 5);
    }
    return result;
}

uint32_t x17(const void * key, int len, uint32_t h)
{
    // Source: https://github.com/aappleby/smhasher/blob/master/src/Hashes.cpp
    const uint8_t * data = (const uint8_t*)key;
    for (int i = 0; i < len; ++i)
    {
        h = 17 * h + (data[i] - ' ');
    }
    return h ^ (h >> 16);
}

uint32_t apply_hash(int hash, const char* line)
{
    switch (hash) {
    case 1: return crc32b((const uint8_t*)line);
    case 2: return MurmurOAAT_32(line, SEED);
    case 3: return FNV(line, strlen(line), SEED);
    case 4: return Jenkins_one_at_a_time_hash(line, strlen(line));
    case 5: return DJB2_hash((const uint8_t*)line);
    case 6: return KR_v2_hash(line);
    case 7: return Coffin_hash(line);
    case 8: return x17(line, strlen(line), SEED);
    default: break;
    }
    return 0;
}

int main(int argc, char* argv[])
{
    // Read arguments
    const int hash_choice = atoi(argv[1]);
    char const* const fn = argv[2];

    // Read file
    FILE* f = fopen(fn, "r");

    // Read file line by line, calculate hash
    char line[MAXLINE];
    while (fgets(line, sizeof(line), f)) {
        line[strcspn(line, "\n")] = '\0';   // strip newline
        uint32_t hash = apply_hash(hash_choice, line);
        printf("%08x\n", hash);
    }
    fclose(f);

    return 0;
}

PS 可以在 Reini Urban (rurban) 的 SMHasher repository 中找到对现代散列函数的速度和质量的更全面的回顾。请注意表中的“质量问题”列。

---

首先，130 个单词的 40 次冲突是否散列到 0..99 不好？如果您不采取专门的措施来实现完美的散列，就不能指望完美的散列。大多数时候，普通的散列函数不会比随机生成器发生更少的冲突。

具有良好声誉的散列函数是 MurmurHash3。

最后，关于哈希表的大小，实际上取决于您想到的哈希表类型，尤其是桶是可扩展的还是单槽的。如果存储桶是可扩展的，那么还有一个选择：您为您拥有的内存/速度限制选择平均存储桶长度。

---

我已经尝试了这些哈希函数并得到了以下结果。我有大约 960^3 个条目，每个 64 字节长，64 个不同顺序的字符，哈希值 32 位。 here 中的代码。

Hash function    | collision rate | how many minutes to finish
==============================================================
MurmurHash3      |           6.?% |                      4m15s
Jenkins One..    |           6.1% |                      6m54s   
Bob, 1st in link |          6.16% |                      5m34s
SuperFastHash    |            10% |                      4m58s
bernstein        |            20% |       14s only finish 1/20
one_at_a_time    |          6.16% |                       7m5s
crc              |          6.16% |                      7m56s

一件奇怪的事情是，几乎所有的哈希函数对我的数据都有 6% 的冲突率。

---

我用过的一件效果很好的东西是以下（我不知道它是否已经提到过，因为我不记得它的名字了）。

您为密钥字母表中的每个字符 [0,255] 预先计算一个带有随机数的表 T。您通过 T[k0] xor T[k1] xor ... xor T[kN] 对密钥“k0 k1 k2 ... kN”进行哈希处理。您可以轻松地证明这与您的随机数生成器一样随机，并且在计算上非常可行，如果您真的遇到了一个非常糟糕的实例，并且有很多冲突，您可以使用一批新的随机数重复整个过程。

---