How HashMap works inside

Key points

• A HashMap is an array of buckets. The key hash picks the bucket; equals picks the entry inside it.
• The raw hashCode is spread first: h ^ (h >>> 16). High bits then influence the bucket.
• Bucket index is hash & (capacity - 1). Capacity is always a power of two so this cheap mask replaces a modulo.
• Default capacity 16, load factor 0.75. At 12 entries the table doubles and everything is rehashed.
• A bucket of 8+ entries treeifies into a red-black tree - but only once capacity reaches 64; below that the table just resizes.
• That is what caps collision damage: a pathological bucket degrades to O(log n) rather than O(n).
• Lookups are O(1) on average. Terrible hash codes make them slow but never wrong.

Example

import java.util.*;

public class Main {

    // Every instance hashes to the same bucket: correct, but slow.
    static final class Clashing {
        final String name;
        Clashing(String name) { this.name = name; }
        @Override public int hashCode() { return 1; }
        @Override public boolean equals(Object o) {
            return o instanceof Clashing c && c.name.equals(name);
        }
    }

    public static void main(String[] args) {
        Map<Clashing, Integer> map = new HashMap<>();
        for (int i = 0; i < 12; i++) map.put(new Clashing("k" + i), i);

        System.out.println("size            : " + map.size() + "  (all in one bucket)");
        System.out.println("get(k7)         : " + map.get(new Clashing("k7")));

        System.out.println();
        System.out.println("how a key finds its bucket in a table of 16:");
        for (String key : List.of("apple", "pear", "fig", "kiwi")) {
            int h = key.hashCode();
            int spread = h ^ (h >>> 16);
            System.out.printf("  %-6s hashCode=%12d  spread=%12d  bucket=%2d%n",
                    key, h, spread, spread & 15);
        }

        System.out.println();
        System.out.println("default capacity 16, load factor 0.75 -> resize after 12 entries");
    }
}

Hash picks the bucket, equals picks the entry. Bad hashes cost speed, never correctness.