46

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

4

8 回答 8

44

LinkedHashMap 会占用更多内存。法线中的每个条目都HashMap只有键和值。每个LinkedHashMap条目都有这些引用以及对下一个和上一个条目的引用。还有一点点家务要做，虽然这通常是无关紧要的。

于 2010-06-11T06:29:55.470 回答
30

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

您不应将复杂性与性能混为一谈。两种算法可以具有相同的复杂性，但其中一种算法的性能始终优于另一种。

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

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

其中C是一个常数。复杂性并没有说明C值的大小。对于两种不同的算法，常数C很可能是不同的。

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

话说回来：

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

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

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

1 - ...以及那些不必要地痴迷于这些事情的人。

于 2010-06-11T06:43:40.930 回答
16
  • LinkedHashMap 还维护了一个双向链表，贯穿其所有条目，这将提供可重现的顺序。这个链表定义了迭代顺序，通常是键插入映射的顺序（插入顺序）。
  • HashMap 没有这些额外成本（运行时、空间），当您不关心插入顺序时，应该优先于 LinkedHashMap。
于 2010-06-11T06:31:48.010 回答
9

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

于 2010-06-11T06:35:45.930 回答
7

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

由于LinkedHashMap中的元素相互连接，因此迭代所需的时间与地图的大小成正比，而不管其容量如何。但是在HashMap的情况下；由于没有固定的顺序，因此对其进行迭代需要与其容量成正比的时间。

我在我的博客上放了更多细节。

于 2012-12-28T11:10:20.830 回答
2

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 - 我们跟踪新添加的条目 in LinkedHashMap，这有助于我们维护插入顺序。

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

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

于 2015-05-04T09:41:02.360 回答
1

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

它看起来像这样：

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

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

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