A hash table keeps its load factor in range by doubling when it fills and halving when it empties, and the two thresholds must be different. Doubling at α = 1 and halving at α = ¼ costs 52 over forty operations at the boundary; doubling and halving both at α = ½ costs 495 for the same forty, rehashing on thirty-nine of them. The gap between the thresholds is the whole mechanism.
Core ideas
One idea with a name worth learning — hysteresis — and two consequences: why the amortised bound holds when the thresholds differ, and why it fails completely when they do not.
Every key’s slot is computed from m, so changing m means recomputing every slot: a resize is Θ(n) and there is no cleverer way. The bound is amortised, exactly as for the two-stack queue: an operation that triggers a resize is expensive, and the sequence containing it is not, because doubling makes resizes exponentially rare.
If the table grows at α = ½ and shrinks at α = ½, then one insertion past the boundary doubles the table, which halves α, which triggers a shrink, which doubles α, and the next operation resizes again. The gap — grow at 1, shrink at ¼ — means that after any resize the load is far from both thresholds, so many operations must happen before another one is due. That gap is called hysteresis.
3 per operation is the promise: forty operations should cost at most 120. The hysteresis policy costs 52, comfortably inside. The equal thresholds cost 495, four times the bound, on the same forty operations — which is what it looks like when a policy has no amortised bound at all rather than a loose one.
The material
Why doubling gives an amortised constant, why the shrink threshold must be lower, and the two policies counted on the same sequence.
A table’s cost depends on its load factor, so the load factor has to be kept in a band. Too high and chains grow or probes cluster; too low and most of the memory is empty. The mechanism is to pick thresholds and resize when one is crossed, rehashing every key into the new table.
A table grows — usually doubling m — when α reaches the growth threshold, and shrinks — usually halving m — when α falls to the shrink threshold. Both resizes rehash all n keys and cost Θ(n).
The standard pair is grow at α = 1 and shrink at α = ¼. The shrink threshold is deliberately far below half the growth threshold, and the next paragraph is why.
Under a policy that doubles at α = 1 and halves at α = ¼, a sequence of k insertions and deletions on a table starting empty costs O(k) in total, so O(1) amortised per operation.
The potential method: give the table a potential that measures how close it is to its next resize — roughly 2n − m above half full and m/2 − n below. An ordinary operation changes n by one and so changes the potential by a constant. A resize costs n and releases potential that the operations since the last resize have paid in, because the gap between the thresholds guarantees there were at least about n/2 of them. The released potential covers the rehash, and the amortised cost of every operation is constant.
That proof needs the gap. If growth and shrink happen at the same load, then immediately after a resize the table is sitting on the other threshold, no operations have accumulated any potential, and the next operation resizes again. There is nothing to release and the argument has no step to make. The failure is not a worse constant; it is the absence of a bound.
The lab’s boundary pattern fills a table and then alternates inserting and deleting, which is the mix designed to sit on a threshold. Forty operations from m = 4:
Read the two rehash counts first. Two resizes in forty operations against thirty-nine. The hysteresis policy resizes twice, early, while the table is growing into its final size, and then never again — the alternating insertions and deletions move α around inside the band and never reach an edge of it. The equal-threshold policy resizes on almost every operation, oscillating between m = 16 and m = 32 from operation 8 onward and moving thirteen or fourteen keys on every resize from operation 13.
The total cost is 52 against 495, and the second one has broken the bound: 3 per operation would be 120. The measured amortised figures are 1.3 and 12.375, and the second is not a constant — it grows with the table, because each thrashing resize costs n and n is proportional to m. Doubling the sequence length on the thrashing policy roughly quadruples its cost.
Forty insertions and no deletions, same thresholds: four rehashes at m = 4, 8, 16, 32, moving 4 + 8 + 16 + 32 = 60 keys in total, for a cost of 100 against the 120 line. The rehash cost of a table that reaches size n is about 2n whatever the sequence, because the doubling costs form a geometric series — which is the cleanest case of the amortised argument and the one to look at before the boundary pattern.
One caution about the measured amortised figure. 13/10 is the total divided by the number of operations for this sequence, and it is below 3, and that is not the bound holding — it is one sequence coming in under it. A different pattern at the same thresholds could come closer to 3 and none can exceed it, and the reason none can is the potential argument above rather than anything the lab did. The lab is what shows you the thrashing policy, which no amount of reasoning about the good policy would have revealed.
Interactive
Double at one load, halve at a lower one, or every operation rehashes
Method
Pick the thresholds, then attack them with the pattern designed to sit between them. A policy tested only on growth has not been tested.
Grow at α_g, shrink at α_s, and require α_s to be well below α_g/2. 1 and ¼ is the standard pair. Equal thresholds, or ½ and ¼, are the ones to be suspicious of, and the reason is arithmetic: after a resize the new load must be far from both edges.
Insertions only. The rehash costs form a geometric series, the total is about 2n, and the cumulative line should sit comfortably under the 3m line. If it does not, the policy is wrong in the easy case and there is no point going further.
Fill the table to just under the growth threshold, then insert and delete alternately. This is the pattern a bad policy dies on, and it is not exotic — a cache or a work queue whose size hovers around a threshold produces it naturally.
The rehash count is the diagnostic; the cost is the symptom. Two rehashes in forty operations is a healthy policy. Thirty-nine in forty is a policy with no amortised bound, and the count says so immediately while the total needs comparing with something.
The first thirteen operations of the lab’s forty, under each policy, starting from m = 4. The pattern fills to thirteen keys and then alternates.
The left column stops resizing after operation 8 and never starts again: α wanders between 9/16 and 7/8 for the remaining thirty-two operations, and neither edge of the band is anywhere near. That is hysteresis working, and it is the whole of the mechanism — there is no cleverness in it beyond choosing two numbers far apart.
The right column resizes on twelve of the first thirteen operations, and keeps going for the rest. Look at operation 8: the insertion pushes α to 1/2, which is the growth threshold, so the table doubles to 32 and α becomes 1/4 — which is below the shrink threshold of 1/2, so the next operation halves it back. The policy has trapped itself between its own two rules.
For a faded rehearsal, try grow at 1 and shrink at 1/2 — a gap, but only a factor of two. The supplied observation is that doubling at α = 1 leaves α = 1/2, which is exactly the shrink threshold. Predict what the operation after a growth does, then run it, and say how far apart the thresholds have to be for the potential argument to have anything to release.
You should be able to state a growth and a shrink threshold and say what the load factor becomes immediately after each kind of resize, count rehashes and keys moved over a stated sequence, recognise thrashing from the rehash count rather than the total, and separate a measured average from the amortised bound the potential argument proves.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.