O(1)哈希查找？

Question

我看到一个断言，说HashSet<T>.Contains()是一个O(1)的操作。这让我感到惊讶，因为我遇到的所有关于哈希的讨论都提到了可能会出现冲突，从而导致O(n)的运行时间。

出于好奇，我查看了HashSet<T>.Contains和HashTable.Contains的文档。这两个方法的文档都声称是O(1)操作。

然而，在反编译器中查看HashSet<T>.Contains()，它使用一个for循环来遍历包含具有相同哈希值的值的插槽列表。

现在可以承认的是，那些关于哈希的讨论也提到了一个良好的哈希算法避免了冲突，在这种情况下查找确实是O(1)。但是，我对大O符号的理解是它是最坏情况的运行时间，而不是最好情况。

那么，O(1)的声明是不正确的吗？还是我缺少了什么？

- ThatBlairGuy

---

我讨厌大O符号 =] - Luiscencio

@Luiscencio 大O符号只是让你告诉其他程序员一个函数将如何扩展的单词。你建议哪些单词可以快速给另一个程序员一个半准确的想法，以了解一个给定函数的扩展能力？ - Bill K

[joke] 你的“函数在吃掉该死的处理器”怎么样了？ - Luiscencio

http://c-sharp-snippets.blogspot.com/2010/03/runtime-complexity-of-net-generic.html - Jaroslav Jandek

我觉得发表一个断言，声称哈希表查找具有O(n!)的时间复杂度，虽然从技术上讲是正确的，但有点误导人，看看会有多少个踩它的人，这会很有趣。 - Staffan

可能是哈希表真的可以是O(1)吗？的重复问题。 - DavidRR

Answer 1

但是我对大O符号的理解是它表示的是最坏情况的运行时间，而不是最好情况。不幸的是，在描述算法时，并没有关于Big-O的“标准”。通常，它用于描述一般或平均情况，而不是最坏情况。 来自维基百科： “……这种符号现在也经常用于分析算法，以描述算法对计算资源的使用：最坏情况或平均情况……” 在这种情况下，如果你有适当的哈希处理，那么限制行为将对于N的大小保持恒定，因此是O(1)。

- Reed Copsey

---

是的。另一个著名的例子是快速排序——最坏情况下的时间复杂度为O(n^2)，但通常被认为是O(n log n)，因为这是平均复杂度。 - kennytm

这很令人惊讶，我本来以为最坏情况会更典型，尤其是对于哈希而言，最坏情况经常出现可能会促使我们寻找更好的算法。不过我当然能理解一般/平均情况也很有用。对于哈希而言，我预计大部分时间都是O(1)。 - ThatBlairGuy

哈希表查找仅为O(1) 平摊，请参见Staffan的答案。即使如此，这也需要一些假设。 - Gilles 'SO- stop being evil'

@Gilles：大多数哈希结构都不是摊销的。它们不会修改原始哈希以防止未来的冲突，这是必需的。(有一些哈希结构可以实现，但.NET的不行...) - Reed Copsey

@Gilles：使用一个非常糟糕的哈希函数，可以保证每次都是最坏情况，这在.NET哈希中是可能的。如果你不相信我，试着使用一个自定义类实现GetHashCode为return 1;，并与HashSet一起使用。 - Reed Copsey

Answer 2

通常情况下，它的时间复杂度为O(1)。

- SLaks

---

即使考虑到内置的GetHashCode已知的性能不佳？我也不会依赖它是O(1)... - Stephen Cleary

@Stephen：你在说什么？即使GetHashCode需要一个小时才能返回，它仍然是O(1)——GetHashCode的性能不随集合大小而变化。 - SLaks

@SLaks，我猜斯蒂芬指的是默认实现对于哈希的适用性较差。请参见https://dev59.com/kXRB5IYBdhLWcg3wF0HH#720196。 - Ben M

@Slaks：Ben是正确的。问题不在于GetHashCode需要很长时间才能返回，而在于它是一个糟糕的哈希算法。这会导致冲突。这将使“O（1）”反射答案朝着不正确的方向推进，因为平均而言它不再成立。 - Stephen Cleary

HashSet 使用 IEqualityComparer<T> 的 GetHashCode 方法，您可以在构造函数中指定并影响性能（好或坏）。 - Jaroslav Jandek

Answer 3

对于一个正确实现的哈希表，查找具有 平摊 常数时间复杂度。

在实践中，由于冲突的存在，单次查找可以是 O(n) 的。然而，如果你执行大量的查找操作，每个操作的平均时间复杂度是常数级别的。

引用维基百科：

平摊分析与平均情况下的性能不同，因为它不涉及概率；平摊分析保证了最坏情况下的操作时间。

该方法需要了解哪些系列操作是可能的。这通常是数据结构的情况，因为数据结构具有在操作之间持久存在的状态。基本思想是，最坏情况下的操作可以改变状态，以使最坏情况在很长一段时间内无法再次发生，从而“摊销”其成本。

- Staffan

---

实际上，在好的哈希表复杂度描述中，必须提到分摊复杂度。但请注意，分摊O(1)复杂度需要假设键被充分随机分布。如果攻击者选择要添加到哈希表中的键，他可以每次强制发生冲突。这可以通过使用加密哈希来避免，但这些非常昂贵，所以你会获得具有难以承受的大常数的常数时间。另一种方法是在哈希中包含一个随机种子（Perl在某个时候就是这样做的）。 - Gilles 'SO- stop being evil'

Answer 4

不，Big O并不定义“最坏情况”，它定义了一个限制。使用良好的哈希算法（提供高效的值分布和低碰撞率）的基于哈希的查找会随着项数的增加而逐渐趋近于一个常数值（它们永远不会达到或超过该常数值，但这就是它成为限制的意义所在）。

- Adam Robinson

Answer 5

我认为这意味着平均时间复杂度为O(1)。

- kennytm

Answer 6

不，大O符号并不一定局限于最坏情况。通常你会看到大O符号用于最好情况、平均情况和最坏情况。只是大多数人倾向于关注最坏情况。除了哈希表的情况外，最坏情况很少发生，因此使用平均情况更有用。

是的，一个好的哈希函数可以降低碰撞的概率。一个糟糕的哈希函数可能会导致聚集效应（不同的值哈希到完全相同或接近相同的值）。很容易证明，通过以一种总是返回相同值的方式实现GetHashCode函数，HashSet确实可以变成O(n)。

简而言之，是的，HashSet和Dictionary可以被描述为具有O(1)的运行时间复杂度，因为重点在于平均情况的场景。

顺便提一下，大O符号也可以用于分析摊销复杂度。摊销复杂度是指将一系列单独的（有时甚至不同的）操作当作一个大操作进行分组时的行为方式。例如，尽管每个操作的最坏情况可能是O(n)，最好情况是O(1)，但伸展树被认为具有摊销O(log(n))的搜索、插入和删除复杂度。

- Brian Gideon

Answer 7

我对大O符号的理解是，“最坏情况”通常是指涉及的元素数量。因此，如果一个函数在处理10个元素时执行O(n)，但在处理100个或更多元素时执行O(n平方)（不确定是否存在这样的算法），那么该算法被认为是O(n平方)。

- Nick

Answer 8

O(1)并不一定意味着“最坏情况”。对于哈希表来说，人们通常说“期望”的查找时间是O(1)，因为哈希碰撞的概率很小。

- Ferdinand Beyer

---

这就是让我感到惊讶的地方——在我发现的各个引用查找中，措辞并没有说“预期”的或“典型”的。它们说“是”，这意味着始终如此。 - ThatBlairGuy

Answer 9

哈希表不仅具有平均情况下的O(1)性能，而且如果哈希函数是随机的，对于任何给定百分比P < 100%，从一个正确设计的哈希表中可以获得P%的性能为O(1)。虽然极端寄生情况随着N的增加变得越来越严重，但这被事实所平衡，即即使是中度寄生情况也变得越来越不可能发生。

- supercat