How do I efficiently iterate over each entry in a Java Map?

Question

If I have an object implementing the Map interface in Java and I wish to iterate over every pair contained within it, what is the most efficient way of going through the map?

Will the ordering of elements depend on the specific map implementation that I have for the interface?

Solution 1

Map<String, String> map = ...
for (Map.Entry<String, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + "/" + entry.getValue());
}

On Java 10+:

for (var entry : map.entrySet()) {
    System.out.println(entry.getKey() + "/" + entry.getValue());
}

Solution 2

To summarize the other answers and combine them with what I know, I found 10 main ways to do this (see below). Also, I wrote some performance tests (see results below). For example, if we want to find the sum of all of the keys and values of a map, we can write:

1. Using iterator and Map.Entry

   long i = 0;
   Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
   while (it.hasNext()) {
       Map.Entry<Integer, Integer> pair = it.next();
       i += pair.getKey() + pair.getValue();
   }
   

2. Using foreach and Map.Entry

   long i = 0;
   for (Map.Entry<Integer, Integer> pair : map.entrySet()) {
       i += pair.getKey() + pair.getValue();
   }
   

3. Using forEach from Java 8

   final long[] i = {0};
   map.forEach((k, v) -> i[0] += k + v);
   

4. Using keySet and foreach

   long i = 0;
   for (Integer key : map.keySet()) {
       i += key + map.get(key);
   }
   

5. Using keySet and iterator

   long i = 0;
   Iterator<Integer> itr2 = map.keySet().iterator();
   while (itr2.hasNext()) {
       Integer key = itr2.next();
       i += key + map.get(key);
   }
   

6. Using for and Map.Entry

   long i = 0;
   for (Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator(); entries.hasNext(); ) {
       Map.Entry<Integer, Integer> entry = entries.next();
       i += entry.getKey() + entry.getValue();
   }
   

7. Using the Java 8 Stream API

   final long[] i = {0};
   map.entrySet().stream().forEach(e -> i[0] += e.getKey() + e.getValue());
   

8. Using the Java 8 Stream API parallel

   final long[] i = {0};
   map.entrySet().stream().parallel().forEach(e -> i[0] += e.getKey() + e.getValue());
   

9. Using IterableMap of Apache Collections

   long i = 0;
   MapIterator<Integer, Integer> it = iterableMap.mapIterator();
   while (it.hasNext()) {
       i += it.next() + it.getValue();
   }
   

10. Using MutableMap of Eclipse (CS) collections

    final long[] i = {0};
    mutableMap.forEachKeyValue((key, value) -> {
        i[0] += key + value;
    });
    

Perfomance tests (mode = AverageTime, system = Windows 8.1 64-bit, Intel i7-4790 3.60 GHz, 16 GB)

1. For a small map (100 elements), score 0.308 is the best

   Benchmark                          Mode  Cnt  Score    Error  Units
   test3_UsingForEachAndJava8         avgt  10   0.308 ±  0.021  µs/op
   test10_UsingEclipseMap             avgt  10   0.309 ±  0.009  µs/op
   test1_UsingWhileAndMapEntry        avgt  10   0.380 ±  0.014  µs/op
   test6_UsingForAndIterator          avgt  10   0.387 ±  0.016  µs/op
   test2_UsingForEachAndMapEntry      avgt  10   0.391 ±  0.023  µs/op
   test7_UsingJava8StreamApi          avgt  10   0.510 ±  0.014  µs/op
   test9_UsingApacheIterableMap       avgt  10   0.524 ±  0.008  µs/op
   test4_UsingKeySetAndForEach        avgt  10   0.816 ±  0.026  µs/op
   test5_UsingKeySetAndIterator       avgt  10   0.863 ±  0.025  µs/op
   test8_UsingJava8StreamApiParallel  avgt  10   5.552 ±  0.185  µs/op
   

2. For a map with 10000 elements, score 37.606 is the best

   Benchmark                           Mode   Cnt  Score      Error   Units
   test10_UsingEclipseMap              avgt   10    37.606 ±   0.790  µs/op
   test3_UsingForEachAndJava8          avgt   10    50.368 ±   0.887  µs/op
   test6_UsingForAndIterator           avgt   10    50.332 ±   0.507  µs/op
   test2_UsingForEachAndMapEntry       avgt   10    51.406 ±   1.032  µs/op
   test1_UsingWhileAndMapEntry         avgt   10    52.538 ±   2.431  µs/op
   test7_UsingJava8StreamApi           avgt   10    54.464 ±   0.712  µs/op
   test4_UsingKeySetAndForEach         avgt   10    79.016 ±  25.345  µs/op
   test5_UsingKeySetAndIterator        avgt   10    91.105 ±  10.220  µs/op
   test8_UsingJava8StreamApiParallel   avgt   10   112.511 ±   0.365  µs/op
   test9_UsingApacheIterableMap        avgt   10   125.714 ±   1.935  µs/op
   

3. For a map with 100000 elements, score 1184.767 is the best

   Benchmark                          Mode   Cnt  Score        Error    Units
   test1_UsingWhileAndMapEntry        avgt   10   1184.767 ±   332.968  µs/op
   test10_UsingEclipseMap             avgt   10   1191.735 ±   304.273  µs/op
   test2_UsingForEachAndMapEntry      avgt   10   1205.815 ±   366.043  µs/op
   test6_UsingForAndIterator          avgt   10   1206.873 ±   367.272  µs/op
   test8_UsingJava8StreamApiParallel  avgt   10   1485.895 ±   233.143  µs/op
   test5_UsingKeySetAndIterator       avgt   10   1540.281 ±   357.497  µs/op
   test4_UsingKeySetAndForEach        avgt   10   1593.342 ±   294.417  µs/op
   test3_UsingForEachAndJava8         avgt   10   1666.296 ±   126.443  µs/op
   test7_UsingJava8StreamApi          avgt   10   1706.676 ±   436.867  µs/op
   test9_UsingApacheIterableMap       avgt   10   3289.866 ±  1445.564  µs/op
   

Graphs (performance tests depending on map size)

Table (perfomance tests depending on map size)

          100     600      1100     1600     2100
test10    0.333    1.631    2.752    5.937    8.024
test3     0.309    1.971    4.147    8.147   10.473
test6     0.372    2.190    4.470    8.322   10.531
test1     0.405    2.237    4.616    8.645   10.707
test2     0.376    2.267    4.809    8.403   10.910
test7     0.473    2.448    5.668    9.790   12.125
test9     0.565    2.830    5.952   13.220   16.965
test4     0.808    5.012    8.813   13.939   17.407
test5     0.810    5.104    8.533   14.064   17.422
test8     5.173   12.499   17.351   24.671   30.403

All tests are on GitHub.

Solution 3

In Java 8 you can do it clean and fast using the new lambdas features:

 Map<String,String> map = new HashMap<>();
 map.put("SomeKey", "SomeValue");
 map.forEach( (k,v) -> [do something with key and value] );

 // such as
 map.forEach( (k,v) -> System.out.println("Key: " + k + ": Value: " + v));

The type of k and v will be inferred by the compiler and there is no need to use Map.Entry anymore.

Easy-peasy!

Solution 4

Yes, the order depends on the specific Map implementation.

@ScArcher2 has the more elegant Java 1.5 syntax. In 1.4, I would do something like this:

Iterator entries = myMap.entrySet().iterator();
while (entries.hasNext()) {
  Entry thisEntry = (Entry) entries.next();
  Object key = thisEntry.getKey();
  Object value = thisEntry.getValue();
  // ...
}

Solution 5

Typical code for iterating over a map is:

Map<String,Thing> map = ...;
for (Map.Entry<String,Thing> entry : map.entrySet()) {
    String key = entry.getKey();
    Thing thing = entry.getValue();
    ...
}

HashMap is the canonical map implementation and doesn't make guarantees (or though it should not change the order if no mutating operations are performed on it). SortedMap will return entries based on the natural ordering of the keys, or a Comparator, if provided. LinkedHashMap will either return entries in insertion-order or access-order depending upon how it has been constructed. EnumMap returns entries in the natural order of keys.

(Update: I think this is no longer true.) Note, IdentityHashMap entrySet iterator currently has a peculiar implementation which returns the same Map.Entry instance for every item in the entrySet! However, every time a new iterator advances the Map.Entry is updated.

View more solutions

Comments

[Nitin Mahesh]

In Java 8 using Lambda Expression: stackoverflow.com/a/25616206/1503859

[akhil_mittal]

Java 8: stackoverflow.com/questions/46898/…

[jai]

Prefer for-loop than while.. for(Iterator entries = myMap.entrySet().iterator(); entries.hasNext(); ) {...} With this syntax the 'entries' scope is reduced to the for loop only.

[Jeff Olson]

This is not the best approach, it's much more efficient to use the entrySet(). Findbugs will flag this code (see findbugs.sourceforge.net/…)

[ScArcher2]

If you do that, then it won't work as Entry is a nested Class in Map. java.sun.com/javase/6/docs/api/java/util/Map.html

[Paul Efford]

you can write the import as "import java.util.Map.Entry;" and it will work.

[Premraj]

EnumMap also has this peculiar behaviour along with IdentityHashMap

[liran]

@jpredham You are right that using the for construct as for (Entry e : myMap.entrySet) will not allow you to modify the collection, but the example as @HanuAthena mentioned it should work, since it gives you the Iterator in scope. (Unless I'm missing something...)

[Steve Kuo]

You should put Iterator in a for loop to limit its scope.

[assylias]

@Pureferret The only reason you might want to use an iterator is if you need to call its remove method. If that is the case, this other answer shows you how to do it. Otherwise, the enhanced loop as shown in the answer above is the way to go.

[kritzikratzi]

@JeffOlson meh, not really. map lookup is O(1) so both loops behave the same way. admittedly, it will be slightly slower in a micro benchmark but i sometimes do this as well because i hate writing the type arguments over and over again. Also this will quite likely never be your performance bottleneck, so go for it if it makes the code more readable.

[Jeff Olson]

@kritzikratzi but with the entrySet() approach, you're doing one lookup for each element, whereas with the keySet()/get() approach, you're doing two lookups for each element. So in theory (haven't tested it), it is O(1) vs. 2 * O(1). Or twice as long. Right?

[kritzikratzi]

more in detail: O(1) = 2*O(1) is pretty much the definition of the big O notation. you're right in that it runs a bit slower, but in terms of complexity they're the same.

[kornero]

Look up in map is O(1), really?))))) Where on Earth it is O(1)?))) HashMap: First - you must calculate hash, second - search in array by hash, third! - linear search through all elements wich has the same hashCode, this calls 'collision', don't you hear about it? =) And what can you say about: TreeMap, ConcurrentSkipListMap are they 'O(1)', too?

[kritzikratzi]

@kornero good point, treemap lookup is O(log n), i only had hashmaps in mind (which are ~ O(1), collisions or not)

[kornero]

@kritzikratzi collisions in hashmaps makes complexity ~ O(n), and there is "Denial of Service via Algorithmic Complexity Attacks" based on this, you can read more about it here: cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003

[kritzikratzi]

by collision or not i meant it doesn't matter if you a few collisions, obviously it's a different story if you have only collisions. so you're being pretty petty, but yep, what you're saying is true.

[Vitalii Fedorenko]

Depending on what you want to do with a map, you can also use stream API on the entries returned by map.entrySet().stream() docs.oracle.com/javase/8/docs/api/java/util/stream/Stream.ht‌​ml

[humblerookie]

@injecteer: Seems the motive of lambda expressions

[Josiah Yoder]

I believe the form Map.Entry is clearer than importing the inner class into the current namespace.

[JohnK]

IntelliJ is giving me errors on Entry thisEntry = (Entry) entries.next();: doesn't recognize Entry. Is that pseudocode for something else?

[liran]

@JohnK try importing java.util.Map.Entry.

[StudioWorks]

@SteveKuo What do you mean by "limit its scope" ?

[ComFreek]

@StudioWorks for (Iterator<Map.Entry<K, V>> entries = myMap.entrySet().iterator(); entries.hasNext(); ) { Map.Entry<K, V> entry = entries.next(); }. By using that construct we limit the scope of (visibility of the variable) entries to the for loop.

[jpaugh]

"LinkedHashMap will either return entries in [...] access-order [...]" ... so you access the elements in the order you access them? Either tautological, or something interesting which could use a digression. ;-)

[Brett]

@jpaugh Only direct accesses to the LinkedHashMap count. Those through iterator, spliterator, entrySet, etc., do not modify the order.

[GPI]

@Viacheslav : very nice answer. Just wondering how Java8 apis are hindered, in your benchmark, by capturing lambdas... (e.g. long sum = 0; map.forEach( /* accumulate in variable sum*/); captures the sum long, which may be slower than say stream.mapToInt(/*whatever*/).sum for example. Of course you can not always avoid capturing state, but that may be a reasonnable addition to the bench.

[dguay]

Note that you can use map.values() or map.keySet() if you want to loop through values or keys only.

[Holger]

@Jeff Olson: the comments that the “Big O” complexity doesn’t change, when there is only a constant factor, is correct. Still, to me it matters whether an operation takes one hour or two hours. More important, it must be emphasized that the factor is not 2, as iterating over an entrySet() does not bear a lookup at all; it’s just a linear traversal of all entries. In contrast, iterating over the keySet() and performing a lookup per key bears one lookup per key, so we’re talking about zero lookups vs. n lookups here, n being the size of the Map. So the factor is way beyond 2…

[Holger]

@kornero: it might be worth noting that you don’t need the keys to have the same hashcode to have a collision; there’s already a collision when hashcode % capacity is the same. Starting with Java 8, the complexity for items having the same hashcode % capacity, but different hashcode or are Comparable falls back to O(log n) and only keys having the same hash code and not being Comparable impose O(n) complexity. But the statement that the complexity of a lookup can be more than O(1) in practice still holds.

[Holger]

You don’t need a stream if you just want to iterate over a map. myMap.forEach( (currentKey,currentValue) -> /* action */ ); is much more concise.

[Admin]

This solution will not work if you have a integer key and String key.

[Holger]

@ZhekaKozlov: look at the mindblowingly large error values. Consider that a test result of x±e implies that there were result within the interval from x-e to x+e, so the fastest result (1184.767±332.968) ranges from 852 to 1518, whereas the second slowest (1706.676±436.867) runs between 1270 and 2144, so the results still overlap significantly. Now look at the slowest result, 3289.866±1445.564, which implies diverging between 1844 and 4735 and you know that these test results are meaningless.

[Chris]

This won't work if you want to reference non-final variables declared outside your lambda expression from within the forEach()...

[The Coordinator]

@Chris Correct. It won't work if you try to use effectively non-final variables from outside the lambda.

[Thierry]

What about comparing the 3 main implementations : HashMap, LinkedHashMap and TreeMap ?

[Peter Mortensen]

1. though → if? 2. The last paragraph might benefit from a brush-up.

[ErikE]

#1 and #6 are exactly the same. Using while vs. a for loop is not a different technique for iterating. And I am surprised they have such variation between them in your tests—which suggests that the tests are not properly isolated from external factors unrelated to the things you intend to be testing.

[michaeak]

Well, this is unnecessarily slow because first get the keys and then the entries. Alternative: Get the entrySets and then for each entryset the key and the value

[Todd Sewell]

#8 is a terrible example, because of the parallel there's now a race condition when adding to i.

[AlexB]

The run times are taken from the article, which does not use the Java Microbenchmarking Harness. The times are therefore unreliable, as the code could, for example, have been completely optimised out by the JIT compiler.

[edin-m]

keySet() is slow

[Basil Bourque]

This was covered in the Answer by Lova Chittumuri. Also covered as item # 3 in the highly-upvoted Answer by Viacheslav Vedenin.

[filpa]

Late comment on an answer that's also late to the party (but very informative). +1 from me for mentioning EnumMap, since it's the first time I've heard of it. There's probably many cases where this might come in handy.

[Mahbubur Rahman Khan]

But only available in API label 24

[Ali Mamedov]

It works perfectly. Thank you!

[Ali Mamedov]

It works perfectly. Thank you!

[Rubén Colomina Citoler]

The order in which register were inserted isn't respected when you loop them after

[Mo'ath Hasan Alshorman]

@JosiahYoder No need to import the inner class Map.Entry since var handling the reference for you.