LinkedHashMap 的性能：Big O、Memory cost 等
Performance of LinkedHashMap: Big O, Memory cost, etc
这是一个新手问题：LinkedHashMap get/put/contains 的大 O 是什么？据我了解，TreeMap 是 O(logN)，而 LinkedList（按值 search/add/delete）是 O(N)。这会使 LinkedHashMap 在 O(logN) 上运行，还是表现更好？在性能和内存使用等方面与HashMap相比如何？
3次都是O(1)。换句话说，时间与数据集大小无关。记忆是 O(N).
LinkedHashMap 提供与 HashMap 相似的性能（在大 O 表示法方面），但也允许按插入顺序进行确定性迭代。
这意味着，get()、put()、contains() 都在 O(1)（摊销平均值）中完成。
您可以在 documentation 中阅读更多内容。
Like HashMap, it provides constant-time performance for the basic operations (add, contains and remove)
性能特征总是在 Java 文档中解释。
https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html
通过查看https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html，这是我现在的理解：
LinkedHahsMap 顾名思义，结合了 HashMap 和 LinkedList 在 get/put/contains 上提供 O(1) 操作。早些时候我对 TreeMap 感到困惑。换句话说，它维护了 HashMap 提供的可预测顺序（插入顺序）
This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). Note that insertion order is not affected if a key is re-inserted into the map.
这与 LRU 非常相似：https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU)
自然地，LHM 的实现需要为每个元素存储额外的 LinkedList。
这是一个新手问题：LinkedHashMap get/put/contains 的大 O 是什么？据我了解，TreeMap 是 O(logN)，而 LinkedList（按值 search/add/delete）是 O(N)。这会使 LinkedHashMap 在 O(logN) 上运行，还是表现更好？在性能和内存使用等方面与HashMap相比如何？
3次都是O(1)。换句话说，时间与数据集大小无关。记忆是 O(N).
LinkedHashMap 提供与 HashMap 相似的性能（在大 O 表示法方面），但也允许按插入顺序进行确定性迭代。
这意味着，get()、put()、contains() 都在 O(1)（摊销平均值）中完成。
您可以在 documentation 中阅读更多内容。
Like HashMap, it provides constant-time performance for the basic operations (add, contains and remove)
性能特征总是在 Java 文档中解释。
https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html
通过查看https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html，这是我现在的理解：
LinkedHahsMap 顾名思义，结合了 HashMap 和 LinkedList 在 get/put/contains 上提供 O(1) 操作。早些时候我对 TreeMap 感到困惑。换句话说，它维护了 HashMap 提供的可预测顺序（插入顺序）
This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). Note that insertion order is not affected if a key is re-inserted into the map.
这与 LRU 非常相似：https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU)
自然地，LHM 的实现需要为每个元素存储额外的 LinkedList。