针对查找进行优化的哈希表

Question

我正在寻找一种具有固定键的地图（在初始化期间固定），并可以更快地查找。它可能不支持添加/更新元素。是否有一些算法可以查看键列表并制定一个函数，以便以后更快地查找。在我的情况下，键是字符串。

更新：

键在编译时未知。但在应用程序的初始化时间内已经确定。之后将不会再进行插入，但会进行大量查找。因此，我希望优化查找。

- balki

---

请查看gperf，它可以在编译时为哈希表中所有已知键提供完美哈希。 - Seth Carnegie

Answer 1

CMPH可能是你正在寻找的东西。基本上这就是gperf，但不需要在编译时设置。

当然，C++11中的std::unordered_map也可能做到这一点，但可能会有一些碰撞。

由于您查找字符串，因此对于字符串，trie（任何不同的trie风格，crit-bit或任何奇怪的名称）也值得研究，特别是如果您有很多字符串。有许多免费的trie实现可供使用。
trie的优点在于它们可以索引压缩字符串，因此它们使用更少的内存，这具有更高的可能性将数据存储在缓存中。而且访问模式不太随机，这也是缓存友好的。哈希表必须存储值加哈希，并且在内存中索引更多或更少随机（不是完全随机，而是不可预测的）。trie / trie-like结构理想情况下只需要一个额外的位来区分每个节点中的键和其公共前缀。

（顺便说一句，O(log(N))在这种情况下可能比O(1)更快，因为大O不考虑这样的事情。）

- Damon

---

Trie 对于字符串（也称为 std::string 或 std::basic_string<char>）而言比 std::unordered_map 慢得多。已经使用不同的优化标志进行了测试。而且互联网上也有很多相关报告。 - cppist

@cppist: 这取决于实现和数据集（包括大小和实际数据）。std::unordered_map是一种哈希映射。它在实际查找方面的时间复杂度为 O(1)，但在字符串长度方面的时间复杂度为 O(N)，并且它必须进行额外的 O(N) 比较。而 crit-bit 树或 trie 在关键字长度和关键字数量方面的时间复杂度均为 O(log(N))。它不需要最终比较，在第一个不同的字节后也不需要触及数据，并且更加缓存友好，触及的页面更少。因此，答案并不是那么容易，哈希表_可能_确实不是最快的工具。 - Damon

N是单词数量。C是碰撞数量。S是字符串长度。Trie用于O1（S）的字符串搜索。哈希集用于H = O2（S）+ O3（C）的字符串搜索。但是，O1（S）比O2（S）大得多。哈希集在连续数据下使用简单算术运算。但是trie使用多个解除引用和if-branches。即使解除引用和分支比简单算术更快，通用处理器也比不连贯的顺序数据更好地工作。良好制作的直接trie确实比unordered_map aka哈希集慢。至少对于（char）字符串。 - cppist

Answer 2

请注意，这些是不同的事情：您需要一个上限吗？您需要一个快速的典型速率吗？还是您需要最快的查找，无需任何问题？最后一个选项会花费您更多的代价，前两个选项可能存在冲突的目标。

---

您可以尝试基于输入创建一个完美的哈希函数（即不具有输入集的冲突）。这是一个已经解决的问题（例如this，this）。然而，它们通常会生成源代码，并可能花费大量时间生成哈希函数。

这个问题的修改是使用通用哈希函数（例如移位乘加），并对合适的参数进行暴力搜索。

这必须与几个字符串比较的成本权衡（如果您不必整理，这些比较并不那么昂贵）。

另一个选择是使用两个不同的哈希函数-这增加了单个查找的成本，但使退化的可能性略微小于外星人窃取您的时钟周期。对于典型的字符串和良好的哈希函数，这很不可能成为问题。

- peterchen

---

+1 是因为你考虑了“你需要一个上限吗”的问题，再加上你的最后一段。你在最后一段描述的基本上是布谷鸟哈希。正如你所说，它对于单个查找（以及插入）来说速度较慢，但它保证了最坏情况下的上限，如果有这个要求，那就非常棒。 - Damon

Answer 3

尝试使用google-sparsehash：http://code.google.com/p/google-sparsehash/

An extremely memory-efficient hash_map implementation. 2 bits/entry overhead! 
The SparseHash library contains several hash-map implementations, including 
implementations that optimize for space or speed.

- Lei Mou

Answer 4

在一个类似的主题（编译时已知项目数）中，我制作了这个：已知整数键集上的查找。低开销，无需完美哈希。幸运的是，它是用C编写的;-)

- wildplasser