Understanding Why HashMap keySet Traversal Performs Two Iterations and How entrySet Improves Efficiency

HashMap is a widely used container in Java, and its traversal methods are frequently discussed. Common ways to iterate a HashMap include using an Iterator, using keySet() with an enhanced for‑loop, using entrySet() with an enhanced for‑loop, and using Java 8+ lambda expressions and streams.

The Alibaba Development Manual notes that entrySet traversal is preferred because it iterates only once, whereas keySet traversal requires two passes: one to obtain an iterator and another to fetch each value from the map.

To illustrate the keySet approach, the article provides a simple Java program:

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 output shows each key‑value pair, but the article points out that the keySet traversal internally performs an extra iteration to create an Iterator object, which is not obvious from the source code.

Decompiling the compiled class reveals that the enhanced for‑loop is translated into:

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 iterator() method of the KeySet class returns a new KeyIterator, which extends the abstract HashIterator. The article examines the source of these classes:

final class KeySet extends AbstractSet<K> {
    public final Iterator<K> iterator() { return new KeyIterator(); }
    // other methods omitted
}

and the KeyIterator implementation:

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

The abstract HashIterator contains the core iteration logic, including a constructor that uses a do‑while loop to locate the first non‑null entry in the hash table:

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

This constructor performs the first traversal to find the initial entry, which explains the “two iterations” observed when using keySet(). In contrast, entrySet() directly provides an iterator over map entries, requiring only a single traversal.

Finally, the article summarizes the findings:

Using keySet internally invokes iterator().

The iterator() method creates a KeyIterator object. KeyIterator extends HashIterator.

The HashIterator constructor iterates to locate the first non‑empty entry.

Thus, the perceived double iteration of keySet stems from the iterator creation step, while entrySet and Map.forEach() offer a more efficient single‑pass traversal.