Why HashMap.keySet() Traversal Performs Two Iterations and How entrySet() Is More Efficient

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 entrySet for traversal and, in Java 8, Map.forEach(), because they require fewer iteration steps.

Key point: keySet traversal needs two passes—one to obtain the iterator and another to retrieve each value—whereas entrySet traversal needs only a single pass.

When using keySet , the first pass converts the set into an Iterator , and the second pass iterates over the keys to fetch values from the map.

Part 2 – Why keySet Traverses Twice

Consider the following code that iterates a map with keySet():

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, but the underlying bytecode shows that the compiler translates the enhanced for‑loop into an explicit iterator:

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 call to map.keySet().iterator() creates a KeyIterator object, which extends HashIterator. To understand where the actual traversal occurs, we inspect the relevant source code.

1. iterator() in Set

The iterator() method of the Set interface returns an iterator over the set's elements.

2. HashMap.KeySet#iterator()

In HashMap, the KeySet class implements iterator() as follows:

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

3. HashMap.KeyIterator

KeyIterator

extends HashIterator and implements Iterator<K>:

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

4. HashMap.HashIterator

The abstract HashIterator class contains the core traversal logic. Its constructor advances to the first non‑null entry using a do‑while loop:

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

The nextNode() method then moves the iterator forward, returning each entry in turn.

Part 3 – Summary

Using keySet() internally creates an iterator() object.

The iterator() method returns a KeyIterator instance. KeyIterator extends HashIterator, which performs the actual traversal.

The constructor of HashIterator locates the first non‑empty entry via a do‑while loop.

keySet → iterator() → KeyIterator → HashIterator

Therefore, keySet traversal involves two passes (iterator creation and value lookup), while entrySet or Map.forEach() can achieve the same result with a single pass.