c++ - 为查找优化的 HashMap

Question

我正在寻找一些具有固定键(在初始化期间固定)并且查找速度更快的 map 。它可能不支持稍后添加/更新元素。是否有一些算法可以查看键列表并制定一个函数，以便以后查找更快。在我的例子中，键是字符串。

更新:

key 在编译时是未知的。但是在应用程序的初始化期间。以后不会有任何进一步的插入，但会有很多查找。所以我想优化查询。

Answer 1

CMPH可能是你要找的。基本上这是 gperf 不需要在编译时设置。

当然，C++11 中的 std::unordered_map 也可能会这样做，尽管可能会发生一些冲突。

由于您查找字符串，对于字符串，特里树(任何不同的特里树风格、crit-bit 或它们拥有的任何时髦名称)也可能值得研究，尤其是当您有许多 其中。有很多免费的 trie 实现可以免费使用。
Tries 的优点是它们可以对字符串进行索引压缩，因此它们使用的内存更少，从而更有可能将数据放入缓存中。此外，访问模式的随机性较低，这也是缓存友好的。哈希表必须存储值加上哈希，并或多或少随机地(不是随机，而是不可预测地)索引到内存中。一个 trie/trie-like 结构在理想情况下只需要一个额外的位来区分每个节点中的键和它的公共(public)前缀。

(请注意，在这种情况下，O(log(N)) 很可能比 O(1) 更快，因为 big-O 不考虑类似的事情。)