TRT
Sign in
easyFoundationsconcept

Why does a hash map resize before it is full?

Explain the load factor, why a fuller table gets slower, why tables double instead of growing by a fixed amount, and what a resize costs.

TRT practice prompt — not a verified question from a named employer.

The Runtime Theory Team2 min read
Learn it firstResizing and load factorAs a table fills, collisions pile up. Tables track their load factor and, past a limit, move every entry into an array twice the size.

A strong answer

A hash map stays fast only while its slots are mostly free. The measure of fullness is the load factor: the number of entries divided by the number of slots. As it rises, collisions become more common and lookups compare more keys. With linear probing, a lookup for a missing key checks about 2.5 slots when the table is half full, 8.5 at 75% and about 50 at 90%. The cost explodes as the table approaches full, and a completely full table with open addressing can't accept another key at all. Chaining degrades more gently, but its lists grow with the load factor too.

So every implementation picks a maximum load factor and grows before reaching it: Java's HashMap at 0.75, Python's dict at two-thirds and Rust's HashMap at seven-eighths. The right limit depends on the collision strategy. Rust's table checks 16 slots at once with a single vector instruction, so it tolerates fuller tables.

Growing means allocating a larger array and inserting every entry again, because a key's slot depends on the size of the array. That makes the insert that triggers a resize cost O(n). Doubling keeps the average cost constant: resizes happen at 8, 16, 32 and so on, so the total number of entries moved stays below 2n, fewer than two moves per insert. Growing by a fixed number of slots instead would resize so often that the average insert would cost O(n).

If you know how many entries a map will hold, create it with enough capacity up front, and it never has to resize.

What the interviewer is listening for

  • The load factor, and how lookup cost climbs steeply as it approaches 1.
  • A concrete limit from a real implementation, and why limits differ.
  • Why a resize has to re-insert every entry: slots depend on the capacity.
  • Doubling, and the amortized argument that keeps inserts O(1) on average.

Common mistakes

  • Saying the table resizes "when it runs out of space". With open addressing that is far too late, and with chaining it never runs out.
  • Saying a resize copies the old array across as it is. Entries have to be re-inserted, because their slots change.
  • Calling every insert O(1). Inserts are O(1) amortized; the one that triggers a resize is O(n).

This answer walks

Practice follow-ups

  1. 01A latency-sensitive server slows down every time one of its large maps resizes. How could you avoid that?
  2. 02Why can Rust's HashMap run seven-eighths full when a table with linear probing slows down badly at 90%?
  3. 03After an 8-slot table doubles, a key from slot 3 can only end up in one of two slots. Which, and why?
  4. 04Should a hash map shrink when most of its entries are removed? What goes wrong if it shrinks too eagerly?
  5. 05Deleted entries leave tombstones that slow down lookups. How does a resize deal with them?

More interviews in this track

hard · dsaHow would you count distinct users across a fleet of services in constant memory?hard · dsaWhy can't a sparse table answer range sums?hard · dsaWhy is a lock-free stack still hard to get right?

Not started

Sign in to save your learning progress.

Sign in to save