Understanding HashMap keySet Traversal and Iterator Mechanism in Java

HashMap is a widely used container in Java, and its traversal can be performed via several methods such as Iterator, keySet(), entrySet(), and Java 8 streams.

The article points out that the Alibaba Development Manual recommends using entrySet() for traversal and, in Java 8, Map.forEach(), because keySet() requires two passes while entrySet() needs only one.

A simple example program demonstrates keySet() traversal, showing the output of key-value pairs and raising the question of why an additional iterator pass occurs.

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

By decompiling the compiled class, the for‑each loop is revealed to be transformed into an explicit iterator obtained via map.keySet().iterator() , followed by a while loop that calls next() and map.get(key) .

public class Test {
    public 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 internal implementation of HashMap.keySet() returns a KeySet object whose iterator() method creates a new KeyIterator , which extends HashIterator .

final class KeySet extends AbstractSet
{
    public final int size() { return size; }
    public final void clear() { HashMap.this.clear(); }
    public final Iterator
iterator() { return new KeyIterator(); }
    public final boolean contains(Object o) { return containsKey(o); }
    public final boolean remove(Object key) { return removeNode(hash(key), key, null, false, true) != null; }
    public final Spliterator
spliterator() { return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0); }
    public final void forEach(Consumer
action) { /* ... */ }
}

The KeyIterator class simply overrides next() to return nextNode().key .

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

The abstract HashIterator constructor contains a do‑while loop that advances to the first non‑null entry in the hash table, which accounts for the first traversal pass.

abstract class HashIterator {
    Node
next;
    Node
current;
    int expectedModCount;
    int index;
    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);
        }
    }
    public final boolean hasNext() { return next != null; }
    final Node
nextNode() { /* ... */ }
    public final void remove() { /* ... */ }
}

Additional examples of inheritance (Father/Son classes) illustrate how constructors are invoked in a hierarchy, reinforcing the concept of iterator creation.

public class Father {
    public Father() {
        System.out.println("father");
    }
}

public class Son extends Father {
    public static void main(String[] args) {
        Son son = new Son();
    }
}

In summary, keySet() traversal internally uses an iterator, the iterator is a KeyIterator that extends HashIterator , and the HashIterator constructor performs the initial scan to locate the first entry, explaining the two‑step traversal.