5

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

更新：

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

4

4 回答 4

2

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

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

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

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

于 2011-12-08T10:21:06.403 回答
1

请注意，这些是不同的事情：您是否需要一个上限，您是否需要一个快速的典型速率，或者您是否需要有史以来最快的查找，没有问题？最后一个会让你付出代价，前两个可能是相互冲突的目标。

您可以尝试根据输入创建一个完美的散列函数（即没有输入集冲突的散列函数）。这是一个以某种方式解决的问题（例如this，this）。但是，它们通常会生成源代码，并且可能会花费大量时间来生成散列函数。

对此的修改将使用通用散列函数（例如移位乘加）并对合适的参数进行强力搜索。

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

另一种选择是使用两个不同的散列函数——这增加了单次查找的成本，但与外星人窃取你的时钟周期相比，降级的可能性略小。这不太可能是典型字符串和体面的散列函数的问题。

于 2011-12-08T10:36:29.880 回答
0

尝试 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.
于 2011-12-08T10:21:01.740 回答
0

在一个类似的主题（编译时已知的（数量）项）中，我制作了这个：Lookups on known set of integer keys。低开销，不需要完美的哈希。幸运的是，它在 C 语言中；-)

于 2011-12-08T14:46:26.247 回答