问C++中的map与hash_map

EN

它们以非常不同的方式实现。

hash_map ( TR1和Boost中的unordered_map；改为使用它们)使用哈希表，其中键被散列到表中的一个槽，值存储在与该键绑定的列表中。

map被实现为平衡的二进制搜索树(通常是红/黑树)。

对于访问集合的已知元素，unordered_map应该会提供稍微好一点的性能，但map将具有其他有用的特征(例如，它以排序的顺序存储，这允许从头到尾进行遍历)。在insert和delete方面，unordered_map比map更快。

hash_map是许多库实现提供的通用扩展。这正是将其作为TR1的一部分添加到C++标准中时将其重命名为unordered_map的原因。map通常使用像红黑树这样的平衡二叉树来实现(当然，实现方式各不相同)。hash_map和unordered_map通常使用哈希表实现。因此，该顺序不会被维持。unordered_map插入/删除/查询将是O(1) (恒定时间)，其中map将是O(log )，其中n是数据结构中的项数。所以unordered_map更快，如果你不关心项目的顺序，应该比map更好。有时，您希望维护顺序(按键排序)，为此，map将是一个选择。

C++规范并没有明确说明您必须为STL容器使用什么算法。然而，它确实对它们的性能施加了某些约束，这排除了对map和其他关联容器使用哈希表的可能性。(它们通常是用红/黑树实现的。)这些约束要求这些容器比哈希表提供更好的最坏情况下的性能。

然而，许多人确实想要哈希表，所以基于哈希的STL关联容器多年来一直是一个常见的扩展。因此，他们在C++标准的较新版本中添加了unordered_map等。