對鍵集進行迭代和對條目集的迭代

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(); } 
}