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

Question

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

- Passionate programmer

Answer 1

LinkedHashMap会占用更多的内存。在普通的HashMap中，每个条目只有键和值。而每个LinkedHashMap的条目除了键和值之外，还包括对下一个和前一个条目的引用。此外，还需要进行一些额外的管理工作，尽管这通常是不相关的。

- Jon Skeet

---

@Jon Skeet，LinkedHashMap 中的值是否包含对前一个和后一个值的额外引用，因此删除或插入任何项都需要额外的重新连接成本？如果我能获得完整的实现，无论是链接还是解释，那就太好了。 - Passionate programmer

@Jon Skeet 感谢您的帮助，我不认为我在那个URL中有源代码，我应该登录吗？ - Passionate programmer

@热爱编程的程序员 - 找Java源代码的一种方法是通过谷歌搜索；例如，搜索"java.util.HashMap.java.html"，你会得到各个版本的结果。 - Stephen C

@StinePike：嗯，从“行为”角度来看确实有所不同 - 但在查找、添加项目等方面的时间花费方面，它们基本上是相当的。（在复杂性方面-常数因子可能略有不同。） - Jon Skeet

如下所述，LinkedHashMap在迭代时更有效率。这会对调整大小产生一些影响。此外，如果您传递一个带有期望消费者查看每个节点的映射，那么这可能是更好的选择。然而，由于小的开销，puts/removes通常会稍微慢一些。 - ticktock

Answer 2

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

您不应将复杂度与性能混淆。两个算法可以具有相同的复杂度，但其中一个可能始终表现更好。

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

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

其中 C 是一个常数。算法的复杂度并不代表 C 值大小的优劣。对于两个不同的算法，常量 C 很可能是不同的。

(还要记住，大O复杂度是关于当 N 变得非常大时的行为/性能。它并没有告诉你关于更小的 N 值的行为/性能。)

---

即便如此：

• HashMap和LinkedHashMap等价使用情况下的性能差异相对较小。

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

• 相对较小的性能和/或内存使用差异实际上对那些对性能或内存至关重要的应用程序的人们来说可能很重要¹。

^{1- ... 还有那些毫无必要地过分关注这些事情的人。}

- Stephen C

Answer 3

• LinkedHashMap 额外维护一个双向链表，包含所有的元素，可以提供可重复的顺序。这个链表定义了迭代顺序，通常是按照插入 key 的顺序（插入顺序）。
• HashMap 不存在这些额外的开销（运行时间、空间），当您不关心插入顺序时，应该优先选择它。

- stacker

---

我想你是指迭代顺序？ - Michael Deardeuff

@MichaelDeardeuff 你说得对，但通常情况下答案是正确的，因为默认情况下“迭代顺序=插入顺序”。插入顺序的可能替代方案是访问顺序。 - G. Demecki

Answer 4

LinkedHashMap是一种有用的数据结构，当您需要了解键插入到Map的顺序时可以使用它。一个适当的用例是实现LRU缓存。由于LinkedHashMap维护顺序，相比于HashMap，该数据结构需要额外的内存。如果插入顺序不是必要的，则应始终选择HashMap。

- Snehal

Answer 5

HashMap和LinkedHashMap之间还有一个重要的区别：在迭代方面，LinkedHashMap更加高效。 由于LinkedHashMap中的元素相互连接，因此迭代所需的时间与其容量成比例，而与其大小无关。但是在HashMap的情况下，由于没有固定顺序，因此对其进行迭代需要与其容量成比例的时间。

我在博客中提供了更多细节。

- rai.skumar

Answer 6

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

LinkedHashMap最显著的特点是它维护键值对的插入顺序。为了实现这一点，LinkedHashMap使用双向链表。

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;
     }
  }

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

Before 指向前一个条目，而 after 指向 LinkedHashMap 中的下一个条目。

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

- Ankit Mittal

Answer 7

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

它看起来像这样：

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

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

- punitusingh

Answer 8

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

- Satish