对键集进行迭代和对条目集的迭代

Question

一位同事今天发出了一条提示，指出后面的代码片断效率更高，因为它不必在每次迭代（如前者）中执行映射查找（＃ 1）。

＃2（后者）的效率如何？我只是不明白＃1和＃2是如何不同的。

**#1 snippet**：

for (String key : map.keySet()) 
{ 
    String value = map.get(key); // does lookup for every key 
    // do something with value 
} 

**#2 snippet**：

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

Answer 1

的问题是，map.get通常有显著恒定要素成本，而迭代map.entrySet()通常只是作为迭代过map.keySet()便宜。

这是对于像TreeMap，其中第一个循环实际上是为O（n log n）的和第二循环将是为O（n），但即使HashMap，get最显著具有恒定的因素成本是可以用第二个循环来避免。

Answer 2

代码＃2可以更快，因为循环的内部部分基本上是两次获取属性的调用。

在代码段＃1中，如果您的key的散列代码不正确，则在每次迭代步骤中，都会调用map.get，这是最糟糕的情况O(n)操作。即使有一个好的散列码，与寻找合适的存储桶和检索value相关的成本也是不变的。

注意，在HashMaps这样的情况下，迭代两个版本是一样的，因为它们都使用HashIterator：

final class KeyIterator extends HashIterator 
    implements Iterator<K> { 
    public final K next() { return nextNode().key; } 
} 

final class EntryIterator extends HashIterator 
    implements Iterator<Map.Entry<K,V>> { 
    public final Map.Entry<K,V> next() { return nextNode(); } 
}