我找到了很多关于map 和unordered_map 的复杂性的帖子。据说 unordered_map 的最坏情况复杂度为 O(N)。出于我的目的，我将输入排序值，如 1 2 5 6 9 11 12..。我需要插入或查找并删除一个值。我将不得不经常插入/删除。我想过使用 set ，它在所有情况下都具有 log(n) 的复杂性。然后我偶然发现了具有最佳 O(1) 复杂度的 unordered_map。但是我需要了解在我的场景中我会面临 unordered_map 的最坏情况吗？又会是怎样的场景？
编辑:在我的例子中，所有值都是唯一的。
最佳答案
unordered_map 最坏的情况通常发生在哈希函数为映射中的每个插入产生冲突时。
我说“通常”是因为该标准仅指定最坏情况的复杂性，而不是何时或如何发生，因此理论上您问题的答案是它由实现定义。
因为你所有的值都是唯一的，而且显然是整数(它提供了非常好的散列，可能是最优的 _ 这又是依赖于实现的)，你不会遇到这种最坏的情况。插入/查找/删除的时间复杂度为 O(1)，所以这看起来是一个合理的选择。
关于c++ - unordered_map 的最坏情况是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24154986/