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<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 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<String, String> 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<K,V> next;        // next entry to return
    Node<K,V> current;     // current entry
    int expectedModCount;  // for fast‑fail
    int index;             // current slot

    HashIterator() {
        expectedModCount = modCount;
        Node<K,V>[] 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<K,V> nextNode() {
        Node<K,V>[] t;
        Node<K,V> 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