迭代键集与迭代条目集

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也有一个可以通过第二个循环避免的常数因子成本.