Stage 4: HashMap internals, lesson 9 of 13

HashMap internals 9: Resize and rehash

Advanced3 min readall versions
Explain it forThe essentials plus production detail and pitfalls.

When size goes over the threshold, HashMap doubles the table (16 → 32 → 64 …) and moves every entry into the new array.

Java 8+ does this cleverly:

  • It reuses the stored hash of each node; nothing is recalculated.
  • Doubling the table means the index uses one more bit of the hash. That bit is hash & oldCapacity:
  • bit is 0: the entry stays at index i;
  • bit is 1: the entry moves to index i + oldCapacity.
  • Each bucket is therefore split into a "lo" list and a "hi" list, and the order of entries is preserved.

Example with 16 → 32 buckets: "book" (bucket 7) stays at 7, "cat" (also bucket 7) moves to 23, and "java" moves from 3 to 19.

Costs to remember: a resize is O(n), a pause proportional to the map size, so presize big maps (part 8). The table never shrinks, even if you remove most entries.

HashMap lab

A faithful simulation of Java's HashMap. Type a key and watch every step.

size
12
capacity
16
threshold
12
load
0.75
resizes
0
longest
3
0banana=2orange=7plum=10
1apple=1cherry=6
2kiwi=5lemon=8pear=11
3
4
5
6
7
8peach=9
9
10
11grape=4
12guava=12
13
14
15mango=3
  1. 12 keys with capacity 16 and load factor 0.75: the map is exactly at its threshold (12). The next new key triggers a resize to 32.

Example

Java
int oldCap = 16;
for (String key : List.of("book", "cat", "java")) {
    int h = key.hashCode() ^ (key.hashCode() >>> 16);
    int before = h & (oldCap - 1);
    int after = h & (2 * oldCap - 1);
    boolean moves = (h & oldCap) != 0;                // the one extra bit decides
    System.out.println(key + ": " + before + " -> " + after + (moves ? "  (moved by +16)" : "  (stayed)"));
}
// book: 7 -> 7   (stayed)
// cat:  7 -> 23  (moved by +16)
// java: 3 -> 19  (moved by +16)

Common mistake

Removing most entries from a huge HashMap and expecting memory to be released. The table never shrinks; copy the survivors into a new map instead.

Under the hood

Because entries only ever go to i or i + oldCapacity, and order is kept, the resize is simple and has no risk of loops. Java 7 was different: it recalculated every index and reversed each list while moving, which could corrupt a bucket into a cycle under concurrent use (part 12). ConcurrentHashMap resizes cooperatively: other threads that touch the map help move buckets.

Check yourself

During a resize from 16 to 32 buckets, where can an entry in bucket 5 go?

How this connects

Part of HashMap internals, part by part.

Was this lesson helpful?

Finished reading? Mark it complete to track your progress.