英文:
Performance of LinkedHashMap: Big O, Memory cost, etc
问题
这是一个新手问题：LinkedHashMap 的 get/put/contains 的时间复杂度是多少？据我所了解，对于 TreeMap 来说，它是 O(logN)，而对于 LinkedList（按值进行搜索/添加/删除），它是 O(N)。这是否意味着 LinkedHashMap 的操作是 O(logN)，还是它表现更好？在性能和内存使用等方面，它与 HashMap 相比如何？
英文:
It's a newbie question: what is the big O for get/put/contains for LinkedHashMap? As I understand for TreeMap it's O(logN), and for LinkedList (to search/add/delete by value), it is O(N). Does that make LinkedHashMap operates on O(logN), or does it perform better? And how does compare with HashMap in terms for performance and memory usage, etc.?
答案1
得分: 1
LinkedHashMap 提供了与 HashMap 相似的性能（从大 O 表示法的角度看），但还允许按插入顺序进行确定性迭代。
这意味着 get()、put()、contains() 都在 O(1) 的时间复杂度内完成（平摊平均）。你可以在文档中阅读更多信息。
英文:
LinkedHashMap offers similar performance to those of HashMap (in terms of big O notation), but also allows a deterministic iteration by the order of insertion.
This means, get(), put(), contains(), are all done in O(1) (amortized average).
You can read more in the documentation.
答案2
得分: 0
所有三次操作的时间复杂度为 O(1)。换句话说，与数据集大小无关。内存复杂度为 O(N)。
英文:
All 3 times are O(1). By other words, time independent on dataset size. Memory is O(N).
答案3
得分: 0
就像 HashMap 一样，它在基本操作（添加、包含和移除）方面提供了常数时间性能。
性能特性总是在 Java 文档中进行了解释。
https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html
英文:
>Like HashMap, it provides constant-time performance for the basic operations (add, contains and remove)
Performance characterstics are always explained in the Java documentation.
https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html
答案4
得分: 0
通过查看 https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html，我现在的理解如下：
LinkedHashMap 顾名思义，结合了 HashMap 和 LinkedList，在 get/put/contains 操作上提供了 O(1) 的性能。我之前对 TreeMap 感到困惑。换句话说，它保持了 HashMap 提供的具有可预测顺序的特性（插入顺序）。
这种实现与 HashMap 的不同之处在于，它通过所有条目维护了一个双向链表。这个链表定义了迭代顺序，通常是键被插入到映射中的顺序（插入顺序）。请注意，如果将键重新插入映射，插入顺序不受影响。
这与 LRU 非常相似：https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU)
自然地，LinkedHashMap 的实现需要为每个元素存储额外的 LinkedList。
英文:
By looking at https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html, this is what I understand now:
LinkedHahsMap by it's name, combines HashMap and LinkedList to offer O(1) operations on get/put/contains. I was confused earlier on with TreeMap. In other words, it maintains what HashMap offers with predictable order (insertion order)
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.
This is very similar to LRU: https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU)
Naturally the implementation of LHM requires additional LinkedList stored for each element.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论