Collections

66. HashMap Internals

HashMap stores entries in an array of buckets; collision entries are stored in a linked list that treeifies to a red-black tree at 8+ entries (Java 8+); a good hashCode distribution minimises collisions.

Java 21 (core language)

Explanation

HashMap internally has an Entry<K,V>[] array (the "table"). For put(key, value): compute hash(key), find index = hash & (capacity - 1), and place the entry in table[index]. Collisions (multiple keys at the same index) form a linked list at that bucket. Since Java 8, if a bucket's linked list grows to 8+ entries and the table has at least 64 slots, the list is treeified into a red-black tree — turning O(n) worst-case lookups back to O(log n).

Resizing: when the number of entries exceeds capacity * loadFactor (default 0.75), the table doubles and all entries are rehashed. Resizing is expensive — pre-size with new HashMap<>(expectedSize / 0.75 + 1) if you know the count.

hashCode matters: if all keys hash to the same bucket, HashMap degrades to O(n) (or O(log n) with treeification). Classes used as keys must have well-distributed hashCode implementations. Mutable keys are dangerous — if the key's hash changes after it's in the map, you'll never find the entry again.

Example

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class HashMapInternals {
    // Object with intentionally bad hashCode: all keys collide
    static class BadKey {
        final int id;
        BadKey(int id) { this.id = id; }
        @Override public int hashCode() { return 1; } // all same bucket!
        @Override public boolean equals(Object o) {
            return o instanceof BadKey b && id == b.id;
        }
        @Override public String toString() { return "K" + id; }
    }

    // Well-distributed hashCode
    static class GoodKey {
        final int id;
        GoodKey(int id) { this.id = id; }
        @Override public int hashCode() { return Objects.hash(id); }
        @Override public boolean equals(Object o) {
            return o instanceof GoodKey g && id == g.id;
        }
    }

    public static void main(String[] args) {
        // Demonstrate performance impact of hash distribution
        int N = 1000;
        Map<BadKey,  Integer> bad  = new HashMap<>(N * 2);
        Map<GoodKey, Integer> good = new HashMap<>(N * 2);

        for (int i = 0; i < N; i++) {
            bad.put(new BadKey(i), i);
            good.put(new GoodKey(i), i);
        }

        long t1 = System.nanoTime();
        for (int i = 0; i < N; i++) bad.get(new BadKey(i));
        long t2 = System.nanoTime();
        for (int i = 0; i < N; i++) good.get(new GoodKey(i));
        long t3 = System.nanoTime();

        System.out.printf("Bad hashCode  lookup: %,d ns%n", t2 - t1);
        System.out.printf("Good hashCode lookup: %,d ns%n", t3 - t2);
        System.out.println("(Bad is much slower due to all keys in one bucket)");

        // Mutable key trap
        var mutableKey = new java.awt.Point(1, 2); // hashCode depends on x,y
        Map<java.awt.Point, String> trap = new HashMap<>();
        trap.put(mutableKey, "value");
        System.out.println("Before: " + trap.get(mutableKey)); // "value"
        mutableKey.x = 99; // mutate the key — changes its hash!
        System.out.println("After:  " + trap.get(mutableKey)); // null (wrong bucket now)
    }
}

Sources