为什么std::map是红黑树而不是哈希表？

Question

对我来说，这很奇怪，我预期它是一个哈希表。

我在下面的答案中看到了3个原因（也许是正确的，但我不认为它们是真正的原因）。 哈希表与自平衡搜索树

1. 虽然哈希可能不是一个简单的操作。但我认为对于大多数类型来说，它都是相当简单的。

2. 当你使用map时，你期望得到的是一种可以提供摊销O(1)插入、删除和查找的东西，而不是log(n)。

3. 我同意树在最坏情况下的性能更好。

我认为还有一个更大的原因，但我想不出来。 例如，在C#中，Dictionary就是一个哈希表。

- OopsUser

---

内存曾经非常昂贵。使用std::unordered_map来实现哈希表的映射。 - segfault

红黑树也是有序的。 - GWW

Answer 1

这在很大程度上是历史原因。标准容器（以及迭代器和算法）是在标准的功能集被固定之前添加的最后一个元素。恰好在那时，他们并没有对哈希映射有足够充分的定义，也没有时间在功能集固定之前添加它。因此，最初的规范只包括基于树的映射。

C++11添加了std::unordered_map（以及std::unordered_set和两者的multi版本），其基于哈希。

- Jerry Coffin

---

标准容器在STL中的标准化之前已经被研究了多年。很难想象没有时间添加它。当然，问题只是为什么STL具有这个属性，这并不能让我们更接近答案。 - Lightness Races in Orbit

@LightnessRacesinOrbit：它们确实被处理了，但请记住（大约）只有STL的一半被纳入标准。特别是在实际规范方面，似乎有相当多的内容是在标准纳入前匆忙编写的。 - Jerry Coffin

Answer 2

原因是map被明确指定为有序容器，它保持元素排序并允许您按排序顺序进行线性迭代。哈希表无法满足这些要求。

在C++11中，他们添加了std::unordered_map，它是一个哈希表实现。

- Mark B

---

不是要冒犯，但我真的想不通为什么这个问题会得到赞同。我会把这个问题理解为：“为什么标准要求 map 是有序的？”而这个回答是：“因为标准要求 map 是有序的。”当然，这是正确的，但这并没有解释“为什么”。 - Jerry Coffin

@Jerry Coffin 我理解（并回答）这个问题是“为什么map的实现不是哈希表”。也许楼主可以澄清他们实际的问题。 - Mark B

询问澄清肯定会有帮助。我也不明白原帖作者需要什么帮助。 - CPlusPlus OOA and D

@MarkB：是的——这个基本问题在于标准没有强制使用红黑树（或者树）。有一些不使用红黑树的 map 实现。 - Jerry Coffin

@Jerry Coffin 只是为了我的个人信息，有哪些非树形容器能够满足 map 的复杂度要求？（我们同意它不强制使用红黑树） - Mark B

Answer 3

一个哈希表需要一个额外的哈希函数。使用树的当前实现 map 可以通过使用 operator< 而不需要额外的哈希函数来工作。此外，map 允许对元素进行排序访问，这可能对某些应用程序有益。在 C++ 中，我们现在可以使用哈希版本，形式为 unordered_set。

- Danvil

---

你有这方面的参考资料吗？我从来没有听说过 == 是任何容器的要求。 - MatthiasB

@MatthiasB：我相当确定这不是任何容器的要求（尽管它被一些算法使用，例如std::find）。需要进行相等比较的容器使用<来实现：(!a<b) && (!b<a) 意味着 a==b。 - Jerry Coffin

在上述书籍的第16页中，它描述了容器的所有其他比较操作都是由<和==运算符定义的。其他比较运算符：!=、>、<=和>=可以通过<和==来定义。STL utility.h头文件被指定为自动实现此功能的位置。 - CPlusPlus OOA and D

@GWW std::map 不直接使用 operator<，而是有两个间接操作：I）std::map<K, V> 只是 std::map<K, V, std::less<K>> 的简写；II）std::less 的默认实现使用 operator<。因此，您可以为某个类型 X 专门指定 std::less<X>，以使用其他内容而不是 operator<，或者（更现实的情况）可以显式地使用不同的比较器参数化映射，例如 std::map<K, V, std::greater<K>> 以按降序存储键。 - fredoverflow

我可以很确定地预测结果：有/没有使用==不会有任何区别。一个不定义 < 的类型只有在你（尝试）实例化 map 时指定比较时才会编译。 - Jerry Coffin

Answer 4

简单来说：因为哈希表无法满足对 std::map 进行迭代的复杂度要求。

为什么 std::map 有这些要求？这是一个无法回答的问题。历史因素起到了一定作用，但总体来说，“就是这样”。

哈希表可以使用 std::unordered_map 实现。

两者的名称或在其他语言中的称呼并不重要。

- Lightness Races in Orbit