java - LinkedHashMap的性能：大O、内存开销等

Question

这是一个新手问题：LinkedHashMap 的 get/put/contains 的大 O 是什么？据我了解，对于 TreeMap，它是 O(logN)，对于 LinkedList（按值搜索/添加/删除），它是 O(N)。这会使 LinkedHashMap 在 O(logN) 上运行，还是表现更好？以及在性能和内存使用等方面与 HashMap 相比如何？

标签： javaalgorithmlinkedhashmap

Answer 1

LinkedHashMap提供与 HashMap 类似的性能（就大 O 表示法而言），但也允许按插入顺序进行确定性迭代。

这意味着, get(), put(), contains(), 都在O(1)（摊销平均）中完成。

您可以在文档中阅读更多内容。