unordered_map 的最坏情况是什么？

Question

unordered_map 的最坏情况是什么？

c++dictionarytime-complexityunordered-mapspace-complexity

12

我发现很多关于map和unordered_map复杂度的帖子。据说unordered_map的最坏情况复杂度为O(N)。我的输入是像1 2 5 6 9 11 12..这样已排序的值。我需要插入、查找和删除一个值，而且我会经常进行插入/删除操作。我考虑使用set，它在所有情况下的复杂度都是log(n)。然后我偶然发现了unordered_map，它的复杂度最好是O(1)。但我需要了解一下，在我的场景中，我是否会遇到unordered_map的最坏情况？如果会，会出现什么情况呢？

编辑：在我的情况下，所有的值都是唯一的。

- Tahlil

您是否有输入整数的范围？ - Sagar Jha

是的，它将是2^29的最大值。 - Tahlil

一个数据结构并没有时间复杂度，算法才有。 - D Drmmr

你可能会对这个链接感兴趣——它讨论了由于创建输入键而触发哈希表最坏情况行为而导致的拒绝服务攻击。 - Tony Delroy

2个回答

1

根据哈希算法的实现方式，使用unordered_map时，有序数据可能会导致大量冲突。由于您的数据是有序的，使用treeset可能更有优势。（假设您不想添加重复数据。）

- ByteByter

你所指的在平衡树中最坏情况为O(n)的操作是哪一个？不是插入、删除或查找，它们的最坏情况都是O(log n)。 - Benjamin Lindley

一棵平衡树，可以让你在删除、插入和查找的平均情况下达到O(log n)的复杂度；最坏情况仍然是n。然而，大多数时间操作都将是O(log n)。Benjamin Lindley说，这取决于集合树的实现方式，它可能在某些情况下需要o(n)的时间。（例如bst）*http://bigocheatsheet.com/ - ByteByter

@ByteByter 一个平衡树的实现，例如红黑树或AVL树，保证最坏情况下是O(log n)。你的链接也是这么说的。 - n. m.

@Benjamin Lindley同意，我只是在说，根据数据结构的编码方式，情况可能会更糟。 - ByteByter

@ByteByter：只有当它的编码方式不再满足其所声称的数据结构的定义时，才会出现这种情况。但是在这种情况下，它可能比O（n）更糟糕。它可能是O（n ^ 2）或O（2 ^ n）。但我们不会再称它为平衡二叉树，因为它无法满足一个平衡二叉树的性能要求。请注意，你提到的bst，我想你是指你链接中的bst，那是一棵非平衡树。 - Benjamin Lindley

@Benjamin Lindley，没错，我想我不应该如此随意地使用“平衡”这个词。 - ByteByter

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- quantdev · Accepted Answer

unordered_map最坏情况通常发生在哈希函数为每个插入操作产生冲突时。

我说“通常”是因为标准只规定了最坏情况的复杂度，而没有说明何时或如何发生，因此，从理论上讲，对于您的问题的答案是取决于实现的。

由于您的所有值都是唯一的，并且显然是整数（它们具有非常好的哈希性能，可能是最优的-这又取决于实现），因此您不会遇到这种最坏情况。插入/查找/删除的时间复杂度将为O(1)，因此看起来是一个合理的选择。