对 C 哈希表有一个好的哈希函数吗？

Question

我需要 C++ 中面向性能的哈希函数实现，用于我将编码的哈希表。我已经环顾四周，只发现“一般”的问题是什么是好的散列函数。我考虑过 CRC32（但是在哪里可以找到好的实现呢？）和一些密码算法。不过，我的桌子有非常具体的要求。

下面是表格的样子：

 100,000 items max
200,000 capacity (so the load is 0.5)
hashing a 6-character string which is a part of English sentence
     examples: "become"    "and he"    ", not "

我的哈希表的 第一要务 是快速搜索（检索）。快速插入并不重要，但它会伴随着快速搜索而来。删除并不重要，我不会研究重新散列。为了处理冲突，我可能会使用 此处 描述的 _单独链接_。我已经看过 这篇文章，但想听听那些以前处理过此类任务的人的意见。

原文由 DV. 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

现在假设你想要一个哈希，并且想要一些在你的情况下可以工作的 快速 的东西，因为你的字符串只有 6 个字符长，你可以使用这个魔法：

 size_t precision = 2; //change the precision with this
size_t hash(const char* str)
{
   return (*(size_t*)str)>> precision;
}

CRC 用于慢动作 ;)

说明： 这通过将字符串指针的内容转换为“看起来像”一个 size_t（int32 或 int64 基于您的硬件的最佳匹配）来工作。因此字符串的内容被解释为原始数字，不再担心字符，然后您将其移位所需的精度（您将此数字调整为最佳性能，我发现 2 适用于散列字符串一套几千）。

此外，真正整洁的部分是现代硬件上的任何体面的编译器都会在 1 条汇编指令中散列这样的字符串，很难打败它；）

原文由 Robert Gould 发布，翻译遵循 CC BY-SA 2.5 许可协议

Answer 2

这个简单的多项式工作得非常好。我从 Microsoft Research 的 Paul Larson 那里得到它，他研究了各种散列函数和散列乘法器。

 unsigned hash(const char* s, unsigned salt)
{
    unsigned h = salt;
    while (*s)
        h = h * 101 + (unsigned) *s++;
    return h;
}

salt 应该在创建哈希表之前初始化为一些 随机 选择的值以防御 哈希表攻击。如果这对您来说不是问题，请使用 0。

表的大小也很重要，以尽量减少冲突。听起来你的很好。

原文由 George V. Reilly 发布，翻译遵循 CC BY-SA 3.0 许可协议