HashMap Internals

Direct Answer

HashMap stores entries in a table of buckets. It mixes the key's hashCode() to choose a bucket, then uses equals() to find the key in that bucket. Collisions start as a linked bin. In current JDKs, a busy bin may become a red-black tree only after the treeify threshold is reached and the table is at least 64 buckets; otherwise the map resizes. When the resize threshold is crossed, the table normally grows and entries are redistributed.

Code Example

The snippet below walks the same path the JVM does — a put that hashes to a bucket, an overwrite when the key equals() an existing one, and a resize once the table fills past its threshold.

import java.util.*;

public class HashMapInternals {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();  // cap 16, lf 0.75
        map.put("apple", 1);   // hash("apple") -> index -> bucket
        map.put("apple", 2);   // same key (equals) -> overwrite to 2
        map.put("grape", 9);   // different bucket (or collision -> chain)

        // get uses the stored mixed hash to select a bin, then equals() pinpoints the key:
        int v = map.get("apple");  // 2

        // After ~12 entries (16 * 0.75) the table resizes to 32.
        for (int i = 0; i < 20; i++) map.put("k" + i, i);
    }
}

Nothing here is special syntax — it is plain Java 17. The machinery (hashing, chaining, resizing) all runs inside put and get, invisible to the caller.

Common Mistakes & Pitfalls

• Forgetting equals(): hash selection narrows the search; equality identifies the logical key.
• Treating internal constants as an API guarantee: current JDKs use treeification thresholds and a minimum table size, but Map does not promise this representation.
• Saying resize re-calls every hashCode(): current implementations redistribute entries using stored hash information.
• Using mutable key state: changing fields used by equals or hashCode after insertion can make lookup fail.
• Assuming expected O(1) means guaranteed O(1): collisions and resizing affect individual operations.