我正在寻找一种具有固定键的地图(在初始化期间固定),并可以更快地查找。它可能不支持添加/更新元素。是否有一些算法可以查看键列表并制定一个函数,以便以后更快地查找。在我的情况下,键是字符串。
更新:
键在编译时未知。但在应用程序的初始化时间内已经确定。之后将不会再进行插入,但会进行大量查找。因此,我希望优化查找。
更新:
键在编译时未知。但在应用程序的初始化时间内已经确定。之后将不会再进行插入,但会进行大量查找。因此,我希望优化查找。
CMPH可能是你正在寻找的东西。基本上这就是gperf
,但不需要在编译时设置。
当然,C++11中的std::unordered_map
也可能做到这一点,但可能会有一些碰撞。
由于您查找字符串,因此对于字符串,trie(任何不同的trie风格,crit-bit或任何奇怪的名称)也值得研究,特别是如果您有很多字符串。有许多免费的trie实现可供使用。
trie的优点在于它们可以索引压缩字符串,因此它们使用更少的内存,这具有更高的可能性将数据存储在缓存中。而且访问模式不太随机,这也是缓存友好的。哈希表必须存储值加哈希,并且在内存中索引更多或更少随机(不是完全随机,而是不可预测的)。trie / trie-like结构理想情况下只需要一个额外的位来区分每个节点中的键和其公共前缀。
(顺便说一句,O(log(N))在这种情况下可能比O(1)更快,因为大O不考虑这样的事情。)
std::unordered_map
是一种哈希映射。它在实际查找方面的时间复杂度为 O(1)
,但在字符串长度方面的时间复杂度为 O(N)
,并且它必须进行额外的 O(N)
比较。而 crit-bit 树或 trie 在关键字长度和关键字数量方面的时间复杂度均为 O(log(N))
。它不需要最终比较,在第一个不同的字节后也不需要触及数据,并且更加缓存友好,触及的页面更少。因此,答案并不是那么容易,哈希表_可能_确实不是最快的工具。 - Damon您可以尝试基于输入创建一个完美的哈希函数(即不具有输入集的冲突)。这是一个已经解决的问题(例如this,this)。然而,它们通常会生成源代码,并可能花费大量时间生成哈希函数。
这个问题的修改是使用通用哈希函数(例如移位乘加),并对合适的参数进行暴力搜索。
这必须与几个字符串比较的成本权衡(如果您不必整理,这些比较并不那么昂贵)。
另一个选择是使用两个不同的哈希函数-这增加了单个查找的成本,但使退化的可能性略微小于外星人窃取您的时钟周期。对于典型的字符串和良好的哈希函数,这很不可能成为问题。
尝试使用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.