Why HashMap.keySet() Traversal Performs Two Passes While entrySet() Traversal Performs One

HashMap is a widely used Java container, and its traversal can be performed via several methods: using an Iterator , using keySet() with an enhanced for‑loop, using entrySet() with an enhanced for‑loop, or using Java 8+ lambda and streams.

The Alibaba Development Manual recommends entrySet (or Map.forEach() in Java 8) because it requires only a single traversal, while keySet incurs two traversals: one to obtain the iterator and another to fetch each value from the map.

Example code using keySet() :

public class Test {
    public static void main(String[] args) {
        Map
map = new HashMap<>();
        map.put("k1", "v1");
        map.put("k2", "v2");
        map.put("k3", "v3");
        for (String key : map.keySet()) {
            String value = map.get(key);
            System.out.println(key + ":" + value);
        }
    }
}

The compiled bytecode shows that the enhanced for‑loop is translated into an iterator obtained via map.keySet().iterator() :

Iterator var2 = map.keySet().iterator();
while (var2.hasNext()) {
    String key = (String) var2.next();
    String value = (String) map.get(key);
    System.out.println(key + ":" + value);
}

The keySet() method returns a Set whose iterator() creates a new KeyIterator object:

public final Iterator
iterator() { return new KeyIterator(); }

KeyIterator extends the abstract HashIterator class and implements Iterator :

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

The constructor of HashIterator contains a do‑while loop that advances to the first non‑null entry in the internal table, which constitutes the first traversal:

HashIterator() {
    expectedModCount = modCount;
    Node
[] t = table;
    current = next = null;
    index = 0;
    if (t != null && size > 0) {
        do {} while (index < t.length && (next = t[index++]) == null);
    }
}

Thus the traversal chain is: keySet() → iterator() → KeyIterator → HashIterator . The initial do‑while loop in HashIterator accounts for the extra pass, whereas entrySet() directly iterates over the entry set without this extra step.

In summary, keySet traversal internally uses an iterator that performs two passes (one to locate the first entry and another to iterate over keys), while entrySet or Map.forEach() traverses the map only once, making them more efficient for most use cases.