HashMap or TreeMap or LinkedHashMap which one is fastest to iterate over?

Question

I have a Map which is filled up during the start up of application. It doesn't change later during the execution of application. Later this map is only used to iterate all the elements in it. Which concrete implementation of Map should I choose? HashMap or TreeMap or LinkedHashMap ?
UPDATE
Insertion order doesn't matter. The only thing that matters is fast iteration of all elements (say 6000 elements).

Answer 1

HashMap will generally be fastest, since it has the best cache behavior (HashMap iterates directly over the backing array, whereas TreeMap and LinkedHashMap iterate over linked data structures).

You may want to use an ImmutableMap or UnmodifiableMap if the map isn't going to change once it's initialized

Answer 2

None of the other answers here take into consideration the effects of the CPU cache, which can be huge when iteration is concerned.

One way to improve this is to use just a single array of interleaved keys and values (keys at even indices, values at odd ones). This will tightly group together these data items and maximally leverage the cache, at least for the references.

But the true, screaming improvement would be achieved if you could avoid creating objects which hold your data and use just arrays of primitive values. This is, naturally, highly dependent on your use case.

Answer 3

I wouldn't use the map. If all you want is to iterate through the entries make a new ArrayList of what you need and use that - you cannot get faster than an ArrayList for iteration.

// Which map you use only chooses the order of the list.
Map<Key,Value> map = new HashMap<>();
// The list to iterate for maximum speed.
List<Map.Entry<Key,Value>> list = new ArrayList<>(map.entrySet());

This way you iterate across the entry set just once to build the list. From then on you are iterating across the list again and again - which certainly should be close to optimal.

Note Changed from LinkedList to ArrayList on Marko's suggestion.

Answer 4

If your map is used only to iterate over elements and the speed of iteration is important, then convert the map into an ArrayList and iterate over it, this will be the fastest way.

Answer 5

I agree with Zim-Zam's answer, and add something: if you need to access both the keys and the values during the iteration, the fastest way is using the entrySet() method, as discussed here.

Now, if you're sure that the map is never going to change, why not use a separate data structure for iteration? for example: iterate once over the finished map and fill with its contents a couple of arrays, one with the keys and the other with the values, in the same corresponding positions. Then traversing those arrays will be as fast as it can get.

Answer 6

As of Java 10 you can use one of the Map.of() overloaded methods or Map.copyOf() to create an unmodifiable Map. As the map returned by these methods doesn't support putting any new entries into the map, the existing keys/values are stored in an interleaving pattern as described in this answer. This should offer the best performance for your use case.

Answer 7

The Map.forEach(BiConsumer) is almost always faster than Iterators, sometimes by a large margin. If you were summing the values for example:

public class TestForStackOverflow {
    int sum = 0;

    // Or whatever Map you are using
    Map<Object, Integer> map = new HashMap();

    static class C implements BiConsumer<Object, Integer> {
        int sum = 0;

        @Override
        public void accept(Object k, Integer v) {
            sum += v;
        }
    }

    public int getSum(Map map) {
        C c = new C();
        map.forEach(c);
        return c.sum;
    }

    public int getSum2(Map map) {
        map.forEach((k, v) -> sum += v);
        return sum;
    }
}