java LinkedHashMap 和 HashMap 的实现有什么不同？

How is the implementation of LinkedHashMap different from HashMap?

提问by Passionate programmer

If LinkedHashMap's time complexity is same as HashMap's complexity why do we need HashMap? What are all the extra overhead LinkedHashMap has when compared to HashMap in Java?

如果 LinkedHashMap 的时间复杂度与 HashMap 的复杂度相同，为什么我们需要 HashMap？与 Java 中的 HashMap 相比，LinkedHashMap 有哪些额外开销？

采纳答案by Jon Skeet

LinkedHashMap will take more memory. Each entry in a normal HashMapjust has the key and the value. Each LinkedHashMapentry has those references andreferences to the next and previous entries. There's also a little bit more housekeeping to do, although that's usually irrelevant.

LinkedHashMap 将占用更多内存。法线中的每个条目HashMap只有键和值。每个LinkedHashMap条目都有对下一个和上一个条目的引用和引用。还有更多的内务工作要做，尽管这通常无关紧要。

回答by Stephen C

If LinkedHashMap's time complexity is same as HashMap's complexity why do we need HashMap?

如果 LinkedHashMap 的时间复杂度与 HashMap 的复杂度相同，为什么我们需要 HashMap？

You should not confuse complexity with performance. Two algorithms can have the same complexity, yet one can consistently perform better than the other.

您不应将复杂性与性能混淆。两种算法可以具有相同的复杂性，但一种可以始终比另一种表现得更好。

Remember that f(N) is O(N)means that:

请记住，这f(N) is O(N)意味着：

limit(f(N), N -> infinity) <= C*N  

where Cis a constant. The complexity says nothing about how small or large the Cvalues are. For two different algorithms, the constant Cwill most likely be different.

哪里C是常数。复杂性与C值的大小无关。对于两种不同的算法，常数C很可能不同。

(And remember that big-O complexity is about the behavior / performance as Ngets very large. It tells you nothing about the behavior / performance for smaller Nvalues.)

（请记住，大 O 复杂性与N变得非常大的行为/性能有关。它不会告诉您较小N值的行为/性能。）

---

---

Having said that:

话说回来：

• The difference in performance between HashMapand LinkedHashMapoperations in equivalent use-cases is relatively small.

• A LinkedHashMapuses more memory. For example, the Java 11 implementation has two additional reference fields in each map entry to represent the before/after list. On a 64 bit platform without compressed OOPs the extra overhead is 16 bytes per entry.

• Relatively small differences in performance and/or memory usage can actually matter a lot to people with performance or memory critical applications¹.

• 等效用例中HashMap和LinkedHashMap操作之间的性能差异相对较小。

• ALinkedHashMap使用更多内存。例如，Java 11 实现在每个映射条目中有两个额外的引用字段来表示之前/之后列表。在没有压缩 OOP 的 64 位平台上，额外的开销是每个条目 16 字节。

• 性能和/或内存使用方面相对较小的差异实际上对拥有性能或内存关键应用程序^{1 的}人来说非常重要。

^{1 - ... and also to people who obsess about these things unnecessarily.}

^{1 - ... 还有那些不必要地痴迷于这些事情的人。}

回答by stacker

• LinkedHashMap additionally maintains a doubly-linked list running through all of its entries, that will provide a reproducable order. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).
• HashMap doesn't have these extra costs (runtime,space) and should prefered over LinkedHashMap when you don't care about insertion order.

• LinkedHashMap 还维护一个双向链表，它贯穿其所有条目，这将提供可重复的顺序。这个链表定义了迭代顺序，这通常是键被插入到映射中的顺序（插入顺序）。
• HashMap 没有这些额外的成本（运行时间、空间），当您不关心插入顺序时，应该优先于 LinkedHashMap。

回答by Snehal

LinkedHashMap is a useful data structure when you need to know the insertion order of keys to the Map. One suitable use case is for the implementation of an LRU cache. Due to order maintenance of the LinkedHashMap, the data structure needs additional memory compared to HashMap. In case insertion order is not a requirement, you should always go for the HashMap.

LinkedHashMap 是一种有用的数据结构，当您需要知道 Map 中键的插入顺序时。一个合适的用例是实现 LRU 缓存。由于LinkedHashMap的顺序维护，数据结构比HashMap需要额外的内存。如果不需要插入顺序，则应始终使用 HashMap。

回答by rai.skumar

There is another major difference between HashMap and LinkedHashMap :Iteration is more efficient in case of LinkedHashMap.

HashMap 和 LinkedHashMap 之间还有另一个主要区别：在 LinkedHashMap 的情况下，迭代效率更高。

As Elements in LinkedHashMapare connected with each other so iteration requires time proportional to the size of the map, regardless of its capacity. But in case of HashMap; as there is no fixed order, so iteration over it requires time proportional to its capacity.

由于LinkedHashMap中的元素相互连接，因此无论其容量如何，迭代所需的时间都与地图的大小成正比。但在HashMap 的情况下；因为没有固定的顺序，所以迭代它需要与其容量成正比的时间。

I have put more details on my blog.

我已经在我的博客上添加了更多细节。

回答by Ankit Mittal

HashMapdoes not maintains insertion order, hence does not maintains any doubly linked list.

HashMap不维护插入顺序，因此不维护任何双向链表。

Most salient feature of LinkedHashMapis that it maintains insertion order of key-value pairs. LinkedHashMapuses doubly Linked List for doing so.

最显着的特点LinkedHashMap是它维护了键值对的插入顺序。LinkedHashMap为此使用双向链表。

Entry of LinkedHashMaplooks like this:

入口LinkedHashMap看起来像这样：

  static class Entry<K, V> {
     K key;
     V value;
     Entry<K,V> next;
     Entry<K,V> before, after;        //For maintaining insertion order    
     public Entry(K key, V value, Entry<K,V> next){
         this.key = key;
         this.value = value;
         this.next = next;
     }
  }

By using before and after - we keep track of newly added entry in LinkedHashMap, which helps us in maintaining insertion order.

通过使用 before 和 after - 我们跟踪新添加的条目 in LinkedHashMap，这有助于我们维护插入顺序。

Before refer to previous entry and after refers to next entry in LinkedHashMap.

之前指的是前一个条目，之后指的是 中的下一个条目LinkedHashMap。

For diagrams and step by step explanation please refer http://www.javamadesoeasy.com/2015/02/linkedhashmap-custom-implementation.html

有关图表和分步说明，请参阅http://www.javamadesoeasy.com/2015/02/linkedhashmap-custom-implementation.html

回答by punitusingh

LinkedHashMap inherits HashMap, that means it uses existing implementation of HashMap to store key and values in a Node (Entry Object). Other than this it stores a separate doubly linked list implementation to maintain the insertion order in which keys have been entered.

LinkedHashMap 继承了 HashMap，这意味着它使用 HashMap 的现有实现来存储节点（条目对象）中的键和值。除此之外，它还存储了一个单独的双向链表实现，以维护输入键的插入顺序。

It looks like this :

它看起来像这样：

header node <---> node 1 <---> node 2 <---> node 3 <----> node 4 <---> header node.

头节点<---> 节点1 <---> 节点2 <---> 节点3 <----> 节点4 <---> 头节点。

So extra overload is maintaining insertion and deletion in this doubly linked list. Benefit is : Iteration order is guaranteed to be insertion order, which is not in HashMap.

所以额外的重载是在这个双向链表中维护插入和删除。好处是：迭代顺序保证是插入顺序，不在HashMap中。

回答by Satish

• Re-sizing is supposed to be faster as it iterates through its double-linked list to transfer the contents into a new table array.
• containsValue() is Overridden to take advantage of the faster iterator.
• LinkedHashMap can also be used to create a LRU cache. A special LinkedHashMap(capacity, loadFactor, accessOrderBoolean) constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently. In this case, merely querying the map with get() is a structural modification.

• 重新调整大小应该更快，因为它遍历其双链表以将内容传输到新的表数组中。
• containsValue() 被覆盖以利用更快的迭代器。
• LinkedHashMap 也可用于创建 LRU 缓存。提供了一个特殊的 LinkedHashMap(capacity, loadFactor, accessOrderBoolean) 构造函数来创建一个链接哈希映射，其迭代顺序是其条目上次访问的顺序，从最近最少访问到最近访问。在这种情况下，仅使用 get() 查询地图是一种结构修改。