我明白我不应该优化我的程序的每一个地方，所以请把这个问题视为"学术"
我最多有100个字符串和每个字符串的整数，就像这样:
MSFT 1
DELL 2
HP 4
....
ABC 58
这个集合是预先初始化的，这意味着一旦创建它就永远不会改变。set初始化后，我大量使用它，所以快速查找很好。字符串非常短，最多30个字符。映射的int也是有限的，在1到100之间。
至少知道字符串是预先初始化的，永远不会改变，应该可以"找到"导致"一篮一项"映射的哈希函数，但可能还有其他hack。
我能想到的一个优化-我只能读取第一个符号。例如，如果"DELL"是唯一以"D"开头的字符串，而我收到了类似"D***"的内容，那么我甚至不需要读取该字符串!显然是"戴尔"。这种查找必须比"哈希map查找"快得多。(这里我假设我们只接收到哈希中的符号，但情况并非总是如此)
对于我的问题是否有现成的或易于实现的解决方案?我正在使用c++和boost。
upd我检查了一下，发现我的股票交易限制是12个符号，而不是上面提到的30个。然而，其他交易所可能允许稍长的符号，所以有一种算法可以继续在长达20个字符的代码上工作是很有趣的。
哈希表[1]原则上是最快的方法。
你可以编译一个完美的哈希函数，因为你提前知道了完整的域。
对于一个完美的哈希，不需要有冲突，所以你可以将哈希表存储在一个线性数组中!
通过适当的调整，你可以
- 在有限的空间中适合所有的哈希元素，使直接寻址成为一个潜在的选项
- 在0 (1) 中有反向查找
生成完美哈希函数的"老派"工具是gperf(1)。维基百科列出了有关该主题的更多资源。
因为所有的争论我运行了一个演示:
下载纳斯达克股票代码并从该集合中随机抽取100个样本，应用gperf如下:
gperf -e ' 15' -L C++ -7 -C -E -k '*,1,$' -m 100 selection > perfhash.cpp生成
157的哈希值MAX_HASH_VALUE和包含同样多项的直接字符串查找表。下面的只是散列函数，用于演示: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。[…显然是"DELL"。这样的查找必须比"hashmap查找"快得多。
A:如果你使用一个简单的std::map，净效果是前缀搜索(因为字典字符串比较快捷键上的第一个字符不匹配)。对于排序容器中的二进制搜索也是如此。
<一口>[1]
p 。对于100个字符串，具有std::search或std::lower_bound的字符串排序数组可能会更快，因为改进了引用的局部性。参考您的概要结果，看看这是否适用。
对她的帖子的小补充:
如果您使用一个简单的
std::map，净效果是前缀搜索(因为字典字符串比较快捷键对第一个字符不匹配)。对于排序容器中的二进制搜索也是如此。
您可以利用前缀搜索来提高效率。std::map和朴素二进制搜索的问题是，它们将为每个单独的比较读取相同的冗余前缀，使整体搜索O(m log n)，其中m是搜索字符串的长度。
这就是为什么hashmap在大集合上胜过这两种方法的原因。然而，有一种数据结构不执行冗余的前缀比较，实际上需要对每个前缀精确地进行一次比较:前缀(搜索)树，更常见的是trie，查找长度m的单个字符串在O(m)中是可行的，这与您获得具有完美哈希的哈希表的渐进运行时间相同。
对于你的目的来说，到底是一个trie还是一个(直接查找)哈希表更有效，这是一个分析的问题。
(Yet) sehe's的另一个小答案:
除了完美哈希函数，还有这个最小完美哈希函数，分别是C Minimal Perfect Hash Function。它几乎与gperf相同，除了:
gperf有点不同，因为它被认为是为小的键集创建非常快速的完美哈希函数，而CMPH库被认为是为非常大的键集创建最小的完美哈希函数
CMPH库在一个易于使用，生产质量，快速的API中封装了最新和更有效的算法。该库被设计用于处理主存无法容纳的大条目。它已经成功地用于构造具有超过1亿个键的集合的最小完美哈希函数，并且我们打算将这个数字扩展到十亿数量级
来源:http://cmph.sourceforge.net/
是的!
Hash必须遍历字符串并构建一个哈希值。当使用链接[Wiki: trie]中解释的trie时，只需要遵循链接结构上的路径，而不需要任何过度计算。如果它是压缩的，就像在页面末尾解释的那样，当首字母是一个单词时，它会计算一个case(你提到的DELL案例)。预处理稍微高一些，但在运行时提供最佳性能。
更多优点:
1. 如果你要查找的字符串不存在，你知道在第一个字符中与现有字符串不同(不需要继续计算)
2. 在实现之后，向trie中添加更多的字符串是很直接的。
可以将字符串存储在二叉树中并在那里进行搜索。虽然这具有O(log n)的理论性能，但如果您只有几个键，并且非常长，并且在前几个字符中已经有所不同，则可能在实践中要快得多。
。当比较键比计算哈希函数便宜时
此外，CPU缓存效果可能(也可能不是)是有益的。
然而，使用一个相当便宜的哈希函数，哈希表将很难被击败。
标准哈希映射以及上面提到的完美哈希函数都受到哈希函数本身执行速度相对较慢的影响。例如，草图中的完美哈希函数可以对数组进行多达5次随机访问。
测量或计算哈希函数和字符串比较的速度是有意义的，假设该功能是由一个哈希函数求值，一个表查找和一个(链接)列表的线性搜索(包含字符串及其索引)来解决哈希冲突。在许多情况下，使用一个更简单但更快的哈希函数并接受更多的字符串比较比使用一个更好但更慢的哈希函数和更少的(标准哈希映射)甚至只有一个(完美哈希)比较要好。
你会在我的网站上找到一个关于"打开字符串"的相关主题的讨论，以及一堆使用通用测试平台的解决方案，使用宏作为免费的C/c++源，在运行时解决问题。我也在考虑一个预编译器。
如果字符串在编译时已知，则只需使用枚举:
enum
{
Str1,
Str2
};
const char *Strings = {
"Str1",
"Str2"
};
使用一些宏技巧可以消除在两个位置重新创建表的冗余(使用文件包含和#undef)。
那么查找可以像索引数组一样快:
const char *string = Strings[Str1]; // set to "Str1"
这将具有最佳的查找时间和引用位置。