Why HashMap.keySet() Traversal Involves Two Passes and How entrySet()/Map.forEach() Is More Efficient

Part 1 Introduction

HashMap is a widely used container in Java, and its traversal methods are frequently discussed. The 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 recommends using entrySet for traversal and, in Java 8, Map.forEach() , citing differences in the number of traversal passes.

keySet traversal requires two passes.

entrySet traversal requires only one pass.

keySet traverses twice: once to convert to an Iterator object, and a second time to retrieve the value for each key.

Part 2 keySet Traversal Explained

We start with a simple example that uses keySet() to iterate a map:

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 is straightforward:

k1:v1
k2:v2
k3:v3

The enhanced for‑loop is syntactic sugar; the compiler actually translates it to an iterator obtained via map.keySet().iterator() . Decompiling the class shows the hidden 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 iterator() method of the KeySet class returns a KeyIterator object, which extends HashIterator . The actual traversal logic resides in HashIterator :

abstract class HashIterator {
    Node
next;        // next entry to return
    Node
current;     // current entry
    int expectedModCount;  // for fast‑fail
    int index;             // current slot

    HashIterator() {
        expectedModCount = modCount;
        Node
[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { // advance to first entry
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }

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

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

    public final void remove() { /* omitted for brevity */ }
}

The constructor contains a do‑while loop that advances to the first non‑null entry, which is the hidden traversal step that keySet performs before the explicit loop in user code.

1 iterator()

Defined in the Set interface, it returns an iterator over the set’s elements.

2 HashMap.KeySet#iterator()

The KeySet class implements this method by returning a new KeyIterator instance.

3 HashMap.KeyIterator

Extends HashIterator and implements Iterator<K> , providing a next() method that returns nextNode().key .

4 HashMap.HashIterator

Implements the core iteration logic, including the initial do‑while that finds the first occupied bucket.

Part 3 Summary

Iterating with keySet() internally uses the iterator() method.

The iterator() method creates a KeyIterator object.

KeyIterator extends HashIterator , inheriting its traversal mechanics.

The HashIterator constructor performs a hidden pass to locate the first non‑null entry, accounting for the extra traversal observed with keySet() .

keySet → iterator() → KeyIterator → HashIterator