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

1. 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();
}```
1. Implementation using `for` with `Map.Entry`
```for (Map.Entry<Integer, Integer> pair : map.entrySet()) {
sum += pair.getKey() + pair.getValue();
}```
1. Implementation using `Map.forEach` (Java 8+)

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

1. Implementation using `Map.keySet` with `for`
```for (Integer key : map.keySet()) {
sum += key + map.get(key);
}```
1. Implementation using `Map.keySet` with `Iterator`
```Iterator<Integer> it = map.keySet().iterator();
while (it.hasNext()) {
Integer key = it.next();
sum += key + map.get(key);
}```
1. 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();
}```
1. Implementation using `Stream.forEach` (Java 8+)

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

1. Implementation using `Stream.forEach` with `Stream.parallel` (Java 8+)
```map.entrySet()
.stream()
.parallel()
.forEach(e -> sum += e.getKey() + e.getValue());```
1. Implementation using `IterableMap` from Apache Collections
```MapIterator<Integer, Integer> mit = iterableMap.mapIterator();
while (mit.hasNext()) {
sum += mit.next() + it.getValue();
}```
1. 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

1. 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```
1. 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```
1. 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```
1. 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```