Map与unordered_map

Question

我的问题与其说是为了调试，不如说是为了学习：

我目前正在优化我的游戏代码，我想知道：

我正在使用一个地图在我的程序中分配一些值，那么unordered_map的使用速度比地图快吗？

(顺便说一句，这不是我的母语！)

Answer 1

这里的区别是，map内部使用红黑树，无序映射是s 哈希表。与unordermap相比，map非常快，因为将元素放入映射只需要1 (O(1))“操作”，其中映射需要在树中找到正确的位置来存储映射中的值(O(log ))。您还可以阅读C++文档中的地图和无序图。

Answer 2

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

但是，您需要散列“键”，这意味着要进行某种形式的计算，使其成为一个数字。

它还取决于插入/删除元素的频率，而不是只查找元素的频率。

对于较大的数据集，大小和位置也会产生很大的影响，而搜索“前几层”通常是快速的，因为如果您多次在同一张地图中搜索，无序的映射占用更多的空间(必须有一些“备用”槽，因为所有10000个元素生成的哈希值都不太可能精确为10000个元素，所以通常哈希映射还远远没有“满”)。因为“最近”的散列搜索不太可能与当前的哈希搜索相匹配，所以缓存也可能没有多大帮助。

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

因此，这是否会给您带来任何显著的性能好处，这是您必须通过衡量性能来解决的问题。