Java Hashtable非恒定时间操作

发布时间：2020-12-15 04:29:34 所属栏目：Java 来源：网络整理

导读：我目前正在学习 Java中的哈希表,我对哈希表的操作及其性能速度有疑问. 我读到哈希表可以在常量时间O(1)中实现插入,查找和删除等操作.我试图弄清楚是什么使哈希表的操作非常量时间,这些操作会是什么？我认为像size()这样的操作会处于线性时间,因为速度取决于

我目前正在学习 Java中的哈希表,我对哈希表的操作及其性能速度有疑问.

我读到哈希表可以在常量时间O(1)中实现插入,查找和删除等操作.我试图弄清楚是什么使哈希表的操作非常量时间,这些操作会是什么？

我认为像size()这样的操作会处于线性时间,因为速度取决于哈希表的大小,但我不确定.

任何想法都将非常感谢！

在一个天真的实现中,计算大小将是线性的,是的.但是,在变量中缓存大小是一种简单的优化,非常值得额外的几个字节以及在添加和删除元素时必须更新该变量的次要性能损失.

请记住,插入是O(1)摊销.它并不总是一个恒定的时间操作.如果哈希表过度增长,则插入将导致其大小调整,即O(n)操作.幸运的是,这些调整很少,其成本可以在其他O(n)插入中平均,平均只增加一个常数因子.

此外,插入,查找和删除平均都是O(1),但在最坏的情况下它们可以是O(n).使用病态错误的哈希函数,它们的性能将严重降低.在最坏的情况下,所有元素都将添加到哈希表中的一个桶中,从而有效地将哈希表转换为链表.

实际上,in Java 8 they added an optimization to HashMap.如果一个桶足够大并且密钥是可比较的,那么它将使用二叉树而不是链表,从而改善从O(n)到O(log n)的最坏情况性能.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!