JAVA / COLLECTIONS
HashMap buckets, collisions and resize behaviour
Predict which bucket any key lands in, why unequal keys share one chain, and exactly when a HashMap doubles its table and re-splits those chains.
What you will learn
- Work out a key's bucket by hand: (h ^ h >>> 16) & (table length - 1)
- Say exactly when the table doubles: when size passes capacity * 0.75
- Explain why colliding keys coexist: equals decides identity, hashCode only location
- Size a map with expected / 0.75 + 1 instead of trusting new HashMap<>(n)
Understanding HashMap buckets, collisions and resize behaviour
A HashMap keeps one array of nodes whose length is always a power of two, and it picks the slot for a key with a bitwise mask rather than a division: index = hash & (length - 1). Masking looks only at the lowest bits of the hash, so a hashCode that varies mainly in its high bits would pile every key into one slot. That is why HashMap first pushes the key's hashCode through h ^ (h >>> 16), folding the top sixteen bits down into the bottom sixteen so they also influence the index.
Two keys collide when their masked hashes agree, and for unequal keys that happens constantly: sixteen slots have to absorb four billion possible hash values. Colliding entries are chained inside the slot, and a lookup walks that chain comparing the node's cached int hash first and only then calling equals. So hashCode decides where to look and equals decides what counts as the same key, which is why a class with a constant hashCode still stores every distinct key correctly, just slowly. Once a single chain reaches eight nodes and the table is at least 64 long, HashMap turns that chain into a red-black tree so a pathological bucket costs O(log n) instead of O(n).
Growth is driven by size, not by collisions: after each insertion HashMap compares size against threshold = capacity * loadFactor, which is 12 for the default 16 slots at 0.75, and doubles the table when it is exceeded. Doubling adds exactly one bit to the mask, so an entry in old slot i either stays at i or moves to i + oldCapacity, decided by the single bit hash & oldCapacity; no hashCode is called again, the stored hash is simply re-masked. Because each chain is split into two lists that keep their relative order, iteration order changes after a resize even though no key changed, which is one concrete reason HashMap order must never be relied on.
import java.util.HashMap;
import java.util.Map;
public class Buckets {
public static void main(String[] args) {
// Requested capacity 4 gives a 4-slot table, threshold 4 * 0.75 = 3.
Map<Integer, String> map = new HashMap<>(4);
map.put(1, "a");
map.put(5, "b");
map.put(9, "c");
System.out.println("size 3, table 4: " + map.keySet());
map.put(13, "d"); // size 4 passes threshold 3, table doubles to 8
System.out.println("size 4, table 8: " + map.keySet());
for (int cap = 4; cap <= 8; cap *= 2) {
System.out.print("bucket index at table " + cap + ":");
for (int key : new int[] {1, 5, 9, 13}) {
int h = key ^ (key >>> 16); // what HashMap does to hashCode()
System.out.print(" " + key + "->" + (h & (cap - 1)));
}
System.out.println();
}
}
}A key's bucket is hash & (table length - 1), so it depends on the current capacity, while equals rather than the hash decides whether two keys in one bucket are the same key.
Worked examples
Every key in one bucket
A constant hashCode is legal and the map still answers correctly, but every lookup becomes a chain walk.
import java.util.HashMap;
import java.util.Map;
public class OneBucket {
static final class Sku {
final String code;
Sku(String code) { this.code = code; }
@Override public int hashCode() { return 7; }
@Override public boolean equals(Object o) {
return o instanceof Sku && ((Sku) o).code.equals(code);
}
@Override public String toString() { return code; }
}
public static void main(String[] args) {
Map<Sku, Integer> stock = new HashMap<>();
for (int i = 0; i < 5; i++) {
stock.put(new Sku("S" + i), i);
}
System.out.println("size = " + stock.size());
System.out.println("get(S3) = " + stock.get(new Sku("S3")));
System.out.println("keys = " + stock.keySet());
}
}Example explained
Line 1hashCode() returns 7 for every Sku, so 7 & 15 sends all five entries into slot 7 of the 16-slot table.
Line 2equals() still separates them, so size is 5 and nothing is overwritten: hashing controls placement, not identity.
Line 3get(new Sku("S3")) finds the right slot immediately but then compares four keys before matching, because the cached-hash shortcut cannot rule anything out when all hashes are equal.
Line 4keys prints in insertion order only because a chain appends at the tail; that is not an ordering guarantee.
Why the hash is spread before masking
Keys that differ only above bit 15 would all share slot 0 until the high bits are folded down.
import java.util.HashMap;
import java.util.Map;
public class Spread {
public static void main(String[] args) {
int[] keys = {196608, 65536, 131072, 0};
for (int key : keys) {
int spread = key ^ (key >>> 16); // Integer.hashCode(key) is key itself
System.out.println(key + ": raw bucket " + (key & 15)
+ ", spread bucket " + (spread & 15));
}
Map<Integer, String> map = new HashMap<>(); // 16 slots, threshold 12
for (int key : keys) {
map.put(key, "x");
}
System.out.println("iteration order: " + map.keySet());
}
}Example explained
Line 1Integer.hashCode returns the value, so every multiple of 65536 has zeros in its low four bits and key & 15 is 0 for all four keys.
Line 2key ^ (key >>> 16) moves bits 16-19 down into bits 0-3, which is what turns one shared slot into slots 0, 1, 2 and 3.
Line 3The keys were inserted as 196608, 65536, 131072, 0 but iterate as 0, 65536, 131072, 196608, because iteration walks the table from slot 0 upward.
Line 4Only four entries exist against a threshold of 12, so nothing here is affected by a resize.
A mutated key is lost in the old bucket
HashMap stores the hash it computed at insertion time, so changing a key afterwards leaves the entry unreachable.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class MutatedKey {
public static void main(String[] args) {
List<String> key = new ArrayList<>();
key.add("a");
Map<List<String>, String> map = new HashMap<>();
map.put(key, "value");
System.out.println("found before: " + map.get(key));
key.add("b"); // the key's hashCode changes from 128 to 4066
System.out.println("found after: " + map.get(key));
System.out.println("still there: " + map.containsValue("value"));
System.out.println("entries: " + map);
}
}Example explained
Line 1The list hashCode is defined as 31 * h + element hash, so [a] hashes to 128 and lands in slot 128 & 15 = 0.
Line 2Adding "b" makes the hash 4066, which masks to slot 2, so get() searches a different bucket and returns null.
Line 3Even if the new hash had masked to the same slot, the node's cached hash field still holds 128 and the e.hash == hash test would fail.
Line 4containsValue scans every slot and every chain, which proves the entry was never removed, only made unfindable.
Important notes
The eight-node treeify threshold only applies once the table is at least 64 slots long; below that HashMap resizes instead of building a tree, and during a later split a tree with six or fewer nodes turns back into a list.
Slot indexes, split placement and iteration order are internals of java.util.HashMap, useful for reasoning about cost but not part of the contract; note also that the table never shrinks when entries are removed.
Common mistakes
Passing the expected entry count straight to new HashMap<>(1000): the constructor rounds up to a 1024-slot table but ignores the 0.75 load factor, so the map still resizes at 768 entries.
Writing hashCode() as a constant, or as a value that only varies above bit 15, on the assumption that a bigger table will sort it out; every such key masks into the same slot at any capacity and get() degrades to a linear chain walk.
Relying on the ascending order HashMap shows for small Integer keys: that order is just ascending slot index, and the insertion that crosses the threshold reshuffles it, as the 13-then-5 order in the main example shows.
Try it yourself
Change, predict, then run
Build a map with new HashMap<>(4), insert the keys 2, 6 and 10, print keySet(), then insert 14 and print keySet() again. Compute h & 3 and h & 7 for all four keys by hand and use them to explain the order you saw.
Open the Java workspaceCheck your understanding
A HashMap with the default 16-slot table holds the Integer keys 1, 17 and 33, all chained in slot 1. Other insertions then push size past 12 and the table doubles to 32 slots. Where do those three keys end up?
- 1 and 33 stay chained in slot 1, and 17 moves to slot 17
- All three stay chained together in slot 1, because doubling keeps existing chains intact
- All three have hashCode() called again and land in unrelated slots
- 1 stays in slot 1, 17 moves to slot 17, and 33 moves to slot 33
Show answer
Doubling adds one bit to the mask, so each entry either stays at slot i or moves to i + 16 depending on hash & 16. That bit is clear for 1 and for 33 (32 + 1), so they remain chained at slot 1, while 17 has it set and moves to 17. Option 4 is tempting because 33 looks like a slot-33 key, but a 32-slot table masks with 31 and 33 & 31 = 1; the stored hash is only re-masked, never recomputed, which also rules out option 3.