HashMap

the picture

you know how map.get(key) is "instant" even with a million entries, while list.contains(x) crawls? the map isn't searching faster. it isn't searching at all.

think of a wall of numbered pigeonholes (the table). when you hand over a parcel, the clerk doesn't look for a free hole. they compute the hole number from the name on the label (the hash), and put it there. to find it later, they compute the same number and look in exactly one hole. if two names compute to the same hole, the parcels just stack up in it (a chain), and the clerk checks each label in that one stack.

everything in that lab follows jdk 25's HashMap.java line for line. i checked it against the real thing: same table sizes after every put, same moment of treeification, same iteration order.

from key to bucket

three steps, all visible in the lab's top panel:

1. key.hashCode(): any int. for a String it's s[0]·31^(n-1) + s[1]·31^(n-2) + ... + s[n-1], with int overflow. so "Aa" is 65·31 + 97 = 2112.
2. spread: h ^ (h >>> 16). mixes the top 16 bits into the bottom 16.
3. index: hash & (n - 1). the table size n is always a power of two, so n - 1 is a mask of ones, and this keeps the low bits. it's hash mod n, without a division and without ever going negative.

void main() {
    Map<String, Integer> counts = new HashMap<>();
    for (String w : "the cat and the hat and the bat".split(" ")) {
        counts.merge(w, 1, Integer::sum);
    }
    IO.println(counts.get("the") + " " + counts.getOrDefault("dog", 0) + " " + counts.size());
    IO.println("Aa".hashCode() + " " + "BB".hashCode());
}

3 0 5
2112 2112

see that second line? two different strings, one hash code. 'A' is one less than 'B', and 'a' is 31 more than 'B', so the sums land on the same number. it's not a bug, it's arithmetic: there are 2³² possible hash codes and infinitely many strings. collisions are guaranteed, so the map has to handle them.

why the spread?

the mask only looks at the low bits. if your keys' hash codes differ only in the high bits, they'd all pile into one bucket. the spread step is the cheap fix.

contrived? a bit. but hash codes that only vary up top are real (think floats, or ids that step by a large power of two), and the spread costs one shift and one xor per call.

collisions, resizing and the 0.75 rule

a bucket holds a chain of nodes. a new key goes on the end of its bucket's chain. a lookup computes the bucket, then walks that chain comparing hash first (cheap int compare) and equals only when the hashes match.

chains stay short as long as the table stays roomy. so the map tracks a threshold: capacity × load factor, and the default load factor is 0.75. the moment size goes past it, the table doubles:

doubling has a neat property. since the new mask has exactly one more bit, every entry in bucket j either stays at j or moves to j + oldCapacity, decided by that single bit (hash & oldCapacity). so java splits each chain in two, keeping the order, without recomputing a single hashCode(). that's the amber flash in the lab.

when one bucket gets crowded

if a bucket already holds 8 entries and you add another, the chain is asked to become a red-black tree (TreeNodes), so lookups in that bucket go from O(n) to O(log n). but only if the table has at least 64 buckets. smaller tables just resize instead, on the theory that the crowding is probably the table being too small. the lab shows exactly that: the 9th colliding key doubles 16 → 32, the 10th doubles 32 → 64, the 11th finally treeifies.

with a decent hashCode(), this basically never happens (the comments in HashMap.java put the odds of 8 in one bucket, with random hash codes, at less than one in ten million). it's armour against bad or hostile hash codes. the whole story, with the tree, lives in HashMap internals.

Map<String, Integer> map = new HashMap<>();
for (String k : List.of("pear", "apple", "fig", "banana", "kiwi")) map.put(k, k.length());
IO.println(map.keySet());

the deal you sign with your keys

the map trusts two methods on your keys, and they have to agree (more in the object methods):

• equal objects must have equal hashCode()s. break this and the map looks in the wrong bucket and never finds an entry that's right there.
• hashCode() must not change while the key is in the map.

a few more things the map promises (or doesn't):

• one null key is fine. it hashes to 0 and lives in bucket 0. null values are fine too, which is why get returning null is ambiguous: use containsKey or getOrDefault.
• iteration order is not specified and can change after a resize. never depend on it.
• not thread-safe. two threads putting at once can lose entries or corrupt a chain. use ConcurrentHashMap.

void main() {
    int h = "polygenelubricants".hashCode();
    IO.println(h + " " + Math.abs(h) + " " + Math.abs(h) % 31 + " " + (h & 15));
}

-2147483648 -2147483648 -2 0

what everything costs