Inside HashMap, and why iterators fail fast

"How does a HashMap work?" is one of the most common Java interview questions. The description below is OpenJDK's implementation — the HashMap contract promises the behaviour, not these numbers, but this is the answer interviewers expect.

Buckets

A HashMap is an array of bins (buckets). To place a key it:

1. calls key.hashCode() and spreads it: h ^ (h >>> 16), mixing the high 16 bits into the low ones;
2. picks the bin (capacity - 1) & spread. Capacity is always a power of two, so this keeps the low bits — which is why the spreading step exists: without it, hash codes that differ only in their high bits would all collide;
3. walks the bin, comparing the stored hash first and calling equals only when the hashes match. A bin is a linked list. When one bin would hold more than 8 entries, it is converted to a red-black tree if the table already has at least 64 bins; a smaller table is resized instead. A tree bin finds a key in O(log n) when the keys differ in hash code or implement Comparable; keys with identical hashes and no ordering can still need a scan of the bin.

The default capacity is 16 and the load factor 0.75, so the threshold is 12. When an insertion takes the size above the threshold, the table doubles and every entry is redistributed — which is also why iteration order can change after a few more puts.

A terrible hashCode therefore never breaks a map; it only makes it slow:

1import java.util.*;2 3public class Solution {4    record SameHash(int id) {5        @Override public int hashCode() { return 42; }   // legal, and awful6    }7 8    public static String describe() {9        Map<SameHash, String> map = new HashMap<>();10        for (int i = 0; i < 2000; i++) map.put(new SameHash(i), "v" + i);11        map.put(new SameHash(7), "replaced");12        return "size=" + map.size()13            + " get(1234)=" + map.get(new SameHash(1234))14            + " get(7)=" + map.get(new SameHash(7))15            + " get(5000)=" + map.get(new SameHash(5000));16    }17}

Fail-fast iterators

Every structural change — adding or removing an element, but not set on a list position or a put that only replaces an existing key's value — increments the collection's modCount. An iterator records that count when it is created and checks it on each next(); if the collection was changed by anyone other than the iterator itself, it throws ConcurrentModificationException. Despite the name, this needs no second thread: removing from a list inside a for-each over it is enough.

1import java.util.*;2 3public class Solution {4    public static List<String> describe() {5        List<String> out = new ArrayList<>();6 7        List<String> four = new ArrayList<>(List.of("a", "b", "c", "d"));8        try {9            for (String s : four) {10                if (s.equals("b")) four.remove(s);11            }12            out.add("no exception");13        } catch (ConcurrentModificationException e) {14            out.add("remove b from [a, b, c, d]: ConcurrentModificationException");15        }16 17        List<String> three = new ArrayList<>(List.of("a", "b", "c"));18        List<String> visited = new ArrayList<>();19        for (String s : three) {20            visited.add(s);21            if (s.equals("b")) three.remove(s);   // next-to-last element22        }23        out.add("remove b from [a, b, c]: no exception, visited=" + visited + " left=" + three);24 25        List<String> safe = new ArrayList<>(List.of("a", "b", "c", "d"));26        safe.removeIf(s -> s.equals("b") || s.equals("c"));27        out.add("removeIf: " + safe);28        return out;29    }30}

Fail-fast is best effort. In the second case above, removing the next-to-last element makes hasNext() return false before next() ever checks the count, so the loop simply stops early and skips an element without any exception. Never rely on the exception to detect a bug. The safe ways to remove while iterating are Iterator.remove(), removeIf, or collecting what to remove and removing it afterwards.

For concurrent access, ConcurrentHashMap never throws this exception: its iterators are weakly consistent — they may or may not reflect changes made after they were created. It also rejects null keys and values, because get returning null must unambiguously mean "absent".

Common mistakes

• list.remove(x) inside for (T x : list) — a ConcurrentModificationException, or, worse, a silently skipped element.
• Treating HashMap iteration order as stable. It depends on the hash codes, the capacity and the insertion history, and a resize reshuffles it.
• Sizing a map that will hold a known 1,000 entries with new HashMap<>(1000): the argument is a capacity, not an entry count, so it still resizes once. Java 19 added HashMap.newHashMap(1000), which sizes for that many entries.