有一个很好的哈希函数的C++哈希表？

我需要在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 "

的首要任务我哈希表的是快速搜索(检索).快速插入并不重要,但它会伴随快速搜索.删除并不重要,重新哈希不是我要研究的东西.为了处理冲突,我可能会使用这里描述的单独链接.我已经看过这篇文章了,但是想要对那些曾经处理过这样的任务的人提出意见.

1> Robert Gould..：

---

现在假设你想要一个哈希,并想要一些在你的情况下可以工作的快速的东西,因为你的字符串只有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个汇编指令中散列这样的字符串,很难被击败;)

---

请注意,这不会像在64位硬件上编写的那样工作,因为强制转换最终会使用str [6]和str [7],它们不是字符串的一部分.此外,在32位硬件上,您只使用字符串中的前四个字符,因此可能会遇到很多冲突.

---

我不知道这是一个好算法.哈希输出非常线性地增加.根本没有雪崩效应......

2> George V. Re..：

---

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

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

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

表的大小也很重要,以尽量减少碰撞.听起来像你的很好.

---

如果你能保证你的字符串总是6个字符长,毫无例外,那么你可以尝试展开循环.

3> Ferruccio..：

---

Boost.Functional/Hash可能对您有用.我没试过,所以我不能保证它的性能.

Boost还有一个CRC库.

我先看一下Boost.Unordered(即boost :: unordered_map <>).它使用哈希映射而不是二进制树作为容器.

我相信一些STL实现在stdext命名空间中有一个hash_map <>容器.