string的散列函数
我正在使用C语言的哈希表，我正在testingstring的哈希函数。
我试过的第一个函数是添加ascii代码并使用模（％100），但是第一次testing数据的结果很差：130个单词有40个冲突。
最终的input数据将包含8 000个字（这是一个文件中的一个字典）。 散列表被声明为int table [10000]，并包含单词在txt文件中的位置。
第一个问题是哪个是散列string的最佳algorithm？ 以及如何确定哈希表的大小？
提前致谢 ！
🙂
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; }
首先，您通常不希望将哈希表使用encryption哈希。 密码标准algorithm非常快，哈希表标准仍然非常慢。
其次，您要确保input的每一位都可以影响结果。 一个简单的方法就是将当前结果旋转一些比特位，然后将当前哈希码与当前字节进行异或运算。 重复，直到到达string的末尾。 请注意，您通常不希望旋转为字节大小的偶数倍。
例如，假设8位字节的常见情况，您可能会旋转5位：
int hash(char const *input) { int result = 0x55555555; while (*input) { result ^= *input++; result = rol(result, 5); } }
编辑：另请注意，对于散列表大小，10000个插槽很less是个不错的select。 你通常需要两件事情之一：你可能需要一个素数作为大小（要求确保某些types的散列分辨率的正确性），否则就是2的幂（所以把值减小到正确的范围可以用一个简单的位掩码）。
维基百科显示一个不错的string哈希函数，称为jenkins一个时间哈希。 它还引用了这个散列的改进版本。
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中的散列表实现，这些也提供了预先构build的散列函数。 我强烈build议使用这些，而不是发明自己的散列表或散列函数; 对于常见的使用情况，他们已经进行了大量优化。
但是，如果数据集是静态的，那么最好的解决scheme可能是使用完美的散列 。 gperf会为给定的数据集生成一个完美的哈希值。
首先，130个单词的40个碰撞散列为0..99坏了？ 如果你不专门采取措施，你不能期望完美的散列。 大多数情况下，普通的散列函数不会比随机生成器具有更less的冲突。
具有良好声誉的散列函数是MurmurHash3 。
最后，关于散列表的大小，它确实取决于你想要什么types的散列表，特别是存储区是可扩展的还是单插槽的。 如果存储桶是可扩展的，那么还有一个select：为存储/速度约束select平均存储桶长度。
我已经试过这些散列函数，并得到以下结果。 我有大约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％的数据冲突率。
有一件事我用了很好的结果是（我不知道它是否已经提到，因为我不记得它的名字）。
您预先为您的密钥字母表中的每个字符使用一个随机数预先计算表T [0,255]。 你用T [k0] xor T [k1] xor … xor T [kN]来散列你的密钥'k0 k1 k2 … kN'。 你可以很容易地发现，这与随机数发生器一样随机，而且在计算上非常可行，如果你真的遇到了一个非常糟糕的例子，那么你可以用一批新的随机数重复整个事件。
虽然djb2 ，如djb2 上的stackoverflow所示 ，几乎可以肯定会更好，但我认为值得展示K＆R哈希：
1）显然是一个可怕的哈希algorithm，如K＆R第1版（ 来源 ）
unsigned long hash(unsigned char *str) { unsigned int hash = 0; int c; while (c = *str++) hash += c; return hash; }
2）可能是一个相当不错的哈希algorithm，如K＆R版本2 （本书第144页所validation）所示; 注意：如果你计划在散列algorithm之外进行模数调整到你的数组长度，一定要从return语句中删除% HASHSIZE 。 此外，我build议你使返回和“hashval”typesunsigned long而不是简单的unsigned （整数）。
unsigned hash(char *s) { unsigned hashval; for (hashval = 0; *s != '\0'; s++) hashval = *s + 31*hashval; return hashval % HASHSIZE; }
注意，从这两种algorithm中可以清楚地看出，第一版哈希值太糟糕的原因之一是因为它没有考虑string字符顺序 ，所以hash("ab")因此会返回与hash("ba")相同的值。 这不是第二版散列，但是，这将（更好！）为这些string返回两个不同的值。
用于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; }
