HashMap vs LinkedHashMap performance in iteration over values()
Solution 1
I think the LinkedHashMap
has to be faster in traversal due to a superior nextEntry
implementation in its Iterator
Here is why :
Let us go step by step from the values
implementation.
The HashMap
implementation of values
is this :
public Collection<V> values() {
Collection<V> vs = values;
return (vs != null ? vs : (values = new Values()));
}
The LinkedHashMap
extends from HashMap
and inherits the same implementation.
The difference is in the Iterator
implementation for the Values
in both.
for HashMap
it extends from java.util.HashMap.HashIterator
private final class ValueIterator extends HashIterator<V> {
public V next() {
return nextEntry().value;
}
}
but for LinkedHashMap
it extends from java.util.LinkedHashMap.LinkedHashIterator
private class ValueIterator extends LinkedHashIterator<V> {
public V next() { return nextEntry().value; }
}
so the difference essentially boils down to nextEntry
implementation.
For LinkedHashMap
it is just calling e.after where e is the Entry
,
but for HashMap
there is some work involved in traversing the Entry[]
array to find the next next.
UPDATE : Code for nextEntry()
in HashMap
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
The Entry[] is not a contiguous store. (There could be null values in between). If you take a look at the above code, what it does is point next to current and find the next next by iterating over the Entry[] .
But I think this performance gain will come at the cost of insertion. Check out the addEntry
method in both classes as an exercise.
Solution 2
I wrote a little profiling program creating 1 million keys (Integer) vs Boolean.TRUE, repeating 100 times. Found the following:
HashMap:-
Create: 3.7sec
Iterate: 1.1sec
Access: 1.5sec
Total: 6.2sec
LinkedHashMap:-
Create: 4.7sec (30% slower)
Iterate: 0.5sec (50% faster)
Access: 0.8sec (50% faster)
Total : 6.0sec
Garbage collection NOT done so pollutes the numbers somewhat, however I think LinkedHashMap has the edge over HashMap and I will be using that in future code.
Solution 3
It almost does not matter. The question is: what do you need. If order of elements is relevant you have to use LinkedHashMap
. Otherwise you just do not need it, so use HashMap
.
Solution 4
Yes, there will be the same performance difference as you get in all iterations over HashMap
versus LinkedHashMap
: HashMap
will take time proportional to the number of entries plus the size of the hash table, and LinkedHashMap
will just take time proportional to the number of entries.
Solution 5
I tried in an UnitTest, iterated values() 10000 times, the milliseconds: 806 vs 902. It is almost the same.
Comments
-
MBZ almost 4 years
Is there any performance difference between
HashMap
andLinkedHashMap
for traversal throughvalues()
function? -
exexzian over 11 yearscould you please elaborate or edit this phrase
"but for HashMap there is some work involved in traversing the Entry[] array to find the next next."
-
Marcus almost 6 yearsFor iterations, it makes sense especially given the above comments, but it's unclear to me how accesses are faster with
LinkedHashMap
. It makes no sense to me howLinkedHashMap
'sget(Object key)
function which essentially does the same thing asHashMap
'sget(Object key)
function, plus checks anafterNodeAccess()
function before returning the result would have a faster performance. -
ACV almost 6 yearsI don't think your test is correct and done properly
-
Mark Jeronimus almost 5 yearsUsing
LinkedHashMap
speeds up a certain task from 25 seconds to 8 seconds! I iterate over the entire map for each entry that I insert (to do some value-specific relationship fixing), so O(N^2). (86MnextNode()
invocations, hashtable has size 1M and ~13K elements) -
Jeffrey Blattman over 2 yearsThat's an 11% difference. That is significant.