c++ - 是否可以比使用 hashmap 更快地将字符串映射到 int？

Question

我知道我不应该优化我的程序的每一个地方，所以请把这个问题看作是“学术的”

我每个人最多有 100 个字符串和整数，如下所示：

MSFT 1
DELL 2
HP   4
....
ABC  58

这个集合是预初始化的，这意味着一旦创建它就永远不会改变。在 set 初始化后，我使用它非常密集，因此可以快速查找。字符串很短，最多 30 个字符。映射int也是有限的，在 1 到 100 之间。

至少知道字符串是预初始化的并且永远不会更改，应该可以“找到”导致“一个篮子一个项目”映射的哈希函数，但可能还有其他黑客攻击。

我可以想象的一个优化 - 我只能读取第一个符号。例如，如果“DELL”是唯一以“D”开头的字符串，而我收到了“D***”之类的内容，那么我什至不需要读取该字符串！它显然是“戴尔”。这种查找必须比“hashmap 查找”快得多。（这里我假设我们只收到散列中的符号，但并非总是如此）

是否有任何现成或易于实施的解决方案来解决我的问题？我正在使用 c++ 和 boost。

upd我检查并发现我的股票交易限制是 12 个符号，而不是上面提到的 30 个。然而，其他交易所可能允许稍长的符号，因此有趣的算法将继续处理长达 20 个字符的长代码。

score 38 · Accepted Answer

哈希表^[1]原则上是最快的方法。

但是，鉴于您提前知道完整的域，您可以编译一个完美的哈希函数。

有了完美的哈希，就不会发生冲突，因此您可以将哈希表存储在线性数组中！

通过适当的调整，您可以

将所有散列元素放在有限的空间中，使直接寻址成为一种潜在的选择
在 O(1) 中进行反向查找

用于生成完美哈希函数的“老派”工具是gperf(1)。维基百科列出了有关该主题的更多资源。

由于所有的辩论，我运行了一个演示：

下载NASDAQ 股票代码并从该集合中获取 100 个随机样本，应用 gperf 如下：

gperf -e ' \015' -L C++ -7 -C -E -k '*,1,$' -m 100 selection > perfhash.cpp

产生一个哈希值 MAX_HASH_VALUE157和一个包含尽可能多项目的直接字符串查找表。这里只是用于演示目的的哈希函数：

inline unsigned int Perfect_Hash::hash (register const char *str, register unsigned int len) {
  static const unsigned char asso_values[] = {
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156,  64,  40,   1,  62,   1,
       41,  18,  47,   0,   1,  11,  10,  57,  21,   7,
       14,  13,  24,   3,  33,  89,  11,   0,  19,   5,
       12,   0, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156
    };
  register int hval = len;

  switch (hval) {
      default: hval += asso_values[(unsigned char)str[4]];   /*FALLTHROUGH*/
      case 4:  hval += asso_values[(unsigned char)str[3]];   /*FALLTHROUGH*/
      case 3:  hval += asso_values[(unsigned char)str[2]+1]; /*FALLTHROUGH*/
      case 2:  hval += asso_values[(unsigned char)str[1]];   /*FALLTHROUGH*/
      case 1:  hval += asso_values[(unsigned char)str[0]];   break;
  }
  return hval;
}

它真的没有变得更有效率。请查看github 上的完整源代码：https://gist.github.com/sehe/5433535

请注意，这也是一个完美的哈希，所以不会有冲突

问：[...]显然是“DELL”。这种查找必须比“hashmap 查找”快得多。

A：如果您使用简单std::map的净效应是前缀搜索（因为第一个字符不匹配的字典字符串比较快捷方式）。排序容器中的二进制搜索也是如此。

^[1] 附言。对于 100 个字符串，由于改进的Locality of Referencestd::search ，具有or的排序字符串数组可能会一样快/更快。请查阅您的个人资料结果以查看这是否适用。std::lower_bound

score 19 · Accepted Answer

对sehe帖子的小补充：

如果您使用简单std::map的净效果是前缀搜索（因为第一个字符不匹配的字典字符串比较快捷方式）。排序容器中的二进制搜索也是如此。

您可以利用前缀搜索来提高效率。简单二分搜索的问题std::map在于，它们会为每个单独的比较重复读取相同的前缀，从而使整体搜索 O( m log n )，其中m是搜索字符串的长度。

这就是为什么 hashmap 在大集合中胜过这两种方法的原因。但是，有一种数据结构不进行冗余前缀比较，实际上每个前缀只需要比较一次：前缀（搜索）树，通常称为trie，查找长度为m的单个字符串是可行的在 O( m ) 中，与完美散列的散列表相同的渐近运行时间。

对于您的目的而言，具有完美散列的 trie 或（直接查找）散列表是否更有效是分析的问题。

score 1 · Accepted Answer

是的！

哈希必须遍历您的字符串并构建哈希值。在使用链接[ Wiki:Trie ]中解释的 trie 时，只需要遵循链接结构上的路径，而无需任何过度计算。如果它是压缩的特里，如页面末尾所述，当首字母是一个单词时（您谈到的 DELL 案例），它会计算一个案例。预处理稍高一些，但在运行时提供最佳性能。

更多优点：
1.如果您要查找的字符串不存在，您知道在第一个字符中与现有字符串不同（不需要继续计算）
2. 实施后，添加更多字符串特里是直截了当的。

score 0 · Accepted Answer

好吧，您可以将字符串存储在二叉树中并在那里搜索。虽然这具有O(log n)理论上的性能，但如果您只有几个键，它们真的很长，并且在前几个字符中已经不同，那么在实践中它可能会快得多。

即比较键比计算散列函数更便宜。

此外，还有 CPU 缓存效应等可能（或可能不会）有益。

但是，使用相当便宜的哈希函数，哈希表将很难被击败。

score 0 · Accepted Answer

如上所述的标准散列映射以及完美的散列函数都受到散列函数本身执行相对较慢的影响。绘制的完美散列函数例如对一个数组有多达 5 次随机访问。

测量或计算散列函数和字符串比较的速度是有意义的，假设功能是通过一个散列函数评估、一个表中的查找以及通过包含字符串及其索引的（链接）列表进行线性搜索来完成的解决哈希冲突。在许多情况下，最好使用更简单但更快的散列函数并接受更多的字符串比较，而不是使用更好但更慢的散列函数并且具有更少（标准散列映射）甚至只有一个（完美散列）比较。

您会在我的网站上找到有关“switch on string”主题的讨论，以及使用宏作为免费 C/C++ 源的通用测试平台的一系列解决方案，这些解决方案可以在运行时解决问题。我也在考虑一个预编译器。

score 0 · Accepted Answer

sehe's（然而）回答的另一个小补充：

除了 Perfect Hash Functions，还有这个 Minimal Perfect Hash Function 的东西，分别是C Minimal Perfect Hash Function. 它几乎与相同gperf，除了：

gperf 有点不同，因为它旨在为小密钥集创建非常快速的完美哈希函数，而 CMPH 库旨在为非常大的密钥集创建最小完美哈希函数

CMPH 库将最新和更高效的算法封装在一个易于使用、生产质量、快速的 API 中。该库旨在处理无法放入主内存的大条目。它已成功用于为具有超过 1 亿个键的集合构建最小完美哈希函数，我们打算将这个数字扩展到十亿个键的数量级

来源：http ://cmph.sourceforge.net/

score -2 · Accepted Answer

如果字符串在编译时已知，则可以使用枚举：

enum
{
  Str1,
  Str2
};

const char *Strings = {
  "Str1",
  "Str2"
};

使用一些宏技巧，您可以消除在两个位置重新创建表的冗余（使用文件包含和#undef）。

然后可以像索引数组一样快地实现查找：

const char *string = Strings[Str1]; // set to "Str1"

这将具有最佳查找时间和参考位置。

c++ - 是否可以比使用 hashmap 更快地将字符串映射到 int？

7 回答 7

Related

Reference