HashMap Internals

HashMap is an array of buckets; each bucket holds the entries whose keys map to that array index. This lesson follows a key from hashCode to its bucket, shows what happens on collisions and on resize, and then covers the maps built on the same design. It relies on the equals and hashCode contract from Object Contracts. Every constant below is quoted from java/util/HashMap.java in the JDK 25 src.zip.

Constant or rule	Value in JDK 25
`DEFAULT_INITIAL_CAPACITY`	16 (table allocated on first put)
`DEFAULT_LOAD_FACTOR`	0.75
`hash(key)`	`h ^ (h >>> 16)`, and 0 for a `null` key
Bucket index	`(n - 1) & hash`, `n` a power of two
`TREEIFY_THRESHOLD`	8
`UNTREEIFY_THRESHOLD`	6
`MIN_TREEIFY_CAPACITY`	64
`MAXIMUM_CAPACITY`	2^30

Examples 3, 4, and 5 read the private table field by reflection, which needs --add-opens (see Packages, Modules, and Reflection).

Example 1: hash spreading and the bucket index

HashMap.hash XORs the high 16 bits of hashCode into the low 16 bits. The table length n is always a power of two, so (n - 1) & hash keeps only the low bits and replaces a slower %. Without spreading, keys whose hash codes differ only in high bits would all land in one bucket of a small table.

Java

public class Spread {
    static int spread(int h) { return h ^ (h >>> 16); }

    public static void main(String[] args) {
        int n = 16;
        int[] codes = {0x10000, 0x20000, 0x30000, 0x40000};   // differ only above bit 15
        for (int h : codes) {
            System.out.printf("hashCode %08x  raw index %2d  spread index %2d%n",
                    h, (n - 1) & h, (n - 1) & spread(h));
        }
        System.out.println("\"hello\".hashCode() = " + "hello".hashCode());
        System.out.println("index in 16 slots  = " + ((n - 1) & spread("hello".hashCode())));
    }
}

Output

hashCode 00010000  raw index  0  spread index  1
hashCode 00020000  raw index  0  spread index  2
hashCode 00030000  raw index  0  spread index  3
hashCode 00040000  raw index  0  spread index  4
"hello".hashCode() = 99162322
index in 16 slots  = 11

Raw indices are all 0; after spreading they differ. The spreading is one XOR and shift because, as the source comment says, tree bins already bound the worst case, so a stronger mix is not worth its cost.

Example 2: null keys, equal keys, and broken hashCode

A null key hashes to 0 and lives in bucket 0; HashMap allows one null key and any number of null values. A lookup compares the stored hash first, then reference equality, then equals. A key class that overrides equals but not hashCode breaks lookups, because equal keys land in different buckets.

Java

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

public class NullsAndContracts {
    static final class BadKey {
        final String id;
        BadKey(String id) { this.id = id; }
        @Override public boolean equals(Object o) { return o instanceof BadKey b && b.id.equals(id); }
        // hashCode not overridden: identity hash differs per instance
    }

    record GoodKey(String id) {}

    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put(null, 1);
        m.put("a", null);
        System.out.println(m.get(null) + " " + m.containsKey("a") + " " + m.get("a"));

        Map<BadKey, String> bad = new HashMap<>();
        bad.put(new BadKey("x"), "value");
        System.out.println("bad lookup: " + bad.get(new BadKey("x")));

        Map<GoodKey, String> good = new HashMap<>();
        good.put(new GoodKey("x"), "value");
        System.out.println("good lookup: " + good.get(new GoodKey("x")));
    }
}

Output

1 true null
bad lookup: null
good lookup: value

get returns null both for a missing key and for a key mapped to null; containsKey tells them apart. Records generate equals and hashCode from their components, so GoodKey works.

Example 3: collisions and treeification

Entries in one bucket form a singly linked list of Node objects. When a put appends a node to a list that already holds TREEIFY_THRESHOLD (8) entries, treeifyBin runs. If the table is shorter than MIN_TREEIFY_CAPACITY (64), it resizes instead, because a small table is the more likely cause of collisions. Once the table has 64 slots, the bucket becomes a red-black tree of TreeNode objects, so lookups in it are O(log n) instead of O(n). When a resize split or removals leave 6 or fewer entries (UNTREEIFY_THRESHOLD), the tree turns back into a list.

Java

import java.lang.reflect.Field;
import java.util.HashMap;

public class Treeify {
    // All keys collide: same hashCode. Comparable lets the tree order them.
    record Key(int id) implements Comparable<Key> {
        @Override public int hashCode() { return 42; }
        @Override public int compareTo(Key o) { return Integer.compare(id, o.id); }
    }

    static Object[] table(HashMap<?, ?> map) throws Exception {
        Field f = HashMap.class.getDeclaredField("table");
        f.setAccessible(true);
        return (Object[]) f.get(map);
    }

    public static void main(String[] args) throws Exception {
        HashMap<Key, Integer> map = new HashMap<>();
        for (int i = 1; i <= 11; i++) {
            map.put(new Key(i), i);
            Object[] t = table(map);
            Object bin = t[(t.length - 1) & (42 ^ (42 >>> 16))];
            System.out.println("size " + i + "  table " + t.length + "  bin " + bin.getClass().getSimpleName());
        }
        System.out.println("get(7) = " + map.get(new Key(7)));
    }
}

Output

size 1  table 16  bin Node
size 2  table 16  bin Node
size 3  table 16  bin Node
size 4  table 16  bin Node
size 5  table 16  bin Node
size 6  table 16  bin Node
size 7  table 16  bin Node
size 8  table 16  bin Node
size 9  table 32  bin Node
size 10  table 64  bin Node
size 11  table 64  bin TreeNode
get(7) = 7

The ninth put appends to a chain of 8 while the table has 16 slots, so the table doubles to 32; the tenth doubles it to 64; the eleventh converts the bin to TreeNode. Tree nodes need about twice the space of plain nodes, which is why trees appear only for long chains. The tree orders keys by compareTo when the keys are Comparable, and otherwise by class name and identity hash, which still works but gives slower lookups.

Example 4: load factor and resize with bucket split

The load factor is the ratio of entries to table slots at which the table doubles: the threshold field equals capacity * loadFactor, 12 for a default map. On resize each entry either stays at index i or moves to i + oldCap, decided by the single bit hash & oldCap. No hash is recomputed and each chain splits into a "lo" and a "hi" list in its original order.

Java

import java.lang.reflect.Field;
import java.util.HashMap;

public class ResizeSplit {
    static int capacity(HashMap<?, ?> m) throws Exception {
        Field f = HashMap.class.getDeclaredField("table");
        f.setAccessible(true);
        Object[] t = (Object[]) f.get(m);
        return t == null ? 0 : t.length;
    }

    public static void main(String[] args) throws Exception {
        HashMap<Integer, Integer> m = new HashMap<>();
        System.out.println("before first put: " + capacity(m));
        int last = 0;
        for (int i = 0; i < 100; i++) {
            m.put(i, i);
            int c = capacity(m);
            if (c != last) { System.out.println("size " + m.size() + " -> capacity " + c); last = c; }
        }

        int oldCap = 16;
        for (int h : new int[] {5, 21, 37, 53}) {   // all in bucket 5 of a 16-slot table
            int newIndex = (h & oldCap) == 0 ? 5 : 5 + oldCap;
            System.out.println("hash " + h + ": bucket 5 -> " + newIndex + " (check " + (h & 31) + ")");
        }
    }
}

Output

before first put: 0
size 1 -> capacity 16
size 13 -> capacity 32
size 25 -> capacity 64
size 49 -> capacity 128
size 97 -> capacity 256
hash 5: bucket 5 -> 5 (check 5)
hash 21: bucket 5 -> 21 (check 21)
hash 37: bucket 5 -> 5 (check 5)
hash 53: bucket 5 -> 21 (check 21)

Integer.hashCode is the value itself, so each hash equals its key. The resize points 13, 25, 49, 97 are the sizes just above 12, 24, 48, and 96. A lower load factor trades memory for shorter chains; a higher one does the reverse.

Example 5: sizing with HashMap.newHashMap (Java 19)

new HashMap<>(n) sets the initial capacity, not the number of entries the map holds without resizing. With load factor 0.75, a map for 100 entries built with new HashMap<>(100) gets capacity 128 and threshold 96, so it resizes once. HashMap.newHashMap(int numMappings) (Java 19) computes ceil(numMappings / 0.75) first. HashSet.newHashSet and LinkedHashMap.newLinkedHashMap were added at the same time.

Java

import java.lang.reflect.Field;
import java.util.HashMap;

public class Presize {
    static int capacity(HashMap<?, ?> m) throws Exception {
        Field f = HashMap.class.getDeclaredField("table");
        f.setAccessible(true);
        return ((Object[]) f.get(m)).length;
    }

    static int resizes(HashMap<Integer, Integer> m, int n) throws Exception {
        int count = 0, last = -1;
        for (int i = 0; i < n; i++) {
            m.put(i, i);
            int c = capacity(m);
            if (last != -1 && c != last) count++;
            last = c;
        }
        return count;
    }

    public static void main(String[] args) throws Exception {
        HashMap<Integer, Integer> a = new HashMap<>(100);
        HashMap<Integer, Integer> b = HashMap.newHashMap(100);
        System.out.println("new HashMap<>(100):    resizes " + resizes(a, 100) + ", capacity " + capacity(a));
        System.out.println("HashMap.newHashMap(100): resizes " + resizes(b, 100) + ", capacity " + capacity(b));
    }
}

Output

new HashMap<>(100):    resizes 1, capacity 256
HashMap.newHashMap(100): resizes 0, capacity 256

A requested capacity is rounded up to the next power of two (tableSizeFor). newHashMap(100) asks for 134, which rounds to 256 with threshold 192.

Example 6: HashSet, computeIfAbsent, and merge

HashSet is a HashMap whose values are one shared dummy object, PRESENT; add returns map.put(e, PRESENT) == null. computeIfAbsent looks up the key once and creates a value only when absent. merge combines a new value with an existing one, and removes the key when the function returns null. The value functions here are lambdas and method references, taught in Lambdas and Functional Interfaces.

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class MapOps {
    public static void main(String[] args) {
        Set<String> seen = new HashSet<>();
        System.out.println(seen.add("a") + " " + seen.add("a"));

        String[] words = {"apple", "avocado", "banana", "blueberry", "cherry", "apple"};
        Map<Character, List<String>> byLetter = new HashMap<>();
        Map<String, Integer> counts = new HashMap<>();
        for (String w : words) {
            byLetter.computeIfAbsent(w.charAt(0), k -> new ArrayList<>()).add(w);
            counts.merge(w, 1, Integer::sum);
        }
        System.out.println(new TreeMap<>(byLetter));
        System.out.println(new TreeMap<>(counts));

        counts.merge("apple", -2, (oldV, delta) -> oldV + delta == 0 ? null : oldV + delta);
        System.out.println("apple present: " + counts.containsKey("apple"));
    }
}

Output

true false
{a=[apple, avocado, apple], b=[banana, blueberry], c=[cherry]}
{apple=2, avocado=1, banana=1, blueberry=1, cherry=1}
apple present: false

The maps are copied into a TreeMap before printing because HashMap iteration order is not specified: it follows bucket order, changes after a resize, and can differ between JDK versions. computeIfAbsent must not modify the same map inside its function; HashMap throws ConcurrentModificationException when it detects that.

Example 7: LinkedHashMap and an LRU cache

LinkedHashMap adds a doubly linked list through all entries. In insertion order (the default) iteration follows put order. With accessOrder = true, every get or put of an existing key moves the entry to the end. Overriding removeEldestEntry evicts the first entry after each insert, which gives a least recently used (LRU) cache in a few lines.

Java

import java.util.LinkedHashMap;
import java.util.Map;

public class LruCache {
    static final class Lru<K, V> extends LinkedHashMap<K, V> {
        private final int maxEntries;
        Lru(int maxEntries) {
            super(16, 0.75f, true);              // access order
            this.maxEntries = maxEntries;
        }
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > maxEntries;
        }
    }

    public static void main(String[] args) {
        Lru<String, Integer> cache = new Lru<>(3);
        cache.put("a", 1); cache.put("b", 2); cache.put("c", 3);
        System.out.println(cache);
        cache.get("a");                           // a becomes most recent
        System.out.println(cache);
        cache.put("d", 4);                        // evicts b, the least recent
        System.out.println(cache);
        System.out.println("eldest: " + cache.firstEntry().getKey()
                + ", newest: " + cache.lastEntry().getKey());
    }
}

Output

{a=1, b=2, c=3}
{b=2, c=3, a=1}
{c=3, a=1, d=4}
eldest: c, newest: d

firstEntry and lastEntry come from SequencedMap (Java 21). LinkedHashMap is not thread-safe; a shared cache needs a lock around it or a concurrent design from Concurrent Collections.

Example 8: IdentityHashMap and WeakHashMap

IdentityHashMap compares keys with == and uses System.identityHashCode. It uses open addressing (keys and values alternate in one array, and collisions probe the next slot) instead of chained buckets. It fits graph algorithms that track visited objects and serialization code. WeakHashMap holds keys through weak references, so an entry disappears after its key becomes unreachable and is collected.

Java

import java.util.HashMap;
import java.util.IdentityHashMap;
import java.util.Map;
import java.util.WeakHashMap;

public class SpecialMaps {
    public static void main(String[] args) throws InterruptedException {
        String k1 = new String("key");
        String k2 = new String("key");
        Map<String, Integer> byEquals = new HashMap<>();
        Map<String, Integer> byIdentity = new IdentityHashMap<>();
        byEquals.put(k1, 1); byEquals.put(k2, 2);
        byIdentity.put(k1, 1); byIdentity.put(k2, 2);
        System.out.println("HashMap size " + byEquals.size() + ", IdentityHashMap size " + byIdentity.size());

        Map<Object, String> weak = new WeakHashMap<>();
        Object strong = new Object();
        weak.put(strong, "kept");
        weak.put(new Object(), "collectable");
        for (int i = 0; i < 50 && weak.size() > 1; i++) {
            System.gc();
            Thread.sleep(10);
        }
        System.out.println("WeakHashMap size after GC: " + weak.size());
        System.out.println("strong key still present: " + weak.containsKey(strong));
    }
}

Output

HashMap size 1, IdentityHashMap size 2
WeakHashMap size after GC: 1
strong key still present: true

System.gc() is only a request, so the loop retries until the entry is gone or 50 attempts pass. WeakHashMap keys must not be referenced from their own values, or they stay reachable. Weak references and reachability are introduced in Immutability, Defensive Copying, and Object Lifecycle.

Interview points

hash = h ^ (h >>> 16); index = (n - 1) & hash with n a power of two.
Default capacity 16 (allocated lazily), load factor 0.75, threshold capacity * loadFactor.
A bucket list treeifies when a put appends to a chain of 8, and only when the table has at least 64 slots; otherwise the table resizes. Trees untreeify at 6.
Resize doubles the table; each entry stays at i or moves to i + oldCap based on hash & oldCap.
Worst-case lookup in a tree bin is O(log n); with Comparable keys the tree orders by compareTo.
new HashMap<>(n) is a capacity hint; HashMap.newHashMap(n) (Java 19) sizes for n entries.
One null key is allowed and sits in bucket 0; Hashtable and ConcurrentHashMap reject null.
HashSet wraps a HashMap with a dummy value. LinkedHashMap(cap, lf, true) plus removeEldestEntry is an LRU cache.
Iteration order of HashMap is not specified and changes after a resize.
Mutating a key's hashCode fields after insertion makes the entry unreachable by lookup.

Summary

HashMap is a power-of-two array of buckets; each bucket is a linked list or a red-black tree.
Spreading high bits into low bits compensates for masking.
Treeification bounds the cost of many collisions, including deliberate collision attacks.
computeIfAbsent and merge replace get-check-put sequences with one lookup.
IdentityHashMap uses == and open addressing; WeakHashMap drops entries whose keys are collected.