哈希表可以实现O(1)似乎是常识,但这对我来说从来没有意义.有人可以解释一下吗？以下是两种情况:
答: 该值是一个小于哈希表大小的int.因此,该值是它自己的哈希值,因此没有哈希表.但如果有,那将是O(1)并且仍然是低效的.
B. 您必须计算值的哈希值.在这种情况下,查找数据大小的顺序为O(n).在你做O(n)工作之后,查找可能是O(1),但在我眼中仍然是O(n).
除非你有一个完美的哈希表或一个大的哈希表,否则每个桶可能有几个项目.因此,无论如何,它在某个时刻转变为一个小的线性搜索.
我认为哈希表很棒,但我没有得到O(1)的名称,除非它只是理论上的.
维基百科关于哈希表的文章始终引用常量查找时间并完全忽略哈希函数的成本.这真是一个公平的衡量标准吗？
编辑:总结我学到的东西:
这在技术上是正确的,因为哈希函数不需要使用密钥中的所有信息,因此可以是恒定时间,并且因为足够大的表可以将冲突降低到接近恒定的时间.
在实践中确实如此,因为随着时间的推移,只要选择散列函数和表大小来最小化冲突,即使这通常意味着不使用常量时间散列函数,它也只会有效.
我已经对哈希表进行了一些研究,并且我一直遵循经验法则,当有一定数量的条目(最大或通过75%的加载因子)时,应该扩展哈希表.
几乎总是,建议是将哈希表的大小加倍(或加倍加1,即2n + 1).但是,我没有找到一个很好的理由.
为什么要加倍大小,而不是将其增加25%,或者将其增加到下一个素数或下一个素数(例如三个)？
我已经知道,选择一个初始哈希表大小是一个素数通常是一个好主意,至少如果你的哈希函数使用模数,如通用哈希.我知道这就是为什么通常建议做2n + 1而不是2n(例如,http://www.concentric.net/~Ttwang/tech/hashsize.htm)
然而正如我所说,我没有看到任何真正的解释,为什么加倍或加倍加一个实际上是一个很好的选择,而不是选择新哈希表的大小的其他方法.
(是的,我已经阅读了关于哈希表的维基百科文章:) http://en.wikipedia.org/wiki/Hash_table
集合有 contains 函数，如果集合中存在成员，则返回 true；否则为假。
其复杂度为O(1)。
我想知道它的复杂度如何是恒定的 O(1) 即它不依赖于大小
以下是文档：https://developer.apple.com/documentation/swift/set/1540013-contains