Java：通过HashMap迭代，效率更高？

Question

给出以下代码，用两种替代方法遍历它，
这两种方法之间是否存在任何性能差异？

 Map<String, Integer> map = new HashMap<String, Integer>(); 
     //populate map 

     //alt. #1 
     for (String key : map.keySet()) 
     { 
      Integer value = map.get(key); 
      //use key and value 
     } 

     //alt. #2 
     for (Map.Entry<String, Integer> entry : map.entrySet()) 
     { 
      String key = entry.getKey(); 
      Integer value = entry.getValue(); 
      //use key and value 
     } 

我倾向于认为alt. #2是通过整个map迭代的更有效的手段（但我可能是错的）

Answer 1

您的第二个选项肯定更有效率，因为您只在第一个选项中进行了一次查找，而第n次只进行一次查找。

但是，没有什么比坚持下去更好的了。所以这里去 -

（不完美的，但不够好，以验证假设，反正我的机器上）

public static void main(String args[]) { 

    Map<String, Integer> map = new HashMap<String, Integer>(); 
    // populate map 

    int mapSize = 500000; 
    int strLength = 5; 
    for(int i=0;i<mapSize;i++) 
     map.put(RandomStringUtils.random(strLength), RandomUtils.nextInt()); 

    long start = System.currentTimeMillis(); 
    // alt. #1 
    for (String key : map.keySet()) { 
     Integer value = map.get(key); 
     // use key and value 
    } 
    System.out.println("Alt #1 took "+(System.currentTimeMillis()-start)+" ms"); 

    start = System.currentTimeMillis(); 
    // alt. #2 
    for (Map.Entry<String, Integer> entry : map.entrySet()) { 
     String key = entry.getKey(); 
     Integer value = entry.getValue(); 
     // use key and value 
    } 
    System.out.println("Alt #2 took "+(System.currentTimeMillis()-start)+" ms"); 
} 

成绩（一些有趣的）

随着int mapSize = 5000; int strLength = 5;
Alt键＃1把26 ms
Alt＃2花了20 ms

With int mapSize = 50000; int strLength = 5;
Alt键＃1把32毫秒
Alt键＃2用了20毫秒

随着int mapSize = 50000; int strLength = 50;
Alt键＃1把22毫秒
Alt键＃2把21毫秒

随着int mapSize = 50000; int strLength = 500;
Alt键＃1把28 MS
Alt键＃2花了23毫秒

随着int mapSize = 500000; int strLength = 5;
Alt键＃1把92毫秒
Alt键＃2把57毫秒

...等等

Answer 2

第二个片段将更快稍微，因为它不需要重新查找密钥。

全部HashMap迭代器调用nextEntry method，返回Entry<K,V>。

您的第一个片段丢弃了条目中的值（在KeyIterator中），然后在字典中再次查找。

你的第二个片段使用键和值直接（从EntryIterator）

（无论keySet()和entrySet()是便宜的电话）

Answer 3

后者比前者更有效。像FindBugs这样的工具实际上会标记前者并建议您执行后者。

Answer 4

bguiz，

我认为（我不知道）的迭代的entrySet（替代2）是稍微更有效，只是因为它不为了得到它的哈希值，每个键...话虽如此，计算散列是每个条目的O（1）操作，因此我们只在整个HashMap上说O（n）......但是请注意，所有这些仅适用于HashMap ...其他实现Map可能具有非常不同的性能特征。

我确实认为你会“推动”实际上注意到性能的差异。如果你担心，那么为什么不设置一个测试用例来计算两种迭代技术？

如果您没有真实的报告的性能问题，那么您真的不用担心很多......在这里几个时钟刻度不会影响程序的整体可用性。

我相信代码的许多其他方面通常比直接执行更重要。当然，有些模块是“性能至关重要的”，而且在编写它之前就已经知道了，单独的性能测试......但这种情况相当罕见。作为一种常规方法，最好集中精力编写完整，正确，灵活，可测试，可重用，可读，可维护的代码......性能可以在以后根据需要进行构建。

版本0应尽可能简单，没有任何“优化”。

Answer 5

一般来说，第二个是有点快了一个HashMap。它只会真的很重要，如果你有很多的哈希碰撞，因为那么get(key)调用得到比O(1)慢 - 它得到O(k)与k是在同一个桶中的条目数（即具有相同哈希码或不同的键的数量散列码仍然映射到同一个桶 - 这取决于地图的容量，大小和加载因子）。

Entry-iterating变体不需要查找，因此它在这里变得更快一些。

另一个注意事项：如果你的地图的容量比实际大小大得多，并且你使用了很多迭代，你可以考虑使用LinkedHashMap。它提供O(size)而不是O(size+capacity)完整迭代的复杂性（以及可预测的迭代次序）。 （您仍应衡量，如果这真的给人一种进步，因为因素可能会有所不同的LinkedHashMap对创建地图更大的开销。）

Answer 6

地图：

Map<String, Integer> map = new HashMap<String, Integer>();

除了2个选项，有还有一个。

1）键设置（） - 使用它，如果你需要使用仅的键

for (String k : map.keySet()) { 
    ... 
} 

2）的entrySet（） - 如果你需要同时使用它：键&值

for (Map.Entry<String, Integer> entry : map.entrySet()) { 
    String k = entry.getKey(); 
    Integer v = entry.getValue(); 
    ... 
} 

3）个值（） - 如果你只需要的值

for (Integer v : map.values()) { 
    ... 
}