std::map中的find()函数的时间复杂度是多少？

Question

std::map类中的find()函数效率如何？它是否通过遍历所有元素查找键，从而变为O(n)级别，或者在平衡树中，或者使用哈希函数或其他什么方法？

- Publius

---

STL有文档，通常会说明复杂度。http://www.cplusplus.com/reference/stl/map/find/ - Don Reba

请参见：标准容器的复杂度保证是什么？ - Martin York

Answer 1

Log(n) 是指以红黑树为基础的时间复杂度。

编辑说明：n 指的是 map 中成员的数量。

- David D

---

真的，它是log(n)。不正确，它基于红黑树。标准定义了该操作的最大复杂度为log(n)，而实现这一点最有效的方法是使用红黑树（尽管这不是必需的）。因此，你把车放在马前面了。 - Martin York

@OrgnlDave：这总是正确的（不是在某种程度上）。 - Martin York

@OrgnlDave：是的，它可以。标准保证了它。我不认为你理解复杂性是什么（你的陈述可能适用于绝对速度但不适用于复杂性）。在现代机器上，100MB仍然很小，你不太可能真正测量出差异。 - Martin York

@OrgnlDave：不，它不会。 - Martin York

@std''OrgnlDave: 我认为你应该阅读这个维基百科页面。std::map::find的复杂度肯定是log(n)。你提到缓存和“现实世界的限制”这一事实表明你对大O符号有误解。你认为std::map::find具有什么样的复杂度？ - Mooing Duck

Answer 2

std::map 和 std::set 是由编译器供应商使用高度平衡的二叉搜索树（例如红黑树，AVL树）实现的。

正如David所指出的那样，find 将需要O(log n)的时间，其中n是容器中元素的数量。

但是这仅适用于像 int、long、char、double等原始数据类型，而不是字符串。

如果将长度为'm'的std:string作为键，则遍历平衡二叉搜索树的高度将需要与树条目的给定键进行 log n 次比较。

当 std::string 是 std::map 或 std::set 的键时，find 和 insert 操作的成本将为 O(m log n)，其中m是需要查找的给定字符串的长度。

- Arif Ali Saiyed

---

我本来想点赞你的，因为你指出了个体比较不一定是O(1)的问题。但是你又加了关于Java的编辑，这一点我不太明白。hashCode()返回的哈希键不是唯一标识符，所以在比较两个键时还需要进行O(m)的字符串比较。 - jogojapan

此外，生成哈希码仍然是O(m)的，因此不仅不会更快，使用哈希码会更慢（假设它们没有被缓存）。 - Mooing Duck

@jogojapan 感谢指出java.lang.String.hashCode()的问题，我通过删除javaj部分并坚持回答的问题进行了更正。同时提出了一个问题：(https://dev59.com/onTYa4cB1Zd3GeqPs0vM)。 - Arif Ali Saiyed

Answer 3

它不会遍历所有元素，而是进行二进制搜索(时间复杂度为O(log(n)))。它使用operator<或比较器来进行搜索。

如果你想要一个哈希映射，你可以使用std::unordered_map (在C++-0x中添加)，它使用哈希函数，并且平均情况下(find()的速度取决于提供的哈希函数和数据)时间复杂度为O(1)。

- fbafelipe

---

@NicolBolas：我记得在某个地方读到过，平衡树不是必须的，感谢您的评论。我已经修正了我的回答。 - fbafelipe