为查找优化的哈希映射

Question

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

更新:

密钥在编译时是未知的.但在应用程序的初始化时间.以后不会再进行任何插入,但会有很多查找.所以我想要优化查找.

Answer 1

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

当然，std::unordered_mapC++11 也可能会这样做，尽管可能会有一些冲突。

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

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