字符串的哈希函数

我正在用 C 语言编写哈希表，我正在测试字符串的哈希函数。

我尝试的第一个函数是添加 ascii 代码并使用 modulo (% 100) ，但是我在第一次数据测试中得到的结果很糟糕: 130个单词需要40次碰撞。

最终的输入数据将包含8000个单词(它是一个字典存储在一个文件中)。散列表声明为 int table[10000]，并包含单词在。Txt 文件。

  • 散列字符串的最佳算法是什么？
  • 如何确定散列表的大小？
323229 次浏览
小开
最佳答案

我用丹 · 伯恩斯坦的 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;
}
小开

首先，是40次碰撞为130个字，散列为0。。99坏？如果没有采取特定的步骤，就不能期望完美的散列。在大多数情况下，普通哈希函数的冲突不会比随机生成器少。

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

最后，关于哈希表的大小，它实际上取决于您想要的哈希表的类型，特别是，桶是可扩展的还是单槽的。如果存储段是可扩展的，那么还有一个选择: 您可以选择存储段/速度约束的平均存储段长度。

小开

首先，通常 没有希望对哈希表使用加密哈希。按照密码学标准算法 非常的速度很快，但是按照哈希表标准算法仍然非常慢。

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

例如，假设通常情况下是8位字节，您可以旋转5位:

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


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

编辑: 还要注意，对于散列表大小来说，10000个插槽很少是一个好的选择。您通常需要以下两种情况之一: 要么需要一个素数作为大小(用某些类型的散列分辨率确保正确性所必需的) ，要么需要一个2的幂(因此可以通过一个简单的位掩码将值减少到正确的范围)。

小开

Wikipedia 显示了一个很好的字符串散列函数，名为 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/hbroke/hsearch 到 四月和 油嘴滑舌中的哈希表实现，它们都提供了预构建的哈希函数。我强烈建议使用它们，而不是发明自己的散列表或散列函数; 它们已经针对常见用例进行了大量优化。

但是，如果您的数据集是静态的，那么最好的解决方案可能是使用 完美的大麻。Gperf将为您生成给定数据集的完美散列。

小开

我使用过的一样东西得到了很好的效果，那就是下面的内容(我不知道它是否已经被提到过，因为我记不住它的名字)。

您预先计算了一个表 T，其中对于键字母表[0,255]中的每个字符都有一个随机数。通过取 T [ k0] xor T [ k1] xor... xor T [ kN ]来散列密钥‘ k0 k1 k2... kN’。你可以很容易地证明这和你的随机数生成器一样是随机的，而且它的计算非常可行，如果你真的遇到了一个非常糟糕的实例，有很多冲突，你可以使用一批新的随机数重复整个过程。

小开

我尝试了这些散列函数，得到了以下结果。我有大约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% 的冲突率。

小开

djb2正常

虽然 djb2，作为 在堆栈溢出上由 Cnicutar 呈现，几乎肯定是更好的，我认为它值得显示的 绑架勒索散列也:

其中一个 K & R 散列很糟糕，一个可能还不错:

  1. 显然是一个 糟透了散列算法，如 K & R 第一版所示。< em > 这是字符串(来源)中所有字节的总和: 
    unsigned long hash(unsigned char *str)
{
unsigned int hash = 0;
int c;


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


return hash;
}
  2. 可能是一个相当不错的哈希算法，如 K & R 版本2 所示(由我在 pg 上验证)。注意: 如果您计划在 hash 算法之外执行数组长度的模大小调整，一定要从 return 语句中删除 % HASHSIZE。另外，我建议您使用返回和“ hashval”类型 unsigned long，或者更好的: uint32_t或 uint64_t，而不是简单的 unsigned(int)。< em > 这是一个简单的算法，它考虑字符串中每个字节的 字节顺序，执行以下类型的算法: hashvalue = new_byte + 31*hashvalue，针对字符串中的所有字节: 
    unsigned hash(char *s)
{
unsigned hashval;


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

注意，从这两个算法中可以清楚地看出，第一版哈希值如此糟糕的一个原因是它没有考虑字符串字符 秩序，因此 hash("ab")将返回与 hash("ba")相同的值。这是 没有，因此使用第二版散列，但是，这将(更好!)返回这些字符串的两个不同值。

std::unordered_map<>模板容器散列表使用的 GCC C + + 11散列函数是 好极了。

用于 unordered_map(哈希表模板)和 unordered_set(哈希集模板)的 GCC C + + 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: : unorder _ map 中使用的默认哈希函数是什么？。

参见

  1. 试用和测试的其他哈希表算法: http://www.cse.yorku.ca/~oz/hash.html。这里提到的哈希算法:
    1. Djb2
    2. 我不知道
    3. 损失(K & R 第一版)
小开

Djb2对于 这本466k 英语词典有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倍。分配更多的报酬递减会让你的哈希表更快，但是速度更快，让你的哈希表变得更小，这会让它以指数级的速度变慢。这是因为散列表有一个非线性 在空间和时间复杂性之间取舍，最佳负载因子为2-sqrt (2) = 0.58... ... 显然。

小开

我想核实一下卞的回答，可惜他没有发布代码。因此，我实现了一个小测试套件，并在 466K 英语单词列表上运行了不同的小散列函数，以查看每个函数的冲突数:

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(或 AArch64)体系结构上，有使用流行的 DJB2散列函数来处理字符串的 几乎没有意义。因为它比相似的函数(MurmurOAAT、 FNV和 Jenkins OAAT)具有更多的冲突，同时具有非常相似的吞吐量。伯恩斯坦的 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;
}

附言。在 Reini Urban (rUrban)的 SMHasher 存储库中可以找到对现代散列函数的速度和质量的更全面的回顾。注意表中的“质量问题”列。


提交答案