为什么通过键O(1)访问字典的元素,即使哈希函数可能不是O(1)？

Question

我看到你如何通过密钥访问你的收藏.但是,哈希函数本身在幕后有很多操作,不是吗？

假设你有一个很好的哈希函数非常有效,它仍然可能需要很多操作.

这可以解释一下吗？

Answer 1

O(1)并不意味着即时.O(1)意味着不变,不考虑数据的大小.哈希函数需要一定的时间,但该时间量不会随着集合的大小而缩放.

Answer 2

它HashFunc本身在幕后有很多操作

这当然是对的.但是,这些操作的数量取决于密钥的大小,而不是密钥插入的哈希表的大小:计算哈希函数的操作数对于具有10或者表的密钥是相同的有一万个条目.

这就是为什么哈希函数的调用通常被认为是O(1).这适用于固定大小的键(整数值和固定长度的字符串).它还为具有实际上限的可变大小键提供了适当的近似值.

但是,通常,哈希表的访问时间是O(k),其中k是哈希键大小的上限.

Answer 3

这意味着无论您的收藏大小是多少,它仍然需要几乎相同的时间来检索其任何成员.

所以换句话说,有5个成员的词典会让coud花费大约0.002毫秒来访问其中一个,以及25个成员的词典应该采取类似的东西.Big O表示算法复杂度超过集合大小而不是实际的语句或执行的函数

Answer 4

如果字典/映射被作为实现HashMap,它具有最好的情况下的复杂的O(1),因为我最好的情况下它需要检索的关键元件的哈希码的准确计算,如果没有键的碰撞.

一个哈希地图可能有最坏情况下运行复杂的O(n),如果你有很多关键的碰撞或非常糟糕的散列函数,因为在这种情况下,它会降低到保存数据的整个阵列的线性扫描.

此外,O(1)并不意味着立即,它意味着它具有恒定的数量.因此,为字典选择正确的实现也可能取决于集合中元素的数量,因为如果只有少数条目,那么函数的非常高的常量成本将更加糟糕.

这就是为什么字典/地图针对不同的场景实现不同的原因.对于Java,有多种不同的实现,C++使用红/黑树等.您可以根据数据的数量并根据其最佳/平均/最差情况运行时效率来选择它们.

Answer 5

理论上它仍然是O(n),因为在最坏的情况下,所有数据可能最终都具有相同的散列并捆绑在一起,在这种情况下,您必须线性地遍历所有数据.