Why Does HashMap.keySet() Iterate Twice? Uncovering Java’s Internal Iterator Mechanics

1. Introduction

HashMap is a core container in Java. Common traversal methods are using an Iterator, using keySet() with an enhanced for‑loop, using entrySet() with an enhanced for‑loop, and Java 8+ stream APIs. The Alibaba Development Manual recommends entrySet() and Map.forEach() because they require fewer traversal steps.

2. Why keySet() Traverses Twice

When iterating with for (K key : map.keySet()) { V value = map.get(key); } the JVM performs two passes: first it obtains an iterator over the key set, then for each key it calls map.get(key) to fetch the value. This results in a “double traversal”.

Compiled form

Iterator<K> it = map.keySet().iterator();
while (it.hasNext()) {
    K key = it.next();
    V value = map.get(key);
    // …
}

3. keySet() → iterator()

The keySet() method returns an inner class KeySet that implements Set<K>. Its iterator() method creates a new KeyIterator instance.

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

4. KeyIterator

KeyIterator

is a final class extending HashIterator and implements Iterator<K>. Its next() simply returns the key of the next node.

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

5. HashIterator Mechanics

HashIterator

is an abstract class that provides the core iteration logic for HashMap. Important fields: Node<K,V> next – next entry to return Node<K,V> current – last returned entry int expectedModCount – fail‑fast check int index – current bucket index

Its constructor advances to the first non‑null bucket using a do‑while loop:

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

hasNext()

checks next != null. nextNode() returns the current entry, moves current forward, and repeats the bucket scan when the chain ends.

public final boolean hasNext() { return next != null; }

final Node<K,V> nextNode() {
    Node<K,V> e = next;
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    if (e == null)
        throw new NoSuchElementException();
    if ((next = (current = e).next) == null && (table = t) != null) {
        do {} while (index < t.length && (next = t[index++]) == null);
    }
    return e;
}

6. Summary of the Call Chain

map.keySet()

returns a KeySet view. KeySet.iterator() creates a KeyIterator. KeyIterator inherits traversal logic from HashIterator.

The HashIterator constructor performs the initial scan for the first entry, which explains the apparent “first traversal”.

keySet → iterator() → KeyIterator → HashIterator