哈希表可以实现O(1)似乎是常识,但这对我来说从来没有意义.有人可以解释一下吗？以下是两种情况:
答: 该值是一个小于哈希表大小的int.因此,该值是它自己的哈希值,因此没有哈希表.但如果有,那将是O(1)并且仍然是低效的.
B. 您必须计算值的哈希值.在这种情况下,查找数据大小的顺序为O(n).在你做O(n)工作之后,查找可能是O(1),但在我眼中仍然是O(n).
除非你有一个完美的哈希表或一个大的哈希表,否则每个桶可能有几个项目.因此,无论如何,它在某个时刻转变为一个小的线性搜索.
我认为哈希表很棒,但我没有得到O(1)的名称,除非它只是理论上的.
维基百科关于哈希表的文章始终引用常量查找时间并完全忽略哈希函数的成本.这真是一个公平的衡量标准吗？
编辑:总结我学到的东西:
这在技术上是正确的,因为哈希函数不需要使用密钥中的所有信息,因此可以是恒定时间,并且因为足够大的表可以将冲突降低到接近恒定的时间.
在实践中确实如此,因为随着时间的推移,只要选择散列函数和表大小来最小化冲突,即使这通常意味着不使用常量时间散列函数,它也只会有效.
如果我们从Java角度看,那么我们可以说hashmap查找需要恒定的时间.但内部实施呢？对于不同的匹配键,它仍然必须搜索特定的桶(对于哪个键的哈希码匹配).那么为什么我们说hashmap查找需要恒定的时间？请解释.
对于在三角时间运行的算法,正确的大O表示法是什么？这是一个例子:
func(x):
for i in 0..x
for j in 0..i
do_something(i, j)
我的第一直觉是O(n²),但我不完全确定.