LinkedHashMap vs HashMap！= LinkedList vs ArrayList

我读过LinkedHashMap的迭代速度比HashMap快，因为它的元素是双向链接的。另外，正因为如此，插入或删除元素时LinkedHashMap速度较慢。大概是因为这些链接也需要更新。LinkedHashMap vs HashMap！= LinkedList vs ArrayList

虽然我可以看到一个类似于链表VS ArrayList中，在链表的元素也被双向链接，我读了它遍历慢比ArrayList中，并且具有更快的插入和删除时间。

这是为什么？也许我在某个地方犯了错误？

干杯！

来源

2010-03-08 Markos Fragkakis

这个比喻不起作用。 LinkedList和ArrayList是List的两个不相关的实现。但是，LinkedHashMap与HashMap具有相同的数据结构，但其中包含一个LinkedList，以便使迭代更快更一致。

LinkedHashMap迭代比HashMap迭代更快的原因是HashMap迭代必须迭代所有的桶，甚至是空的迭代。 LinkedHashMap具有指向数据的列表意味着它可以跳过空桶。 LinkedHashMap中的列表是一个链表，因为删除时间保持不变（而不是O（n），如果它是一些支持arrray的列表）。

来源

2010-03-08 21:35:06 ILMTitan

+1注意跳过的空桶。此外，LinkedHashMap在遍历Map（插入或最后访问的订单）时提供可预测的排序;一个HashMap迭代器的顺序是不可预测的。 – 2010-03-09 06:47:53

一些细节：

迭代器为了LinkedHashMap的是相同的插入顺序到地图。所以LinkedList部分只需要在末尾“插入”（对于跟踪尾部的链表，O（1）），Map部分只做一个O（1）的映射插入。一般链接列表插入是O（N），并且在插入可能发生之前，ArrayList插入必须在1个插槽中阵列复制内容。

来源

2010-03-08 21:25:19 z5h

LinkedHashMap也可以构造为使用上次访问的顺序（请参阅http://java.sun.com/javase/6/docs/api/java/util/LinkedHashMap。HTML＃的LinkedHashMap％28int，％20float，％20boolean％29）。 – 2010-03-09 06:50:09

@凯文：很高兴知道！谢谢。 – z5h 2010-03-09 14:43:42

链接列表迭代运行时（访问每个元素）在理论上与数组列表相同。两者都需要O（n）（Big-O Notation）运行时。但是，由于数组的内存分配超过了连续的内存块（链接列表元素单独分配，并且可能位于内存中的任何位置），缓存将生效。

来源

2010-03-08 21:26:58

要迭代链表，必须在每个元素中跟随每个引用（链接）。这些引用几乎可以指向任何地方，但不能保证下一个元素跟在内存中的当前元素之后，这对缓存不利。由于每个参考都必须检索，因此速度较慢。数组在内存中是连续的，下一个元素就是当前元素的内存位置，并且元素的大小递增。

对于双向链表，数组中任何位置的插入都非常快，因为只需要更改前后元素的引用。另一方面，数组较慢，因为在任何点插入都会导致整个数组被复制以为新元素留出空间。即使追加一个元素也会导致在没有足够的连续内存分配给数组加上新添加的元素时复制整个数组。

您将特别注意处理大数据集时的插入差异。无论arraycopy()的速度有多快，双向链接列表的插入总是更快。因为HashMap很少迭代并依赖插入和排序，所以双向链表可能会提高性能。

来源

2010-03-08 21:32:22 Virtlink

是的，但Java的LinkedList有效地添加某些点的唯一方法是使用它的ListIterator。使用正常的add（n，o）方法需要在每次调用时迭代整个列表。当隐藏实现并使用List接口时，这会变得棘手，并且Java具有'RandomAccess'标记接口的原因之一。 – 2010-03-09 06:41:45

LinkedHashMap vs HashMap！= LinkedList vs ArrayList

回答

相关问题