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

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

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

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

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

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

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

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

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

A hashtable^[1] is in principle the fastest way.

You could然而编译一个完美的哈希函数 http://en.wikipedia.org/wiki/Perfect_hash_function鉴于您提前知道完整的域名这一事实。

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

通过适当的调整，您可以

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

用于生成完美哈希函数的“老式”工具是gperf(1) http://www.gnu.org/software/gperf/。维基百科列出了有关该主题的更多资源。

因为所有的争论我运行了一个演示:

正在下载并从该集中获取 100 个随机样本，应用 gperf 如下：

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

结果哈希值 MAX_HASH_VALUE 为157 and a direct尽可能多的项目的字符串查找表。这是just用于演示目的的哈希函数：

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 https://gist.github.com/sehe/5433535

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

Q. [...] 显然是“DELL”。这种查找必须比“哈希图查找”快得多。

A:如果你使用一个简单的std::map最终效果是前缀搜索（因为第一个字符不匹配的字典字符串比较快捷方式）。在排序容器中进行二分查找也是如此。

^[1] PS. For 100 strings, a sorted array of string with std::search or std::lower_bound would potentially be as fast/faster due to the improved Locality of Reference http://en.wikipedia.org/wiki/Locality_of_reference. Consult your profile results to see whether this applies.