Java Map实现渐进复杂度(HashMap、LinkedHashMap、TreeMap)

Question

我正在尝试处理 HashMap、LinkedHashMap 和 TreeMap 的渐近复杂性。在不同的网站和文章中写道，平均 get = O(1)，最坏情况下 - O(n)。 (如果所有键都添加到一个桶中)。

但是我读过书 Bruce Eckel thinking in java 并且有一个比较的例子

如果您查看此数据，则它会出现 O(n)

我完全糊涂了。谁能解释一下 Map 实现的渐近复杂性 - HashMap、LinkedHashMap 和 TreeMap，至少对于 获取 和放置？ (也许有一篇很好的文章，所有内容都清楚并放在一起？)

编辑

最感兴趣的是put方法。因为当某个大小发生时 resize() 类似于 ArrayList。

Answer 1

它称为摊销 O(1)，意思是在有很多条目的一段时间内，您经常get。您似乎也缺乏对 O(1) 的理解 - 这意味着它是不变的。如果我向 HashMap 添加更多条目 - 检索条目所需的时间是相同的，无论是 HashMap 中的 10 还是 1000 万个条目并考虑hashCode 已实现，并且没有 return 1 的虚拟实现(例如，条目将被放入同一个桶中)。

在某些情况下确实会发生调整大小，但它甚至与 ArrayList 的做法相去甚远。 ArrayList 只会使内部数组变大，总是； HashMap 会将内部桶加倍到某个点 ( see when exactly here )，之后它将某个桶转换为 Tree，从而加快搜索速度 - 这是在 java-8 中添加的。