哈希表可以实现O(1)似乎是常识,但这对我来说从来没有意义.有人可以解释一下吗？以下是两种情况:
答: 该值是一个小于哈希表大小的int.因此,该值是它自己的哈希值,因此没有哈希表.但如果有,那将是O(1)并且仍然是低效的.
B. 您必须计算值的哈希值.在这种情况下,查找数据大小的顺序为O(n).在你做O(n)工作之后,查找可能是O(1),但在我眼中仍然是O(n).
除非你有一个完美的哈希表或一个大的哈希表,否则每个桶可能有几个项目.因此,无论如何,它在某个时刻转变为一个小的线性搜索.
我认为哈希表很棒,但我没有得到O(1)的名称,除非它只是理论上的.
维基百科关于哈希表的文章始终引用常量查找时间并完全忽略哈希函数的成本.这真是一个公平的衡量标准吗？
编辑:总结我学到的东西:
这在技术上是正确的,因为哈希函数不需要使用密钥中的所有信息,因此可以是恒定时间,并且因为足够大的表可以将冲突降低到接近恒定的时间.
在实践中确实如此,因为随着时间的推移,只要选择散列函数和表大小来最小化冲突,即使这通常意味着不使用常量时间散列函数,它也只会有效.
我对哈希表的时间复杂性感到困惑很多文章表明它们是"摊销的O(1)"而不是真正的命令O(1)这在实际应用中意味着什么.哈希表中的操作的平均时间复杂度是多少,实际实现中不是理论上的,为什么操作不正确O(1)？
我们如何找出哈希表上搜索操作的平均和最差情况时间复杂度,该操作已通过以下方式实现:
假设'N'是需要进行哈希处理的键数.我们采用大小为M的哈希表(M = alpha*N,alpha~0.1).通过以链式链表方式存储密钥来解决冲突,将每个新条目存储在由'hashTable [i]'指向的每个链表的头部.
恕我直言,最好,平均和最坏情况的复杂性可能是O(1),O(N/M)和O(N).如果我错了,请纠正我.将会有一个详细的解释.