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

Question

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

这就是 table 的样子:

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 "

我的哈希表的第一优先是快速搜索(检索)。快速插入并不重要，但它会伴随着快速搜索而来。删除并不重要，我不会研究重新散列。为了处理冲突，我可能会按照 here 的描述使用单独的链接。 .我已经看过 this article ，但想听听以前处理过此类任务的人的意见。

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 条汇编指令中散列这样的字符串，很难打败它；)