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

StackOverflow https://stackoverflow.com/questions/628790

  •  07-07-2019
  •  | 
  •  

题

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

这 第一优先 我的哈希表的特点是快速搜索（检索）。快速插入并不重要，但它会伴随着快速搜索。删除并不重要，重新散列也不是我会研究的事情。为了处理碰撞，我可能会使用 单独链接 如上所述 这里. 。我已经看过了 本文, ，但想听听以前处理过此类任务的人的意见。

有帮助吗？

解决方案

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

其他提示

这个简单的多项式非常有效。我是从微软研究院的Paul Larson那里学到的，他研究了各种散列函数和散列乘法器。

unsigned hash(const char* s, unsigned salt)
{
    unsigned h = salt;
    while (*s)
        h = h * 101 + (unsigned) *s++;
    return h;
}
在创建哈希表之前，应将

salt初始化为某些随机选择的值以防止哈希表攻击。如果这对您来说不是问题，请使用0。

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

Boost.Functional / Hash 可能是用到你。我没试过，所以我不能保证它的表现。

Boost还有一个 CRC库。

我先看一下 Boost.Unordered （即boost :: unordered_map <！> lt; <！> gt;）。它使用哈希映射而不是二进制树作为容器。

我相信一些STL实现有一个hash_map <！> lt; <！> gt; stdext命名空间中的容器。

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

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

由于您存储英文单词，因此您的大多数字符都是字母，并且数据的最重要的两位不会有太大的变化。除此之外，我会保持它非常简单，只需使用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作为哈希表的实现？使用这些可能会节省很多与实现自己的类相反的工作。

  

哈希表的首要任务是快速搜索（检索）。

那么你使用正确的数据结构，因为在哈希表中搜索是O（1）！ ：）

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

简单的事情：

// 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位。

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

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

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

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

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top