LinkedHashMap 与 HashMap != LinkedList 与 ArrayList
我读到 LinkedHashMap 的迭代速度比 HashMap 更快，因为它的元素相互之间是双重链接的。此外，正因为如此，LinkedHashMap 在插入或删除元素时速度较慢。大概是因为这些链接也需要更新。
虽然我可以看到 LinkedList 与 ArrayList 的类比，因为 LinkedList 的元素也是双向链接的，但我读到它的迭代速度比 ArrayList 慢，并且插入和删除时间更快。
这是为什么呢？也许我在某个地方犯了错误？
干杯!
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.
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 slower than ArrayList, and has faster insertion and deletion times.
Why is this? Perhaps I am making a mistake somewhere?
Cheers!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
这个类比是行不通的。 LinkedList 和 ArrayList 是 List 的两个不相关的实现。然而，LinkedHashMap 与 HashMap 具有相同的数据结构，但其中融入了 LinkedList，以使迭代更快且一致。
LinkedHashMap迭代比HashMap迭代快的原因是HashMap迭代必须迭代所有桶，甚至是空桶。事实上 LinkedHashMap 有一个指向数据的列表，这意味着它可以跳过空桶。 LinkedHashMap 中的列表是一个链表，因为删除时间保持不变（如果是某种数组支持的列表，则不是 O(n)）。
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.
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).
链接列表迭代运行时（访问每个元素）“理论上”与数组列表相同。两者都需要 O(n)（Big-O 表示法）运行时间。但是，由于数组的内存分配是在连续的内存块上（链表元素是单独分配的，并且可能位于内存中的任何位置），因此缓存生效。
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.
一些细节：
LinkedHashMap 的迭代器顺序与映射中的插入顺序相同。因此 LinkedList 部分只需在末尾进行“插入”（对于跟踪尾部的链表来说，其复杂度为 O(1)），而 Map 部分仅执行映射插入，其复杂度为 O(1)。一般链表插入的时间复杂度为 O(N)，而 ArrayList 插入必须在插入发生之前将内容复制到 1 个槽上。
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.
要迭代链表，必须遵循每个元素中的每个引用（链接）。这些引用几乎可能指向任何地方，不能保证下一个元素跟随内存中的当前元素，这不利于缓存。由于必须检索每个引用，因此速度较慢。
数组在内存中是连续的，下一个元素只是当前元素的内存位置，随着元素的大小递增。
对于双向链表，在数组中的任何位置插入都非常快，因为只需更改前一个和后一个元素的引用。另一方面，数组速度较慢，因为在任何点插入都会导致复制整个数组以为新元素腾出空间。即使追加一个元素，当没有足够的连续内存分配给数组加上新添加的元素时，也会导致整个数组被复制。
在处理大数据集时，您会特别注意到插入差异。无论 arraycopy() 有多快，双向链表的插入速度总是更快。由于 HashMap 很少迭代并且依赖于插入和顺序，因此双向链表可能会提高性能。
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.