c++ - 专门的哈希表 C++

Question

我需要计算很多不同的项目。我正在处理一个配对列表，例如：

A34223,34
B23423,-23
23423212,16

我打算做的是将第一个值（键）散列成一个 32 位整数，然后它将成为稀疏结构的键，其中“值”将被添加（全部从零开始）数字并且为负数。

鉴于它们的密钥很短且是字母数字，有没有办法在 32 位 x86 架构上生成快速的哈希算法？或者是否存在现有的合适哈希？

我对散列的设计一无所知，但希望由于输入简单，有一种方法可以生成高性能散列，以保证在给定的“X”键长度下不会发生冲突并且具有高分散性所以当长度超过“X”时最小化碰撞。

Answer 1

当您使用 C++ 时，您应该做的第一件事是使用 std::map 创建一个简单的实现。它是否足够快（可能会）？如果是这样，请坚持下去，否则请调查您的 C++ 实现是否提供了哈希表。如果是这样，请使用它来创建一个简单的实现、测试、计时。速度够快吗（几乎可以肯定）？

只有在您用尽了这些选项之后，您才应该考虑实现自己的哈希表和哈希函数。

Answer 2

保证没有碰撞是困难的。

在你的情况下，钥匙

A34223
B23423
23423212

可以毫不费力地将其转换为 32 位整数。

这是一个从字符串生成哈希的好函数：

/**
 *  "The Practice of Programming", Hash Tables, section 2.9, pg. 57
 *
 *  computes hash value of string
 */
DWORD
strhash( char* str )
{
  //#define MULTIPLIER 31 or 37
  unsigned int   h;
  unsigned char* p;

  h = 0;
  for ( p=(unsigned char*)str; *p != '\0'; p++ )
    h = 31 * h + *p; // <- FIXED MULTIPLIER

  return h;
}

Answer 3

检查Bob Jenkins 的网站以获得良好的哈希函数。IIRC 它与 Perl 中使用的哈希相同。