O(1)哈希查找？

Question

我遇到了一个断言HashSet <T> .Contains()是一个O(1)操作.这令我感到惊讶,因为我遇到的每次哈希讨论都提到了碰撞的可能性,可能导致O(n)运行时间.

好奇,我查看了HashSet <T> .Contains和HashTable.Contains的文档.两种方法的文档都提出了同样的主张.

当我查看反射器时,HashSet <T> .Contains()是用for循环实现的,它通过一个包含具有相同散列值的槽列表.

现在可以肯定的是,那些关于哈希的讨论也提到了一个好的哈希算法可以避免冲突,在这种情况下查找确实是O(1).但我对Big O符号的理解是,它是最糟糕的运行时间,而不是最好的.

O(1)声明是否错误？或者我错过了什么？

Answer 1

但我对Big O符号的理解是,它是最糟糕的运行时间,而不是最好的.

不幸的是,在描述算法时,Big-O没有"标准".通常,它用于描述一般或平均情况 - 而不是最坏的情况.

来自维基百科:

...此符号现在经常用于分析算法以描述算法对计算资源的使用:最坏情况或平均情况......

在这种情况下,它描述了一个标准情况,给定适当的散列.如果你有适当的散列,限制行为对于大小N将是恒定的,因此O(1).

Answer 2

一般来说,它是O(1).

Answer 3

对于正确实现的哈希表,查找具有分摊的恒定时间复杂度.

实际上,正如你所说,在碰撞的情况下,单个查找可以是O(n).但是,如果执行大量查找,则每个操作的平均时间复杂度是不变的.

引用维基百科:

摊销分析与平均案例绩效的不同之处在于不涉及概率; 摊销分析保证每次操作的时间超过最坏情况的性能.

该方法需要知道哪一系列操作是可能的.这种情况最常见于数据结构,其状态在操作之间持续存在.基本思想是最坏情况下的操作可以改变状态,使得最坏情况不能长时间再次发生,从而"摊销"其成本.

Answer 4

不,Big O没有定义"最坏情况",它定义了一个限制.基于散列的查找(具有良好的散列算法,提供有效的值分布和低冲突率)随着项目数量的增加而向一个恒定值前进(它们永远不会达到或者是恒定值,但这就是它的限制点).