Understanding Why HashMap.keySet() Traverses Twice in Java

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

The Alibaba Development Manual recommends entrySet for iteration and, in Java 8, Map.forEach() , because the number of traversal passes differs: keySet requires two passes while entrySet needs only one.

To investigate the claim that keySet traverses twice, a simple program is shown that iterates over a map with for (String key : map.keySet()) . The compiled bytecode (viewed via decompilation) reveals that the enhanced for‑loop is translated to map.keySet().iterator() , creating an Iterator object.

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 decompiled version shows the explicit creation of Iterator var2 = map.keySet().iterator(); followed by a while (var2.hasNext()) loop, confirming the first traversal to obtain the iterator.

Further inspection of the KeySet class reveals that its iterator() method returns a new KeyIterator instance, which extends HashIterator . The KeyIterator simply overrides next() to return nextNode().key .

The abstract HashIterator constructor contains a do‑while loop that advances to the first non‑null entry in the internal table, effectively performing the second traversal to locate the first element.

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

In summary:

Using keySet() internally invokes iterator() .

The iterator() method creates a KeyIterator object.

KeyIterator extends HashIterator , whose constructor performs a loop to find the first non‑empty entry.

This explains why keySet appears to traverse twice.

keySet → iterator() → KeyIterator → HashIterator