Understanding Why HashMap.keySet() Traverses Twice and How entrySet() Provides a More Efficient Iteration

HashMap is a widely used Java container, and its traversal methods include using an Iterator, keySet() with an enhanced for‑loop, entrySet() with an enhanced for‑loop, and Java 8+ lambda/stream APIs.

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

Why does keySet traverse twice? The first pass creates an Iterator from the key set, and the second pass retrieves each value from the map using the keys.

Example code using keySet():

public class Test {
    public static void main(String[] args) {
        Map<String, String> 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 class shows that the enhanced for‑loop is transformed into an iterator:

public class Test {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap();
        map.put("k1", "v1");
        map.put("k2", "v2");
        map.put("k3", "v3");
        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 KeySet object whose iterator() creates a KeyIterator instance:

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

KeyIterator

extends HashIterator and implements Iterator, providing a next() method that returns nextNode().key.

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

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

Thus, using keySet() implicitly performs two traversals: one to obtain the iterator and another to fetch each value, whereas entrySet() (or Map.forEach()) accesses entries directly in a single pass.

Summary points:

Iterating with keySet() internally calls iterator(). iterator() creates a KeyIterator object. KeyIterator extends HashIterator, whose constructor loops to locate the first non‑empty entry.

This double‑pass behavior explains why entrySet() is recommended for efficient HashMap traversal.