C++：预计有很多未命中：map vs unordered_map

Question

我不熟悉 C++ 中的工具。如果这个问题听起来很垃圾，请原谅我。

从map.find()的doc开始，复杂度为O(log(N))。这似乎暗示了实现中的树结构。

从 unordered_map.find() 的 doc 开始，平均复杂度是恒定的，而最坏情况是 O(N)。这似乎是一个散列-table.

我正在寻找一种地图，可以让我：

1. 预分配内存，即我确切知道有多少项目将进入地图
2. 当在地图中找不到大量查询时性能良好，我知道这会在我的用例中发生

unordered_map 满足 (1) 与 unordered_map.rehash，但未找到的查询可能需要很长时间。 map 似乎对未找到的查询有更好的性能，但没有预分配内存功能。有什么建议吗？

Answer 1

只有一个固定数量的项目往往暗示您要插入一些特定的项目，然后将它们留在集合中直到完成.

如果是这样的话，我可能会将这些项目放入 std::vector 中并进行排序。然后，如果分布reasonably predictable，则使用插值搜索，否则使用二分搜索。

只要您不需要 insert/delete 更多项并保持顺序，这通常比树快很多，即使您使用二进制搜索，只是因为数据是连续的。

鉴于您预计在搜索中会出现相当多的遗漏，我会考虑将哈希 table (unordered_map) 设置为极低的负载系数，以便绝大多数有时，您会对密钥进行哈希处理，如果不存在，您很有可能会落在一个空的哈希桶上，因此您会很快收到搜索失败的指示。您可以使用 max_load_factor().

设置加载因子

Answer 2

A Bloom Filter is good for situations where you expect a lot of misses. It's kind of like a hash table, except that it uses multiple hashes and doesn't actually store the items in the table, just a bit to tell you if the item is not part of the collection. It will tell you very quickly if there's a miss, then you need a secondary method (such as the one suggested by ) 如果过滤器指示可能的匹配项，则进行第二次查找。