java LinkedHashMap vs HashMap != LinkedList vs ArrayList

LinkedHashMap vs HashMap != LinkedList vs ArrayList

提问by Markos Fragkakis

I have read that LinkedHashMap has faster iteration speed than HashMap because its elements are doubly linked to each other. Additionally, because of this, LinkedHashMap is slower when inserting or deleting elements. Presumably because these links also need to be updated.

我读过 LinkedHashMap 比 HashMap 具有更快的迭代速度，因为它的元素彼此双重链接。此外，正因如此，LinkedHashMap 在插入或删除元素时速度较慢。大概是因为这些链接也需要更新。

Although I can see an analogy to LinkedList vs ArrayList, in that the elements of LinkedList are also doubly-linked, I read that it iterates slowerthan ArrayList, and has faster insertion and deletion times.

虽然我可以看到 LinkedList 与 ArrayList 的类比，因为 LinkedList 的元素也是双向链接的，但我读到它的迭代速度比 ArrayList慢，并且插入和删除时间更快。

Why is this? Perhaps I am making a mistake somewhere?

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

Cheers!

干杯!

回答by ILMTitan

The analogy does not work. LinkedList and ArrayList are two unrelated implementations of a List. LinkedHashMap, however, is the same data structure as a HashMap but with a LinkedList woven into it to make iteration faster and consistent.

这个类比是行不通的。LinkedList 和 ArrayList 是 List 的两个不相关的实现。然而，LinkedHashMap 是与 HashMap 相同的数据结构，但其中编织了一个 LinkedList 以使迭代更快和一致。

The reason that LinkedHashMap iteration is faster than HashMap iteration is that HashMap iteration has to iterate over all of the buckets, even the empty ones. The the fact that LinkedHashMap has a list pointing to the data means that it can skip the empty buckets. The list in the LinkedHashMap is a linked list because removal times remain constant (rather than O(n) if it was some arrray-backed list).

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

回答by Kevin Sylvestre

Linked lists iteration run-times (accessing each element) are 'theoretically' the same as an array list. Both require O(n) (Big-O Notation) runtime. However, because memory allocation for arrays is over a continuous block of memory (linked lists elements are allocated individually and may be anywhere in memory), caching comes into effect.

链表迭代运行时间（访问每个元素）“理论上”与数组列表相同。两者都需要 O(n)（Big-O Notation）运行时。然而，因为数组的内存分配是在一个连续的内存块上进行的（链表元素是单独分配的，可能在内存中的任何地方），缓存开始生效。

回答by z5h

Some details:

一些细节：

The iterator order for LinkedHashMap is the same as insertion order into the map. So the LinkedList portion only has to "insert" at the end (which is O(1) for a linked list that keeps track of the tail), and the Map portion only does a map insert which is O(1). A general linked-list insert is O(N) and an ArrayList insert has to array-copy the contents over 1 slot before an insert can happen.

LinkedHashMap 的迭代器顺序与插入到映射中的顺序相同。因此，LinkedList 部分只需在末尾“插入”（对于跟踪尾部的链表，这是 O(1)），而 Map 部分仅执行 O(1) 的映射插入。一般的链表插入是 O(N) 并且 ArrayList 插入必须在插入之前将内容数组复制到 1 个插槽上。

回答by Daniel A.A. Pelsmaeker

To iterate a linked list, one has to follow each and every reference (link) in each element. These references may point almost anywhere, there is no guarantee that the next element follows the current one in memory, which is bad for caching. Because each reference has to be retrieved, it is slower. Arrays are continuous in memory and the next element is just the memory location of the current element incremented with the size of the element.

要迭代一个链表，必须遵循每个元素中的每一个引用（链接）。这些引用几乎可以指向任何地方，不能保证下一个元素跟随内存中的当前元素，这对缓存不利。因为必须检索每个引用，所以速度较慢。数组在内存中是连续的，下一个元素就是当前元素的内存位置，随着元素的大小增加。

For a doubly linked list, insertion anywhere in the array is very fast because only references of the preceding and following element have to be changed. An array, on the other hand, is slower because insertion at any point will cause the entire array to be copied to make space for the new element. Even appending an element will also cause the entire array to be copied when there is not enough continuous memory allocated for the array plus the newly added element.

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

You'll especially notice the insertion differences when dealing with big datasets. No matter how fast arraycopy()may be, a doubly linked list is always faster for insertion. Because HashMaps are rarely iterated and rely on insertion and order, a doubly linked list might give it a performance boost.

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