Iterating Map Entries Efficiently

suggest change

This section provides code and benchmarks for ten unique example implementations which iterate over the entries of a Map<Integer, Integer> and generate the sum of the Integer values. All of the examples have an algorithmic complexity of Θ(n), however, the benchmarks are still useful for providing insight on which implementations are more efficient in a “real world” environment.

Implementation using Iterator with Map.Entry

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

Implementation using for with Map.Entry

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

Implementation using Map.forEach (Java 8+)

map.forEach((k, v) -> sum[0] += k + v);

Implementation using Map.keySet with for

for (Integer key : map.keySet()) {
    sum += key + map.get(key);
}

Implementation using Map.keySet with Iterator

Iterator<Integer> it = map.keySet().iterator();
while (it.hasNext()) {
    Integer key = it.next();
    sum += key + map.get(key);
}

Implementation using for with Iterator and Map.Entry

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

Implementation using Stream.forEach (Java 8+)

map.entrySet().stream().forEach(e -> sum += e.getKey() + e.getValue());

Implementation using Stream.forEach with Stream.parallel (Java 8+)

map.entrySet()
   .stream()
   .parallel()
   .forEach(e -> sum += e.getKey() + e.getValue());

Implementation using IterableMap from Apache Collections

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

Implementation using MutableMap from Eclipse Collections

mutableMap.forEachKeyValue((key, value) -> {
    sum += key + value;
});

Performance Tests (Code available on Github)

Test Environment: Windows 8.1 64-bit, Intel i7-4790 3.60GHz, 16 GB

Average Performance of 10 Trials (100 elements) Best: 308±21 ns/op

Benchmark                           Score     Error  Units
test3_UsingForEachAndJava8            308  ±     21  ns/op
test10_UsingEclipseMutableMap         309  ±      9  ns/op
test1_UsingWhileAndMapEntry           380  ±     14  ns/op
test6_UsingForAndIterator             387  ±     16  ns/op
test2_UsingForEachAndMapEntry         391  ±     23  ns/op
test7_UsingJava8StreamAPI             510  ±     14  ns/op
test9_UsingApacheIterableMap          524  ±      8  ns/op
test4_UsingKeySetAndForEach           816  ±     26  ns/op
test5_UsingKeySetAndIterator          863  ±     25  ns/op
test8_UsingJava8StreamAPIParallel    5552  ±    185  ns/op

Average Performance of 10 Trials (10000 elements) Best: 37.606±0.790 μs/op

Benchmark                           Score     Error  Units
test10_UsingEclipseMutableMap       37606  ±    790  ns/op
test3_UsingForEachAndJava8          50368  ±    887  ns/op
test6_UsingForAndIterator           50332  ±    507  ns/op
test2_UsingForEachAndMapEntry       51406  ±   1032  ns/op
test1_UsingWhileAndMapEntry         52538  ±   2431  ns/op
test7_UsingJava8StreamAPI           54464  ±    712  ns/op
test4_UsingKeySetAndForEach         79016  ±  25345  ns/op
test5_UsingKeySetAndIterator        91105  ±  10220  ns/op
test8_UsingJava8StreamAPIParallel  112511  ±    365  ns/op
test9_UsingApacheIterableMap       125714  ±   1935  ns/op

Average Performance of 10 Trials (100000 elements) Best: 1184.767±332.968 μs/op

Benchmark                            Score       Error  Units
test1_UsingWhileAndMapEntry       1184.767  ±  332.968  μs/op
test10_UsingEclipseMutableMap     1191.735  ±  304.273  μs/op
test2_UsingForEachAndMapEntry     1205.815  ±  366.043  μs/op
test6_UsingForAndIterator         1206.873  ±  367.272  μs/op
test8_UsingJava8StreamAPIParallel 1485.895  ±  233.143  μs/op
test5_UsingKeySetAndIterator      1540.281  ±  357.497  μs/op
test4_UsingKeySetAndForEach       1593.342  ±  294.417  μs/op
test3_UsingForEachAndJava8        1666.296  ±  126.443  μs/op
test7_UsingJava8StreamAPI         1706.676  ±  436.867  μs/op
test9_UsingApacheIterableMap      3289.866  ± 1445.564  μs/op

A Comparison of Performance Variations Respective to Map Size

x: Size of Map
f(x): Benchmark Score (μs/op)

          100      600     1100     1600     2100
 ---------------------------------------------------
 10  |   0.333    1.631    2.752    5.937    8.024
  3  |   0.309    1.971    4.147    8.147   10.473
  6  |   0.372    2.190    4.470    8.322   10.531
  1  |   0.405    2.237    4.616    8.645   10.707
Tests    2  |   0.376    2.267    4.809    8.403   10.910
f(x)    7  |   0.473    2.448    5.668    9.790   12.125
  9  |   0.565    2.830    5.952    13.22   16.965
  4  |   0.808    5.012    8.813    13.939  17.407
  5  |   0.81     5.104    8.533    14.064  17.422
  8  |   5.173   12.499   17.351    24.671  30.403

Found a mistake? Have a question or improvement idea? Let me know.

Table Of Contents