c++ - map 和 unordered_map

Question

我的问题更多是出于学习目的而非调试目的:

我目前正在优化我的一个小游戏的代码，我想知道:

我在我的程序中使用 map 来分配一些值，那么 unordered_map 在使用上是否比 map 更快？

(顺便说一句，对不起我的英语，这不是我的母语!)

Answer 1

std::unordered_map 是一个“hash_map”，这意味着搜索它是 O(1)，其中 std::map 是一个红黑树，搜索是 O(log2(n))。因此，如果您有 1000 个元素，区别在于在找到“正确”的那个之前查看 std::map 中的 10 个键，而不是查看一个。有 100 万个元素，我们先查看 std::map 中的 20 个键，然后再找到“正确的”一个 - std::unordered_map 中仍然只有一个。

但是，您需要对“ key ”进行哈希处理，这意味着进行某种形式的计算以使其成为一个数字。

它还取决于您插入/删除元素的频率，与您仅查找元素的频率相比。

对于较大的数据集，大小和位置也会产生很大影响，搜索“前几层”通常很快，因为它在缓存中 [如果您多次搜索同一张 map ]，无序映射占用更多空间的地方(必须有一些“备用”插槽，因为所有 10000 个元素生成的哈希值都恰好是 10000 个元素的可能性很小，因此通常情况下， HashMap 远非“完整”)。因为“最近”的散列搜索不太可能与当前的匹配，所以缓存可能也无济于事。

当然，std::unordered_map，顾名思义，是无序的——如果你遍历它，键是哈希顺序的(模桶计数，所以即使你知道散列，通常很难知道它是什么顺序)，而不是“排序”的顺序。这在某些情况下可能很重要。

因此，这是否会给您带来任何明显的性能优势，您必须通过衡量性能来弄清楚。