你知道std::unordered_set和std::unordered_map的底层实现原理和优缺点吗？

本文共计994个文字，预计阅读时间需要4分钟。

某日二师兄参加XXX科技有限公司的C++工程师开发岗位第27面：面试官：知道std::unordered_set和std::unordered_map吗？二师兄：知道。面试官：知道std::unordered_set和std::unordered_map吗？二师兄：知道。两者都支持C++11引入的新容器，与std::set和std::map功能类似。

某日二师兄参加XXX科技公司的C++工程师开发岗位第27面：

面试官：知道std::unordered_set/std::unordered_map吗？

二师兄：知道。两者都是C++11引入的新容器，和std::set和std::map功能类似，key唯一，unordered_map的value可变。

二师兄：不同于set/map，unordered_set/unordered_map都是无序容器。

面试官：那你知道它们底层怎么实现的吗？

二师兄：两者底层使用哈希表实现，因此插入、删除和查找操作的平均时间复杂度为常数时间O(1)。

面试官：既然平均复杂度是O(1)，那么是不是可以取代set和map了？

二师兄：这里是平均的时间复杂度。