LinkedHashMap vs HashMap != LinkedList vs ArrayList

Question

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!

Answer 1

Doug Lea (author of TreeMap and java.util.concurrent) always slapped my (and my classmates') wrists whenever we used a LinkedList. To paraphrase him "there really isn't an good use case for using a LinkedList."

The advantage of an ArrayList is that is backed by an Array, thus whenever possible you have the speed of random access. The case against "inserting at the beginning of the list is faster with LinkedList" might be true, but System.arraycopy() is really fast, and that's what ArrayList uses.

http://www.docjar.com/html/api/java/util/ArrayList.java.html at line 460.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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).