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

Question

我知道我不应该优化我的程序的每一个点，所以请考虑这个问题是“学术性的”

我最大有100个字符串和整数，每个都是这样的：

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

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

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

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

对于我的问题，是否有任何现成的或易于实施的解决方案？我使用c和助推。

我检查了一下，发现我对股票代码的交换限制是12个符号，而不是上面提到的30个。然而，其他交易所可能允许稍微长的符号，所以让算法继续处理多达20个字符的长股票代码是很有趣的。

Answer 1

对

哈希必须遍历字符串并生成哈希值。当使用链接[Wiki:trie]中解释的trie时，只需要遵循链接结构上的路径，而不需要任何过度计算。如果是压缩trie，如本页末尾所述，当首字母代表一个单词时，它会考虑计数一个案例（您提到的戴尔案例）。预处理稍高，但在运行时性能最佳。

还有一些优点：
1。如果您要查找的字符串不存在，您知道第一个字符与现有字符串不同（不需要继续计算）
2。实现后，直接向trie添加更多字符串。

Answer 2

sehe帖子的小补充：

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

您可以利用前缀搜索来提高效率。std：：map和朴素二进制搜索的问题是，对于每个单独的比较，它们都会冗余地读取相同的前缀，使得整体搜索为O（m log n），其中m是搜索字符串的长度。

这就是为什么hashmap在大型集上胜过这两种方法的原因。然而

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

Answer 3

原则上，哈希表是最快的方式。

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

有了完美的散列，就不需要冲突，所以可以将散列表存储在线性数组中！

通过适当的调整，你可以

• 将所有哈希元素放在有限的空间中，使直接寻址成为一个潜在选项
• 在O（1）中进行反向查找

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

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

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

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

结果是哈希值MAX\u hash\u值为157，并且直接字符串查找表包含尽可能多的项。以下是用于演示的哈希函数：

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

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

Q、 […]这显然是“戴尔”。这种查找必须比“hashmap查找”快得多。

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

^[1]PS。对于100个字符串，由于改进了引用位置，使用std::search或std::lower_bound的排序字符串数组可能会同样快/更快。请查阅您的配置文件结果，看看这是否适用。