Understanding Why HashMap.keySet() Traversal Involves Two Iterations and Its Internal Mechanism

HashMap is a widely used Java container, and its traversal methods are numerous. The article lists four common ways: 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 recommends entrySet for traversal and, in Java 8, Map.forEach() , citing differences in traversal counts. Specifically, keySet traversal requires two passes (once to obtain an Iterator and once to retrieve values), whereas entrySet traversal needs only one.

KeySet traversal involves two iterations: one to convert to an Iterator object and another to fetch values from the HashMap.

To illustrate, a sample code using keySet() is provided:

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 output shows the expected key‑value pairs. The underlying reason for the double iteration is that the enhanced for-loop on keySet() is compiled to use an Iterator obtained via map.keySet().iterator() . Decompiling the compiled class reveals the iterator usage:

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");
        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 KeyIterator object. KeyIterator extends HashIterator , which contains the actual traversal logic. The constructor of HashIterator uses a do‑while loop to locate the first non‑null entry in the internal table:

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 , where HashIterator performs the actual iteration over the HashMap entries.

The article also briefly touches on inheritance concepts using simple Father and Son classes to illustrate constructor chaining, reinforcing the idea that creating a Son instance triggers the Father constructor.

Summary

1. Traversing with keySet() internally uses the iterator() method.

2. The iterator() method creates a KeyIterator object.

3. KeyIterator extends HashIterator .

4. The HashIterator constructor iterates to find the first non‑null entry, completing the traversal process.

keySet → iterator() → KeyIterator → HashIterator