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

Question

我知道我不应该优化我的程序的每一个位置所以请认为这个问题是"学术的"

我有每个最多100个字符串和整数,类似的东西:

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

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

至少知道字符串是预先初始化的并且永远不会改变它应该可以"找到"导致"一篮子一项"映射的哈希函数,但可能还有其他黑客.

我能想象的一个优化 - 我只能读取第一个符号.例如,如果"DELL"是唯一以"D"开头的字符串,并且我收到了类似"D***"的内容,而不是我甚至不需要阅读字符串!它显而易见地"戴尔".这种查找必须比"hashmap lookup"快得多.(在这里,我假设我们只接收哈希中的符号,但并非总是如此)

我的问题是否有任何可以使用或易于实施的解决方案？我正在使用c ++和boost.

upd我检查并发现,对于我的交易限制,股票代码是12个符号,而不是如上所述的30个符号.然而,其他交换可能允许稍微长一些的符号,因此有一个算法可以继续处理多达20个字符长的代码,这很有意思.

Answer 1

哈希表^[1]原则上是最快的方式.

但是,你可以编译一个Perfect Hash函数,因为你事先知道完整的域名.

使用完美的哈希,不需要发生冲突,因此您可以将哈希表存储在线性数组中!

通过适当的调整,您可以

• 适合有限空间中的所有哈希元素,使直接寻址成为可能的选择
• 在O(1)中进行反向查找

用于生成Perfect Hash函数的"old-school"工具将是gperf(1).维基百科列出了有关该主题的更多资源.

由于所有的争论,我运行了一个演示:

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

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

产生一个哈希值MAX_HASH_VALUE 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

请注意,这也是一个完美的哈希,所以不会发生碰撞

问: [...] 显而易见的是"戴尔".这种查找必须比"hashmap lookup"快得多.

答:如果你使用简单std::map的净效果是前缀搜索(因为词典字符串比较快捷键对第一个字符不匹配).对于已排序容器中的二进制搜索,情况也是如此.

^[1] PS.对于100个字符串,由于改进的参考局部性,带有std::search或std::lower_bound可能快速/更快的字符串的排序数组.请查阅您的个人资料结果,看看是否适用.

Answer 2

对sehe的帖子的小补充:

如果你使用简单std::map的净效果是前缀搜索(因为词典字符串比较快捷键对第一个字符不匹配).对于已排序容器中的二进制搜索,情况也是如此.

您可以利用前缀搜索更高效.两个std::map和天真二进制搜索的问题在于它们将为每个单独的比较冗余地读取相同的前缀,使得整体搜索O(m log n)其中m是搜索字符串的长度.

这就是为什么hashmap比较大型集合的这两种方法的原因.但是,有一种数据结构不执行冗余前缀比较,实际上需要将每个前缀恰好比较一次:前缀(搜索)树,通常称为trie,查找长度为m的单个字符串是可行的在O(m)中,您获得具有完美散列的哈希表的相同渐近运行时.

具有完美散列的trie或(直接查找)哈希表是否更适合您的目的是分析问题.