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

27

LinkedHashMap将占用更多内存。正常的HashMap中的每个条目都具有密钥和值。每个LinkedHashMap条目具有对下一个和前一个条目的引用和的引用。还有一点家务要做，尽管这通常是无关紧要的。

2010-06-11 06:29:55

+0

其结果是，性能稍低相比HashMap中的。 – Snehal 2010-06-11 06:32:21

+0

@Jon Skeet它是不是像LinkedHashMap中的值包含对上一个值和下一个值的额外引用，删除或插入任何项目都需要额外的费用来重新连接？如果我得到完整的实现或者有链接或解释，那将是非常棒的。 – 2010-06-11 06:39:41

+0

@热情的程序员：源代码是公开的 - 为什么不看那里？是的，插入和删除确实需要更新链接列表。 – 2010-06-11 06:58:24

10

LinkedHashMap还维护一个双向链接列表，其中运行所有条目，这将提供一个可重复的顺序。这个链表定义了迭代排序，这通常是键被插入映射的顺序（插入顺序）。
HashMap没有这些额外成本（运行时间，空间），并且当您不关心广告订单时应该首选LinkedHashMap。

来源

2010-06-11 06:31:48 stacker

+0

我认为你的意思是迭代次序？ – 2011-11-13 00:29:39

+0

@MichaelDeardeuff你是对的，但答案通常是正确的，因为迭代顺序=插入顺序deafult。可能替代*插入顺序*是*访问顺序*。 – 2014-12-16 09:58:31

5

当你需要知道键的映射顺序时，LinkedHashMap是一个有用的数据结构。一个合适的用例是用于实现LRU缓存。由于LinkedHashMap的维护顺序，与HashMap相比，数据结构需要额外的内存。在插入顺序不是要求的情况下，您应该始终使用HashMap。

来源

2010-06-11 06:35:45 Snehal

20

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

您不应该将复杂性与性能混淆。两种算法可以具有相同的复杂性，但是可以一致地执行比其他更好的算法。

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

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

其中C1和C2是严格为正的常数。复杂性没有说明数值有多大或多么小。对于两种不同的算法，常数很可能是不同的。

（请记住，大O的复杂性有关的行为/性能N变得非常大。它会告诉你什么关于小N值的行为/性能。）

话虽如此，在等效用例中的HashMap和LinkedHashMap操作之间的性能差异相对较小。通常，更多相关的额外内存开销。

来源

2010-06-11 06:43:40

+1

这是一组优秀的区别。 – Jared 2016-02-26 20:33:07

4

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

如LinkedHashMap的元素被相互连接，以便迭代需要时间正比于地图的大小，不管其容量。但是在HashMap;因为没有固定的顺序，所以迭代它需要时间与其容量成正比。

我在我的blog上放了更多细节。

来源

2012-12-28 11:10:20

0

重新上浆应该是较快，因为它通过其双链表遍历到的内容传送到一个新的表阵列。
containsValue（）被覆盖以利用更快的迭代器。
LinkedHashMap也可用于创建LRU缓存。提供了一个特殊的 LinkedHashMap（capacity，loadFactor，accessOrderBoolean）构造函数用于创建链接哈希映射，其迭代顺序为上次访问它的条目的顺序，从最近最少访问到最近访问的。在这种情况下，只有用get（）查询地图是一个结构修改。

来源

2013-02-05 13:54:25 Satish

1

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

它看起来像这样：

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

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

来源

2014-02-01 18:33:47 punitusingh

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

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

之前参考前条目和之后提到LinkedHashMap的下一个条目。

对于图和一步一步的说明请参考http://www.javamadesoeasy.com/2015/02/linkedhashmap-custom-implementation.html

来源

2015-05-04 09:41:02

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

回答

相关问题