字符串的哈希函数

Question

字符串的哈希函数

calgorithmhashdictionaryhashtable

173

我正在使用C语言实现哈希表，并测试字符串的哈希函数。

首先，我尝试了将ASCII码相加并使用模运算（% 100），但是在第一组包含130个单词的数据测试中，结果很差：40个冲突。

最终输入的数据将包含8000个单词（这是一个存储在文件中的字典）。哈希表声明为int table[10000]，其中包含单词在.txt文件中的位置。

什么是最适合哈希字符串的算法？
如何确定哈希表的大小？

- lilawood

11

如果你的哈希表有1万个条目，为什么要使用模100？在如此小的模数下得到130个单词中的40次冲突并不奇怪。 - Carey Gregory

15

请参考以下资源了解各种哈希函数（从通用到字符串到加密）：http://burtleburtle.net/bob/hash/evahash.html 和 http://www.partow.net/programming/hashfunctions/。 - user166390

5

为了澄清@CareyGregory先生的问题：您是否意识到，作为基本的数学定理，在100个桶中放置130个物品（即mod 100），必然会产生30次碰撞（其中碰撞是指将第二、第三等物品放入同一个桶的每次情况），对吗？因此，您只比这还多一点点。 - derobert

4

@lilawood：好的，我明白了，但为了更好地测试，您应该使用80个单词和100个条目的哈希表。这将给您与实时数据相同的比例，并且不会强制发生冲突。 - Carey Gregory

5

可能是字符串好的哈希函数的重复问题。 - M.J. Rayburn

显示剩余7条评论

11个回答

33

首先，通常情况下你不会想要在哈希表中使用加密哈希。即使是按照加密标准非常快速的算法，在哈希表的标准下也仍旧是异常缓慢。

其次，你需要确保输入的每一位都能/将影响到结果。一种简单的方法是将当前结果向左循环移动一定数量的位数，然后将当前哈希码与当前字节进行异或运算。重复此过程，直到到达字符串的末尾。请注意，通常不要将旋转值设置为字节大小的偶数倍。

例如，假设按照8位字节的常见情况，你可以左移5位：

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

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

编辑：还要注意，10000个槽位很少是哈希表大小的好选择。通常有两种情况：您要么需要一个质数作为大小（对某些类型的哈希解析确保正确性），要么需要2的幂次方（这样可以通过简单的位掩码将值缩小到正确的范围）。

- Jerry Coffin

这不是C语言，但我对您对此相关答案的想法很感兴趣：https://dev59.com/JF0Z5IYBdhLWcg3wdQEy#31440118 - Suragch

1

@Suragch：自从我写这篇文章以来，许多处理器已经开始包含特殊的硬件来加速SHA计算，这使得它变得更具竞争力。尽管如此，我怀疑你的代码并不像你想象的那样安全——例如，IEEE浮点数有两种不同的位模式（0和-0），应该产生相同的哈希值（它们将彼此比较相等）。 - Jerry Coffin

2

@thanos.a，你可以手写它，就像这样：static inline unsigned rol(unsigned r, int k) {return (r << k) | (r >> (32 - k));}（假设是32位整数）。至少在x86-64上，GCC会将其编译为一条指令。 - vonbrand

一些批评：result 只需要是非0的；1就可以了。好的，对输入进行异或运算比加法更好。使用 += 来进行 ROL 操作比使用 = 更好。如果需要，ROL 可以是 SHL。将5改为7可以减少冲突。两行最终处理器 h += h<<17; h ^= h>>12; 会稍微扩散一下，提高均匀性。因此，这可能是最好的最小32位哈希/校验和函数，只需8个指令，超过了类似的函数如 ELFHash/BKDRHash/DJB2。虽然在64位机器上不够优化。 - bryc

@bryc：使用左移而不是旋转意味着如果您哈希一个足够长的字符串，那么您首先哈希的字符对最终结果没有影响。 - Jerry Coffin

显示剩余3条评论

24

我想验证边小宁的答案，但不幸的是他没有发布他的代码。所以我实现了一个小的测试套件，并在466K英文单词列表上运行了不同的小哈希函数，以查看每个函数的碰撞次数。

Hash function      |     Collisions | Time (words) | Time (file) | Avalanching
===============================================================================
CRC32              |    23 (0.005%) |     96.1 ms  |   120.9 ms  |      99.8%
MurmurOAAT         |    26 (0.006%) |     17.2 ms  |    19.4 ms  |     100.0%
FNV hash           |    32 (0.007%) |     16.4 ms  |    14.0 ms  |      98.6%
Jenkins OAAT       |    36 (0.008%) |     19.9 ms  |    18.5 ms  |     100.0%
DJB2 hash          |   344 (0.074%) |     18.2 ms  |    12.7 ms  |      92.9%
K&R V2             |   356 (0.076%) |     18.0 ms  |    11.9 ms  |      92.8%
Coffin             |   763 (0.164%) |     16.3 ms  |    11.7 ms  |      91.4%
x17 hash           |  2242 (0.481%) |     18.6 ms  |    20.0 ms  |      91.5%
-------------------------------------------------------------------------------
large_prime        |    25 (0.005%) |     16.5 ms  |    18.6 ms  |      96.6%
MurmurHash3_x86_32 |    19 (0.004%) |     20.5 ms  |     4.4 ms  |     100.0%

我在测试中包括了对每个单词进行哈希和对整个英文单词文件进行哈希的时间。我还在测试中使用了更复杂的MurmurHash3_x86_32作为参考。此外，我还计算了“avalanching”，这是衡量连续单词哈希的不可预测性的指标。低于100%意味着“相当可预测”（对于哈希表可能还可以，但对于其他用途来说是不好的）。

结论：

在Intel x86-64（或AArch64）架构上，使用流行的DJB2哈希函数几乎没有什么意义。因为它与类似的函数（FNV，Jenkins OAAT和MurmurOAAT）相比，碰撞更多，而吞吐量相当。Bernstein的DJB2在处理短字符串时表现特别糟糕。例如碰撞：Liz/MHz，Bon/COM，Rey/SEX。
如果您必须使用“乘以奇数”的方法（例如DJB2 = x33，K&R V2 = x31或SDBM = x65599），请选择一个大的32位质数，而不是一个小的8位数。这对于减少碰撞的数量有很大的影响。例如，hash = 17000069 * hash + s[i]只产生25个碰撞，而DJB2产生344个碰撞。

测试代码（使用gcc -O2编译）：

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>

#define MODE     1          // 1 = hash each word individually; 2 = hash the entire file
#define MAXLEN   50         // maximum length of a word
#define MAXWORDS 500000     // maximum number of words in a file
#define SEED     0x12345678

#if MODE == 1
char words[MAXWORDS][MAXLEN];
#else
char file[MAXWORDS * MAXLEN];
#endif

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, uint32_t h)
{
    // See: https://github.com/aappleby/smhasher/blob/master/src/Hashes.cpp
    h ^= 2166136261UL;
    const uint8_t* data = (const uint8_t*)key;
    for(int i = 0; data[i] != '\0'; 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://dev59.com/PWsz5IYBdhLWcg3wxq4V#45641002
    // a.k.a. Java String hashCode()
    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)
{
    uint32_t hash, i;
    for (hash = i = 0; str[i] != '\0'; ++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://dev59.com/oGEi5IYBdhLWcg3wuuUk#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://dev59.com/PWsz5IYBdhLWcg3wxq4V#7666668
    uint32_t result = 0x55555555;
    while (*input) { 
        result ^= *input++;
        result = _rotl32(result, 5);
    }
    return result;
}

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

uint32_t large_prime(const uint8_t *s, uint32_t hash)
{
    // Better alternative to x33: multiply by a large co-prime instead of a small one
    while (*s != '\0')
        hash = 17000069*hash + *s++;
    return hash;
}

void readfile(FILE* fp, char* buffer) {
    fseek(fp, 0, SEEK_END);
    size_t size = ftell(fp);
    rewind(fp);
    fread(buffer, size, 1, fp);
    buffer[size] = '\0';
}

struct timeval stop, start;
void timing_start() {
    gettimeofday(&start, NULL);
}

void timing_end() {
    gettimeofday(&stop, NULL);
    printf("took %lu us\n", (stop.tv_sec - start.tv_sec) * 1000000 + stop.tv_usec - start.tv_usec);
}

uint32_t apply_hash(int hash, const char* line)
{
    uint32_t result;
#if MODE == 2
    timing_start();
#endif
    switch (hash) {
        case 1: result = crc32b((const uint8_t*)line); break;
        case 2: result = large_prime((const uint8_t *)line, SEED); break;
        case 3: result = MurmurOAAT_32(line, SEED); break;
        case 4: result = FNV(line, SEED); break;
        case 5: result = Jenkins_one_at_a_time_hash(line); break;
        case 6: result = DJB2_hash((const uint8_t*)line); break;
        case 7: result = KR_v2_hash(line); break;
        case 8: result = Coffin_hash(line); break;
        case 9: result = x17(line, SEED); break;
        default: break;
    }
#if MODE == 2
    timing_end();
#endif
    return result;
}

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

    printf("Algorithm: %d\n", hash_choice);
    printf("File name: %s\n", fname);

    // Open file
    FILE* f = fopen(fname, "r");

#if MODE == 1
    char line[MAXLEN];
    size_t word_count = 0;
    uint32_t hashes[MAXWORDS];

    // Read file line by line
    while (fgets(line, sizeof(line), f)) {
        line[strcspn(line, "\n")] = '\0';   // strip newline
        strcpy(words[word_count], line);
        word_count++;
    }
    fclose(f);

    // Calculate hashes
    timing_start();
    for (size_t i = 0; i < word_count; i++) {
        hashes[i] = apply_hash(hash_choice, words[i]);
    }
    timing_end();

    // Output hashes
    for (size_t i = 0; i < word_count; i++) {
        printf("%08x\n", hashes[i]);
    }

#else 
    // Read entire file
    readfile(f, file);
    fclose(f);
    printf("Len: %lu\n", strlen(file)); 

    // Calculate hash
    uint32_t hash = apply_hash(hash_choice, file);
    printf("%08x\n", hash);
#endif

    return 0;
}

附注：关于现代哈希函数的速度和质量的更全面的评估可以在Reini Urban（rurban）的SMHasher repository中找到。请注意表格中的“质量问题”栏目。

- Andriy Makukha

1

这正是我在寻找的答案！太棒了，点赞+1。 - Ted Klein Bergman

11

维基百科介绍了一个称为 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;
}

- RushPL

9

`djb2`算法很好

虽然djb2算法，正如cnicutar在stackoverflow上介绍的那样，几乎肯定更好些，但我认为值得展示一下K&R哈希函数：

K&R中的一个哈希函数很差，另一个可能相当不错：

Apparently a terrible hash algorithm, as presented in K&R 1st edition. This is simply a summation of all bytes in the string (source):

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

    while (c = *str++)
        hash += c;

    return hash;
}

Probably a pretty decent hash algorithm, as presented in K&R version 2 (verified by me on pg. 144 of the book); NB: be sure to remove % HASHSIZE from the return statement if you plan on doing the modulus sizing-to-your-array-length outside the hash algorithm. Also, I recommend you make the return and "hashval" type unsigned long, or even better: uint32_t or uint64_t, instead of the simple unsigned (int). This is a simple algorithm which takes into account byte order of each byte in the string by doing this style of algorithm: hashvalue = new_byte + 31*hashvalue, for all bytes in the string:
```
unsigned hash(char *s)
{
    unsigned hashval;

    for (hashval = 0; *s != '\0'; s++)
        hashval = *s + 31*hashval;
    return hashval % HASHSIZE;
}
```

请注意，从这两个算法中可以清楚地看出，第一版哈希算法之所以糟糕，是因为它没有考虑字符串字符的顺序，因此 hash("ab") 将返回与 hash("ba") 相同的值。然而，在第二版哈希中并非如此，它会将这些字符串返回两个不同的值，做得（更好！）。

GCC C++11哈希函数用于std::unordered_map<>模板容器哈希表是很优秀的。

强调：GCC C++11哈希函数用于unordered_map(哈希表模板)和unordered_set(哈希集合模板)，其实现如下：

1. 这是关于“GCC C++11哈希函数是什么”的部分回答，它声明GCC使用Austin Appleby的MurmurHashUnaligned2实现(http://murmurhash.googlepages.com/)。详见此链接https://dev59.com/z2Ik5IYBdhLWcg3wTcYr#19411888。

2. 在文件“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<>`哈希表更好。

不仅如此，Austin还将MurmerHash3发布到了公共领域。在这里查看我关于此问题的其他答案：C ++ std :: unordered_map中使用的默认哈希函数是什么？。

另请参阅

尝试和测试其他哈希表算法：http://www.cse.yorku.ca/~oz/hash.html。其中提到的哈希算法有：
1. djb2
2. sdbm
3. lose lose (K&R第一版)

- Gabriel Staples

9

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

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

- Nick Johnson

hsearch是通过比较字符串或字符串指针地址来进行搜索的吗？我认为它只是检查指针地址？我尝试使用不同的指针但相同的字符串值。hsearch失败并声明未找到任何元素。 - Sandeep

9

djb2在这个466k英语词典中有317个冲突，而MurmurHash的64位哈希没有冲突，32位哈希有21个冲突（对于466k个随机32位哈希值，大约有25个冲突是可以预期的）。我的建议是，如果可用的话，请使用MurmurHash，它非常快，因为它一次处理几个字节。但如果您需要一个简单和短的哈希函数来复制和粘贴到您的项目中，我建议使用murmurs one-byte-at-a-time版本。

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倍。分配比这更多的空间将使您的哈希表更快，但回报急剧减少，使哈希表比这小将使其指数级变慢。这是因为哈希表的空间和时间复杂度之间存在非线性权衡，其最佳负载因子为2-sqrt(2) = 0.58… 显然。

- Wolfgang Brehm

2

首先，130个单词哈希到0..99中出现40次冲突，这是不好的吗？如果您没有采取特定措施来实现完美的哈希，则不能期望完美的哈希。通常情况下，普通哈希函数的冲突比随机生成器少不了多少。 MurmurHash3是一个声誉良好的哈希函数。

最后，关于哈希表的大小，这真的取决于您想要什么样的哈希表，特别是桶是否可扩展或者只有一个插槽。如果桶是可扩展的，那么又有一个选择：您可以根据内存/速度限制选择平均桶长度。

- Pascal Cuoq

1

预期哈希碰撞次数为 n - m * (1 - ((m-1)/m)^n) = 57.075...。40 次碰撞比随机情况下预期的要好（在 p 得分为0.999时，为46到70）。所讨论的哈希函数比随机更均匀，或者我们正在目睹一个非常罕见的事件。 - Wolfgang Brehm

2

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

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%的冲突率。

- Xiaoning Bian

1

虽然这个链接可能回答了问题，但最好在此处包含答案的基本部分并提供参考链接。仅有链接的答案如果链接页面发生更改可能会变得无效。 - thewaywewere

赞一个好的表格，但是在你的回答中发布每个哈希的源代码也是必不可少的。否则，链接可能会失效，我们就没办法了。 - Gabriel Staples

1

预期的碰撞次数应该是9.112499989700318E+7或0.103 * 960³，如果哈希值是真正随机的，那么如果它们都在这个值左右，我不会感到惊讶，但是0.0616 * 960³似乎有点偏离，几乎像哈希值比随机分布更均匀，而且在64字节长度下，这个限制肯定应该被接近。你能分享一下你哈希的字符串集，这样我就可以尝试复现它吗？ - Wolfgang Brehm

有人知道 14s only finish 1/20 是什么意思吗？我不理解这句话。 - Gabriel Staples

0

我用过的一种有效方法是以下内容（我不知道它是否已经被提到，因为我记不起它的名字）。

您可以预先计算一个表T，其中包含密钥字母表[0,255]中每个字符的随机数。通过使用T[k0] xor T[k1] xor ... xor T[kN]来哈希您的密钥'k0 k1 k2 ... kN'。您可以轻松地证明这与您的随机数生成器一样随机，并且在计算上非常可行，如果您真的遇到了很多冲突的情况，您可以使用新的一批随机数重复整个过程。

- Michael Nett

如果我没记错的话，这会遇到与 Gabriel 的答案中 K＆R 第一版相同的问题；即“ ab”和“ ba”将哈希到相同的值。 - Johann Oskarsson

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- cnicutar · Accepted Answer

259

我已经使用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;
}

- cnicutar

55

这个答案中链接的页面非常有趣。 - Adrien Plisson

2

程序如何从while循环中退出？=S - Daniel N.

4

当c为零时。while(c = *str++)的等效语句应该是(0 != (c = *str++))。 - rxantos

6

@Josepas，哈希函数理想情况下应该返回一个size_t或其他类似的无符号值（例如此代码中的unsigned long）。调用者负责对结果取模以适应哈希表。调用者控制哈希到的表槽；而不是函数。它只返回一些无符号数字。 - WhozCraig

6

太棒了！这个算法轻松击败了Murmur哈希，FNV变种哈希和许多其他哈希算法！加一！ - David Haim

显示剩余19条评论

字符串的哈希函数

djb2算法很好

K&R中的一个哈希函数很差，另一个可能相当不错：

Austin Appleby的MurmerHash3是最好的！它甚至比他在上面使用的gcc C++11 std::unordered_map<>哈希表更好。

另请参阅

`djb2`算法很好

Austin Appleby的MurmerHash3是最好的！它甚至比他在上面使用的gcc C++11 `std::unordered_map<>`哈希表更好。