java - 遍历键集与遍历条目集

Question

一位同事今天发出了一条提示，指出后一段代码更高效，因为它不必像前一段 (#1) 那样在每次迭代时都在 map 中进行查找。

#2(后者)如何更有效率？我只是不明白 #1 和 #2 有何不同。

**#1 片段**:

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

**#2 片段**:

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 具有常数因子成本，可以通过第二个循环避免。