std::map是否在O(1)上查找密钥？我以为是，直到我想得更多。它基于树实现，因此查找时间应该是 O(log N)，对吗？
而且，是否有可能让 O(1) 查找字符串键std::unordered_map？
问问题
49301 次
3 回答
57
查找的复杂度为std::mapO(log N)（容器大小的对数）。
根据 C++11 标准的第 23.4.4.3/4 段std::map::operator []：
复杂性：对数。
查找的复杂度std::unordered_map在平均情况下为 O(1)（常数），在最坏情况下为 O(N)（线性）。
根据 C++11 标准的第 23.5.4.3/4 段std::unordered_map::operator []
复杂性：平均情况 O(1)，最坏情况 O(
size())。
笔记：
如果您的问题只涉及计算复杂性，那么上面写的应该回答它。实际上，操作的计算复杂度是根据容器的大小（它包含的元素数量）来衡量的。
但是，如果您正在寻找一种在使用字符串键的容器上执行 O(1) 查找的方法，并且查找的复杂性相对于字符串的长度而不是容器的大小是恒定的，那么答案是std::unordered_map不符合您的要求。
为了查找密钥，首先需要生成它的哈希值；当键是一个字符串时，这个操作本身在字符串的大小上可能是线性的。然后，实现必须将键与同一个桶中的所有字符串键进行比较，并且这些比较中的每一个又与这些字符串的大小呈线性关系。
于 2013-04-17T19:08:25.833 回答
6
是的，确实std::map 将具有O(log N)并且std::unordered_map将具有平均恒定时间复杂度，并且O(N)在最坏的情况下，如果有太多的哈希冲突。
于 2013-04-17T19:08:32.787 回答
2
基本上 std::map 是使用红黑树实现的。在红黑树中插入和删除操作需要 O(LogN) 时间，因此在 std::map 中，每个元素的时间复杂度为 O(LogN)。
std::unodered_map 是使用散列实现的，其中每个操作都需要 O(1) 时间。
于 2018-10-28T15:57:54.583 回答