有效地迭代地图条目

本节提供了十个独特示例实现的代码和基准,这些实现迭代 Map<Integer, Integer> 的条目并生成 Integer 值的总和。所有这些示例都具有Θ(n) 的算法复杂性,但是,基准测试仍然有助于深入了解哪些实现在真实世界环境中更有效。

  1. 使用 IteratorMap.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. 使用 forMap.Entry 实现
    for (Map.Entry<Integer, Integer> pair : map.entrySet()) {
        sum += pair.getKey() + pair.getValue();
    }
  1. 使用 Map.forEach (Java 8+)实现
    map.forEach((k, v) -> sum[0] += k + v);
  1. 使用 Map.keySetfor 实现
    for (Integer key : map.keySet()) {
        sum += key + map.get(key);
    }
  1. 使用 Map.keySetIterator 实现
    Iterator<Integer> it = map.keySet().iterator();
    while (it.hasNext()) {
        Integer key = it.next();
        sum += key + map.get(key);
    }
  1. 使用 forIteratorMap.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. 使用 Stream.forEach (Java 8+)实现
    map.entrySet().stream().forEach(e -> sum += e.getKey() + e.getValue());
  1. 使用 Stream.forEachStream.parallel (Java 8+)实现
    map.entrySet()
       .stream()
       .parallel()
       .forEach(e -> sum += e.getKey() + e.getValue());
  1. 使用实施 IterableMapApache 的集合
    MapIterator<Integer, Integer> mit = iterableMap.mapIterator();
    while (mit.hasNext()) {
        sum += mit.next() + it.getValue();
    }
  1. 使用实施 MutableMapEclipse 的收藏
     mutableMap.forEachKeyValue((key, value) -> {
         sum += key + value;
     });

性能测试Github 上 提供的代码
测试环境:Windows 8.1 64 位,Intel i7-4790 3.60GHz,16 GB

  1. 10 次​​试验的平均性能(100 种元素)最佳: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
    
  2. 10 次​​试验的平均性能(10000 种元素)最佳: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
    
  3. 10 次​​试验的平均性能(100000 个元素)最佳: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
    
  4. 与地图大小相关的性能变化比较

StackOverflow 文档

       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