Stage 4: HashMap internals, lesson 7 of 13

HashMap internals 7: Load factor

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

The load factor decides how full the table may get before it grows:

  • threshold = capacity × load factor. With the defaults, 16 × 0.75 = 12.
  • When size becomes greater than the threshold (the 13th entry), the table doubles to 32 buckets, and the new threshold is 24.

The trade-off:

  • Lower (for example 0.5): fewer collisions and faster lookups, but more memory and more frequent resizes.
  • Higher (for example 1.0): less memory, but longer chains and slower lookups.
  • 0.75 is the balance. The JDK source notes that with the default load factor and a reasonable hash, the chance of any bucket reaching 8 entries is about 0.00000006.

You can pass a load factor to the constructor, but the default is right for almost every program.

HashMap lab

Example

Java
Map<String, Integer> a = new HashMap<>();              // capacity 16, load factor 0.75 -> threshold 12
Map<String, Integer> b = new HashMap<>(16, 0.5f);      // resizes after 8 entries: faster lookups, more memory
Map<String, Integer> c = new HashMap<>(16, 1.0f);      // resizes after 16 entries: less memory, longer chains

for (int i = 1; i <= 13; i++) {
    a.put("key" + i, i);                               // the 13th put makes size 13 > 12 -> resize to 32
}

Common mistake

Raising the load factor to "save memory" in a performance-critical map. Longer chains make every get() and put() slower.

Under the hood

The 0.00000006 figure comes from modelling bucket sizes with a Poisson distribution (average 0.5 entries per bucket at load factor 0.75). It's also why tree buckets are rare in practice: they mostly appear with bad hash codes or deliberate attacks.

Check yourself

With the default capacity and load factor, which put() triggers the first resize?

How this connects

Part of HashMap internals, part by part.

Was this lesson helpful?

Finished reading? Mark it complete to track your progress.