35

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

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

4

9 回答 9

24

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

于 2009-03-10T03:37:22.740 回答
14

这个简单的多项式工作得非常好。我从 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。

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

于 2009-03-10T06:36:42.073 回答
6

Boost.Functional/Hash可能对你有用。我没有尝试过，所以我不能保证它的性能。

Boost 还有一个CRC 库。

我会先看一个Boost.Unordered（即 boost::unordered_map<>）。它对容器使用哈希映射而不是二叉树。

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

于 2009-03-10T03:10:36.313 回答
4

你的表的大小将决定你应该使用什么大小的散列。当然，您希望尽量减少碰撞。我不确定您通过最大项目和容量指定了什么（它们对我来说似乎是同一件事）在任何情况下，这些数字中的任何一个都表明 32 位哈希就足够了。您可能会摆脱 CRC16（约 65,000 种可能性），但您可能需要处理很多冲突。另一方面，冲突可能比 CRC32 哈希处理得更快。

我会说，选择 CRC32。您会发现不乏文档和示例代码。由于您已经确定了最大值并且速度是优先事项，因此请使用指针数组。使用哈希生成索引。碰撞时，增加索引直到你碰到一个空桶..快速而简单。

于 2009-03-10T03:17:31.617 回答
4

由于您存储英文单词，因此您的大多数字符都是字母，并且数据的最重要两位不会有太大变化。除此之外，我会保持它非常简单，只使用 XOR。毕竟，您不是在寻找加密强度，而只是在寻找合理均匀的分布。这些方面的东西：

size_t hash(const std::string &data) {
  size_t h(0);
  for (int i=0; i<data.length(); i++)
    h = (h << 6) ^ (h >> 26) ^ data[i];
  }
  return h;
}

除此之外，您是否将 std::tr1::hash 视为哈希函数和/或将 std::tr1::unordered_map 视为哈希表的实现？与实现自己的类相比，使用这些可能会节省很多工作。

于 2009-03-10T03:53:25.417 回答
2

如果您需要搜索短字符串并且插入不是问题，也许您可​​以使用 B-tree 或 2-3 树，在您的情况下通过散列不会获得太多收益。

这样做的方法是在每个节点中放置一个字母，因此首先检查节点“a”，然后检查“a”的子节点是否为“p”，它是“p”的子节点，然后是“ l”，然后是“e”。在你有“apple”和“apply”的情况下，你需要寻找最后一个节点，（因为唯一的区别是最后一个“e”和“y”）

但是在大多数情况下，您只需几步（“xylophone”=>“x”->“ylophone”）就可以得到单词，因此您可以像这样优化。这可能比散列更快

于 2009-03-10T03:12:01.117 回答
2

我的哈希表的第一要务是快速搜索（检索）。

那么您使用的是正确的数据结构，因为在哈希表中搜索是 O(1)！:)

CRC32 应该没问题。实现并不复杂，它主要基于 XOR。只要确保它使用一个好的多项式。

于 2009-03-10T03:25:08.447 回答
2

简单的事情怎么样：

// Initialize hash lookup so that it maps the characters
// in your string to integers between 0 and 31
int hashLookup[256];

// Hash function for six character strings.
int hash(const char *str)
{
    int ret = 0, mult = 1;
    for (const char *p = str; *p; *p++, mult *= 32) {
        assert(*p >= 0 && *p < 256);
        ret += mult * hashLookup[*p];
    }

    return ret;
}

这假定 32 位整数。它每个字符使用 5 位，因此哈希值中只有 30 位。也许，您可以通过为前一个或两个字符生成六位来解决此问题。如果你的字符集足够小，你可能不需要超过 30 位。

于 2009-03-10T03:27:24.603 回答
1

从 C++11 开始，C++ 提供了一个std::hash< string >( string ). 这可能是一个高效的散列函数，可为大多数字符串提供良好的散列码分布。

此外，如果您正在考虑实现哈希表，那么您现在应该考虑使用 C++ std::unordered_map。

于 2017-12-05T15:09:42.847 回答