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

给定下面的代码，用两种替代方法遍历它，
这两种方法有什么不同吗？

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 alt. #2是遍历整个map的更有效的手段（但我可能是错的）

Answer 1

你的第二个选项肯定是更高效的，因为在第一个选项中，你只进行一次查找而不是n次。

但是，没有什么比在可能的情况下试用更好的了。 所以这里呢 –

（不完美，但足以validation假设，并在我的机器无论如何）

 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; int mapSize = 5000; int strLength = 5;
Alt＃1花了26毫秒
Alt＃2花了20毫秒

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

用int mapSize = 50000; int strLength = 50; int mapSize = 50000; int strLength = 50;
Alt＃1花了22毫秒
Alt＃2花了21毫秒

用int mapSize = 50000; int strLength = 500; int mapSize = 50000; int strLength = 500;
Alt＃1花了28毫秒
Alt＃2花了23毫秒

用int mapSize = 500000; int strLength = 5; int mapSize = 500000; int strLength = 5;
Alt＃1花了92毫秒
Alt＃2花了57毫秒

…等等

Answer 2

第二个片段会稍快，因为它不需要重新查找键。

所有的HashMap迭代器都调用nextEntry方法 ，它返回一个Entry<K,V> 。

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

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

（ keySet()和entrySet()都是便宜的调用）

Answer 3

后者比前者更有效率。 像FindBugs这样的工具实际上会标记前者，并build议你去做后者。

Answer 4

地图：

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

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

1） keySet（） – 使用它，如果你只需要使用键

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

2） entrySet（） – 使用它，如果你需要两个： 键和值

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

3） values（） – 使用它，如果你只需要的值

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

Answer 5

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

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

另一个注意事项：如果你的地图的容量比实际大小大得多，并且你使用迭代很多，你可以考虑使用LinkedHashMap。 它为一个完整的迭代（以及一个可预测的迭代顺序）提供O(size)而不是O(size+capacity)复杂度。 （如果真的有所改进，你还是应该进行测量，因为这些因素可能会有所不同，LinkedHashMap在创build地图时有更大的开销。）

Answer 6

bguiz，

我认为（我不知道）迭代EntrySet（替代scheme2）的效率稍微高一点，因为它不会散列每个键以获得它的值。说了算，散列是一个O （1）每个条目的操作，因此我们只是在整个HashMap谈论O（n）…但是请注意，所有这些仅适用于HashMap … Map其他实现可能具有非常不同的性能特征。

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

如果你没有一个真正的，报告的性能问题，那么你真的不用担心…在这里几个时钟滴答，不会影响你的程序的整体可用性。

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

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