Java Hashtable 非常数时间操作

Question

3

我正在学习Java中的哈希表，有一个与哈希表操作和性能速度相关的问题。

我读到哈希表可以在常数时间内(O(1))执行插入、查找和删除等操作。我正试图弄清楚是什么使哈希表的操作不是常数时间，以及一些这样的操作会是什么。

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

如果您有任何想法，将不胜感激！

- user4780686

你有看过 Java 库源代码吗？http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java - Nayuki

如果两个元素具有相同的哈希码，会发生什么？ - dkatzel

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- John Kugelman · Accepted Answer

在一个天真的实现中，计算大小是线性的。但是缓存大小到一个变量中是一种简单的优化方式，这样做值得额外的几个字节和稍微降低性能，因为随着元素的添加和删除需要更新该变量。

请记住，插入是摊销的O(1)操作。它并不总是一个恒定时间的操作。如果哈希表过度充满，则插入将导致其被重新调整大小，这是一个O(n)的操作。幸运的是，这些调整大小很少发生，它们的成本可以在其他O(n)插入之间平均分摊，平均只增加了一个常数因子。

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

实际上，在Java 8中他们对HashMap进行了优化。如果桶足够大且键是Comparable，它将使用二叉树而不是链表，将最坏情况的性能从O(n)提高到O(log n)。