Hashing makes every shard equally likely to receive a key, which is not the same as making every shard receive the same number of keys. The mean is exactly m/N and the maximum is whatever the stream produced, and the gap between them is the quantity a capacity plan has to be built on. This lesson measures that gap on a placement you can reproduce, and reseeds, because one placement is one sample of a distribution.
Core ideas
One hard idea, and it is a negative one: the property hashing gives you is about expectations, and a capacity plan is not built on expectations.
A good hash makes each of the N shards equally likely for each of the m keys. That is a statement about one key at a time. The counts that result are a random vector whose mean is m/N in every coordinate and whose maximum is above that mean essentially always — with 1 200 keys in 12 shards the fullest shard held 122 against a mean of 100.
max/mean = max · N / m, and all three of those are counts, so the imbalance is a fraction rather than a float: 122 × 12/1 200 = 61/50. There is nothing to approximate and nothing to model. The lab counts the occupancies and divides, which is why the figure it prints is the same figure you would get by counting the placement by hand.
Across seeds 7 through 14 with the same 1 200 keys and 12 shards, the fullest shard ran from 112 to 122 and max/mean averaged 1.170. Quoting the 1.220 from a single run as “the imbalance” treats one draw as a property of the scheme. The lesson is about the distribution of the maximum, and that only becomes visible when you move the seed.
The material
The placement, the two numbers that describe it, how the gap between them behaves as the load grows, and the one result here that this library states without proving.
Under hash partitioning the shard of a key k is h(k) mod N for a hash function h. Keys near each other in the original key space are scattered, so range scans become expensive and the placement stops depending on what the keys mean. The occupancy of a shard is the number of keys assigned to it, and its mean over the fleet is m/N whatever the hash does.
The claim under examination is the everyday one: that hashing spreads keys evenly. It spreads them uniformly at random, which is a different sentence. Uniform means no shard is favoured; it does not mean no shard is fuller, and the whole of this course's imbalance arithmetic lives in that distinction.
The placements here come from a seeded generator printed on the page, so “random” is reproducible: the stream is x → 16 807·x mod (2³¹ − 1), with the modulus prime on purpose. The generator used elsewhere on this library's paths has a modulus of 2³¹, and the low bits of such a stream are periodic — x mod 4 cycles 0, 1, 2, 3 for ever. Taking that stream modulo 8 or 16 fills the shards perfectly level, which would demonstrate the opposite of this lesson's claim. The constants are on the page so you can check which generator drew your placement.
Raise the load and max/mean improves: the same 12 shards with 12 000 keys came out at 1.046 and with 120 000 keys at 1.018. It is tempting to read that as the imbalance going away. It is not going away — it is being divided by a larger mean. The absolute excess over the mean went from 22 keys to 46 keys to 182 keys as the mean went from 100 to 1 000 to 10 000, which is growth like √mean rather than a constant.
That is why the lab prints the excess in units of √mean rather than as a percentage. Measured that way it stays a small number of order one — 2.20, 1.45, 1.82 on those three runs — instead of appearing to shrink. It is a noisy small number, and reseeding shows it moving between 1.20 and 2.20 on the default placement, which is the honest picture: a term of a fixed order of magnitude, not a constant.
Provision every shard for the mean and the fullest one is over its allocation by 22% on the default placement. Provision every shard for the fullest and 11 of the 12 are over-bought. The usable answer is neither: size for a maximum you have measured across several seeds — 1.170 on average and 1.220 at worst here — and treat the excess as a cost of hashing rather than as a defect to be engineered away.
When the number of keys equals the number of shards, the maximum occupancy is Θ(log n / log log n). That result is stated, not proved — not here and nowhere else in this library. Its proof needs Chernoff bounds, which the Algorithms path excludes from its own scope, so no lesson anywhere establishes it. What this lesson does is measure the maximum on placements you choose.
Two related quantities are computed exactly, and they are computed elsewhere. “Balls in Bins and the Birthday Bound”, on the Randomised Algorithms course of the Algorithms path, derives the expected number of colliding pairs as n(n − 1)/2m and the expected number of empty bins as m(1 − 1/m)ⁿ, both by linearity of expectation and both exact. Those are the expectations this lesson does not compute; the maximum is the thing it measures. The seeded generator itself is “Hashing and Pseudorandom Numbers” on the Discrete Mathematics path.
Keep the three statuses apart when you quote a figure from this course. The mean is exact. The maximum on a given placement is measured and reproducible. The growth rate of the maximum is stated. A design review that treats the third as though it had the standing of the first is the failure this paragraph exists to prevent.
Interactive
Measure max over mean on a seeded placement, then reseed and measure again
Method
The order matters: compute what is exact first, so that everything measured afterwards has something to be measured against.
m/N is exact and needs no placement. It is the number every later figure is a ratio to, and having it first stops a large maximum from looking alarming when it is ordinary.
max · N / m is max/mean as a fraction. Keep it as a fraction: 61/50 says more than 1.22 when you come to compare two placements, because you can see the counts it came from.
One placement is one draw. Record the maximum from each and take both the average and the worst you saw. Eight seeds on the default placement give an average max/mean of 1.170 and a worst of 1.220, and those are two different numbers for two different purposes.
Provisioning at the mean under-provisions the fullest shard by the excess. Quote the figure with its sample: “max/mean 1.17 on average over eight seeds, 1.22 at worst” is a defensible input to a capacity plan; “about 1.2” is not.
One placement measured exactly, and then the same key count spread over ten times as many shards, which is where the ratio misleads.
Ten times the shards made max/mean look much worse and did not really change the underlying quantity. That is the shape of the whole result: the excess tracks √mean, so shrinking the mean by spreading keys thinner makes the ratio deteriorate even though nothing about the hashing changed.
For a faded rehearsal, keep 12 shards and take the key count to 12 000. The supplied first move is the mean, which is 1 000. Predict whether max/mean will be closer to or further from 1 than it was at 1 200 keys, then read the fullest shard off the lab, compute max/mean and the excess in root-means, and say which of the two figures actually told you something about the hash. Reseed three times before you commit to an answer.
You should be able to compute the mean and max/mean from a placement, describe how the excess behaves as the mean grows, and say which of the figures on this page are exact, which are measured, and which are stated without proof.
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.