Iterating over Key Set vs Iterating over Entry Set

Question

A coworker sent out a tip today that states that the latter snippet of code is more efficient because it does not have to do the lookup in the map on every iteration like the former (#1).

How is #2 (latter) more efficient? I just don't understand how #1 and #2 are different.

**#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

The issue is that map.get usually has a significant constant-factor cost, whereas iterating over map.entrySet() is usually just as cheap as iterating over map.keySet().

This is most significant for things like TreeMap, where the first loop would actually be O(n log n) and the second loop would be O(n), but even for HashMap, get has a constant-factor cost that could be avoided with the second loop.

Answer 2

Snippet #2 can be faster as the inner part of the loop is basically two calls for getting properties.

In snippet #1, at each iteration step you call map.get which is a worst-case O(n) operation if you have bad hash codes for key. Even with a good hash code, there is a constant cost associated with finding the right bucket and retrieving the value.

Note that the iteration in case of HashMaps for both versions is the same, as they both use a 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(); }
}