When a hash table doubles its bucket array, why must every existing entry be re-bucketed?
answer
- where does a slot number come from
- the table size is inside the formula
- hashes stay fixed, indexes do not
- two keys sharing a bucket at size 8
- 7 mod 8 versus 15 mod 16
basics
~20 sA key's bucket index is derived from its hash reduced by the table size, so changing the size changes where most keys belong. Copying buckets across unchanged would leave entries in slots that lookups no longer probe.
solid answer
~50 sThe bucket index is a function of both the hash and the current capacity — typically `hash(k) mod capacity`, or the low bits of the hash when capacity is a power of two. Grow the capacity and that function changes, so the table must walk every entry and place it at its newly computed index. Concretely, in an 8-bucket table keys whose hashes are 7 and 15 both land in bucket 7; after doubling to 16 buckets, 7 stays in bucket 7 while 15 moves to bucket 15. If you copied the old buckets over untouched, a later lookup for the second key would compute index 15, find it empty, and report the key missing. That walk is what makes a resize O(n) in the current entry count, and it is the reason a single insert can be enormously more expensive than its neighbours.
code
pseudocode · 10 lines// old_bucket has m slots, each a list of keys
new_bucket = array of 2 * m empty lists
for i in 0..m-1
for each key k in old_bucket[i]
j = hash(k) mod (2 * m) // index depends on the NEW size
add k to new_bucket[j]
old_bucket = new_bucket
m = 2 * mgo deeper
Be ready to say that the slot is computed from the hash and the current table size, so growing the table changes almost every slot. The 7-and-15 example in an 8-bucket table is enough to prove it.
Explain the mechanics: the index reduction, why doubling a power-of-two capacity moves about half the entries, and why the transfer makes a resize Θ(n) in the number of stored entries.
Show what the transfer costs in production — a transient double-allocation, invalidated iterators, reshuffled iteration order, and one insert that runs orders of magnitude longer than its neighbours.
Own the consequence: because index depends on capacity, any design that must avoid mass re-placement has to change the mapping scheme rather than tune the load factor. Be able to say when that complexity is worth buying.
## Where a bucket index comes from A hash table stores entries in an array of `capacity` buckets. Placement is a two-step reduction: first a hash function maps the key to a wide integer, then that integer is reduced into the range `0..capacity-1` — usually `hash(k) mod capacity`, or `hash(k) AND (capacity - 1)` when the capacity is kept a power of two. Lookup repeats exactly the same two steps, which is what makes the table fast: it computes where the key *must* be rather than searching. The critical detail is that **the second step depends on the table size**. The hash of a key never changes, but the slot that hash reduces to changes the moment `capacity` changes. ## The worked example Take an 8-bucket chained table holding two keys whose hashes are 7 and 15. - 7 mod 8 = 7, and 15 mod 8 = 7 — both live in bucket 7, chained together. - Double to 16 buckets: 7 mod 16 = 7, but 15 mod 16 = 15. The first key stays put; the second belongs somewhere entirely different. Nothing about the keys changed — only the divisor did. A lookup after the resize computes index 15 for the second key, finds an empty bucket, and concludes the key is absent. The table has not lost data so much as hidden it. This is also why a resize cannot be a memory `realloc` that simply extends the array. Extending gives you buckets 8..15 full of nothing, while every key that should now live there is still sitting in the first half. ## What "rehashing" actually costs A resize allocates the new array, then iterates every occupied slot and every chain node in the old one, recomputing each entry's index and linking it into the new array. The work is proportional to the number of stored entries, so a resize is Θ(n) time and, during the transfer, both arrays are live — a transient memory peak of roughly 1.5x to 3x the steady-state footprint depending on layout. One worthwhile nuance: "rehash" is a slight misnomer in many production tables. Because a hash function can be expensive on long keys, implementations often store the computed hash alongside each entry, so a resize recomputes only the cheap *index* reduction, not the hash itself. The entries still all move; only the arithmetic per entry gets cheaper. Under open addressing (entries stored directly in the array, collisions resolved by probing to another slot) the transfer is a full re-insertion: each surviving entry is probed into the new array from its new home slot. A pleasant side effect is that tombstones — the markers left behind by deletions so probe chains stay intact — are dropped rather than carried over, so a resize also cleans up deletion debris. ## Consequences a candidate should be able to name - **A resize invalidates positions.** Any index, pointer, or iterator into the bucket array is meaningless afterwards, which is why iterating a table while inserting into it is unsafe in essentially every implementation. - **Iteration order can change.** If iteration walks buckets in order, a resize reshuffles which entries are adjacent. Order was never a promise, and a resize is the event that most visibly breaks anyone who assumed it was. - **The cost lands on one unlucky operation.** The insert that crosses the growth threshold pays for all n moves. That is the whole reason insertion is described as *amortized* O(1) rather than O(1). ## The wrong answers "Just copy the buckets over" is the common one, and it fails for the reason above. "The hash changes when the table grows" is the other — it does not; the reduction does. A third is "only the colliding keys need to move", which sounds plausible but is backwards: with a power-of-two capacity, doubling splits each old bucket into exactly two destinations based on one newly examined bit, so roughly half of *all* entries move, colliding or not.
- Does the hash function itself have to run again during a resize?Not necessarily. The hash of a key is independent of capacity, so many production tables cache each entry's computed hash next to the entry and a resize recomputes only the cheap index reduction. Every entry still has to be visited and moved; caching the hash reduces the per-entry constant, not the Θ(n) shape of the work.
- If capacity is a power of two, how many entries actually change bucket when it doubles?About half. With a power-of-two capacity the index is the low bits of the hash, so doubling exposes exactly one additional bit. Entries whose new bit is 0 keep their index; those whose bit is 1 move to `index + old_capacity`. Every entry must still be examined to find out which group it is in, so the walk is Θ(n) regardless.
- Why is it unsafe to hold an index into the bucket array across an insert?An insert may cross the growth threshold and trigger a resize, which allocates a fresh array and re-places every entry. Any saved bucket index, node pointer, or iterator position then refers to the old array or to an entry that has moved. That is the mechanical reason iterating a table while inserting into it is rejected or undefined almost everywhere.
Bucket numbers are like postal routes derived from the current number of districts. Redraw the map into twice as many districts and every address has to be re-sorted, even though nobody moved house.
saying these in an interview costs you the question
- Says the old buckets can simply be copied into the larger array
- Thinks a key's hash value changes when the table grows
- Claims only keys that were colliding need to move
- Assumes resizing is O(1) because it just allocates memory
- Believes iteration order is stable across a resize