3 java hashtable time-complexity data-structures
我目前正在学习Java中的哈希表,我对哈希表的操作及其性能速度有疑问.
我读到哈希表可以在常量时间O(1)中实现插入,查找和删除等操作.我试图找出是什么使哈希表的操作非常量时间,这些操作会是什么？
我认为操作会像size()线性时间一样,因为速度取决于哈希表的大小,但我不确定.
任何想法都将非常感谢!
在一个天真的实现中,计算大小将是线性的,是的.但是,在变量中缓存大小是一种简单的优化,非常值得额外的几个字节以及在添加和删除元素时必须更新该变量的次要性能损失.
请记住,插入是O(1)摊销.它并不总是一个恒定的时间操作.如果哈希表过度增长,则插入将导致其大小调整,即O(n)操作.幸运的是,这些调整大小很少,其成本可以在其他O(n)插入中平均,平均只增加一个常数因子.
此外,插入,查找和删除平均都是O(1),但在最坏的情况下它们可以是O(n).使用病态错误的哈希函数,它们的性能将严重降低.在最坏的情况下,所有元素都将添加到哈希表中的一个桶中,从而有效地将哈希表转换为链表.
实际上,在Java 8中他们添加了一个优化HashMap.如果一个桶足够大并且密钥是Comparable它将使用二叉树而不是链表,从而将最坏情况性能从O(n)改为O(log n).