我了解我不应该优化程序的每个位置，因此请认为该问题是“学术性的”
我每个人最多有100个字符串和整数，像这样：
MSFT 1 DELL 2 HP 4 .... ABC 58
此集已预先初始化，这意味着创建后就不会更改。set初始化后，我会非常密集地使用它，因此可以快速进行查找。字符串很短，最多30个字符。映射int也受到限制，并且在1到100之间。
int
至少知道字符串是预先初始化的且永不更改的，应该有可能“找到”散列函数，从而导致“一篮子一项目”的映射，但是可能还有其他黑客。
我能想到的一种优化-我只能读第一个符号。例如，如果“ DELL”是唯一以“ D”开头的字符串，并且我收到了类似“ D ***”的信息，那么我甚至不需要读取该字符串！显然是“ DELL”。这种查找必须比“哈希映射查找”快得多。（在这里，我假设我们只接收散列中的符号，但并非总是如此）
有没有可以立即使用或易于实施的解决方案来解决我的问题？我正在使用c ++和boost。
upd 我检查了一下，发现我的股票交易限额为12个符号，而不是如上所述的30个符号。但是，其他交易所可能允许使用略长的符号，因此有趣的是，该算法将继续处理多达20个字符的长行情记录器。
哈希表[1]原则上是最快的方法。
您 可以 然而编译一个完美的哈希函数因为你知道时间的全域超前的事实。
有了完美的哈希，就不会发生冲突，因此您可以将哈希表存储在线性数组中！
通过适当的调整，您可以
生成Perfect Hash函数的“老派”工具将是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 请注意，这也是完美的哈希，因此 不会发生冲突
由于所有辩论， 我进行了一个演示 ：
下载纳斯达克股票代码并从该集合中获取100个随机样本，应用gperf如下：
gperf -e ' \015' -L C++ -7 -C -E -k '*,1,$' -m 100 selection >
perfhash.cpp
结果为哈希值MAX_HASH_VALUE 157和 直接 字符串查找表，其中包含多个项目。这 只是 用于演示目的的哈希函数：
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
请注意，这也是完美的哈希，因此 不会发生冲突
问 ： 这显然是“ DELL”。 这种查找必须比“哈希映射查找”快得多。
答： 如果您使用简单std::map的字词，则最终效果是前缀搜索（因为第一个字符不匹配的词典字符串比较快捷方式）。在已排序的容器中进行二进制搜索也是如此。
std::map
[1] PS 。对于100个字符串，由于改善 了“引用的本地性”， 使用std::search或排序的字符串数组std::lower_bound可能会变得越来越快。查阅您的个人资料结果以查看是否适用。
std::search
std::lower_bound
