Java Language Maps Iterating Map Entries Efficiently
Example
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.
Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Integer, Integer> pair = it.next();
sum += pair.getKey() + pair.getValue();
}
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.keySetwithfor
for (Integer key : map.keySet()) {
sum += key + map.get(key);
}
- Implementation using
Map.keySetwithIterator
Iterator<Integer> it = map.keySet().iterator();
while (it.hasNext()) {
Integer key = it.next();
sum += key + map.get(key);
}
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.forEachwithStream.parallel(Java 8+)
map.entrySet()
.stream()
.parallel()
.forEach(e -> sum += e.getKey() + e.getValue());
- Implementation using
IterableMapfrom Apache Collections
MapIterator<Integer, Integer> mit = iterableMap.mapIterator();
while (mit.hasNext()) {
sum += mit.next() + it.getValue();
}
- Implementation using
MutableMapfrom 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
