How do you get the expected number of empty shards when n keys are hashed uniformly across n shards?

## The technique: turn a count into a sum of indicators An **indicator variable** takes the value 1 when some condition holds and 0 otherwise. The trick that makes it useful is that its expected value *is* the probability of the condition, because `E[X] = 1 * P(condition) + 0 * P(not condition) = P(condition)`. So whenever the quantity you want is a **count of things that happened**, you can write it as a sum of indicators, one per candidate, and then read its expectation off as a sum of ordinary probabilities. The hard part of the original problem - how the candidates interact - is never entered. For `n` keys hashed uniformly into `n` shards: 1. Let `X_i = 1` when shard `i` receives no key at all. 2. The number of empty shards is `X_1 + X_2 + ... + X_n`. 3. `E[X_i] = P(shard i is empty)`, one probability about one shard. 4. The expected number of empty shards is the sum of those `n` probabilities. ## Computing the one probability A single key lands on shard `i` with probability `1/n`, so it misses with probability `1 - 1/n`. The `n` keys are hashed independently of one another, so all of them miss shard `i` with probability `(1 - 1/n)^n`. That expression is the classic approach to `1/e`: | n | (1 - 1/n)^n | Expected empty shards | |---|---|---| | 10 | 0.349 | 3.5 | | 100 | 0.366 | 36.6 | | 1,000 | 0.368 | 367.7 | | limit | 1/e = 0.3679 | 0.368n | So hashing a thousand keys into a thousand shards leaves roughly 368 shards untouched, and only about 632 shards occupied. Engineers who expect a near-perfect spread find this surprising, and it is exactly the sort of figure that decides whether a per-shard fixed cost is affordable. ## Why the sum is legitimate here The shard occupancies are plainly **not** independent: if you learn that shard 1 is empty, the `n` keys must be elsewhere, which makes every other shard slightly more likely to be occupied. Summing expectations is still exactly right. That is the whole appeal of the method - it needs each individual probability and nothing about how they relate, so a problem whose joint distribution is intractable collapses into `n` one-line calculations. The general form is worth carrying: for `m` keys into `n` shards, `P(a given shard is empty) = (1 - 1/n)^m`, roughly `e^(-m/n)`, giving `n * e^(-m/n)` empty shards. At `m = 2n` that is about `0.135n` - doubling the keys does not halve the empties, it cuts them by a factor of e. ## What the method does not give you This is the boundary an interviewer usually probes next. - **It gives an average, not a guarantee.** The expected count says nothing on its own about how far a particular run may sit from it. - **It does not give extremes.** The size of the *busiest* shard is not a sum of indicators, so no amount of linearity produces it. With `n` keys in `n` shards the average load is 1, while the maximum load is far larger - it grows roughly like `log n / log log n` - and a capacity plan built on the average will under-provision the hot shard badly. - **It does not survive a non-uniform hash.** Every term assumed `1/n` per key. If the key distribution concentrates, the per-shard probabilities differ and must be summed individually, which the method still supports, but the tidy `(1 - 1/n)^m` closed form does not. ## Where this shows up in practice - **Expected distinct shards touched** by a batch of lookups, which decides how many connections or round trips a fan-out costs. - **Expected number of occupied buckets** in a hashed structure, which drives memory sizing and decides whether a sparse layout is worth it. - **Expected probe count** in a lookup that retries on a hit, where each probe contributes one indicator. In every case the recipe is identical: name the candidate set, write the condition that makes one candidate count, compute that single probability, and multiply or sum. Reaching for the joint distribution first is the mistake the question is designed to catch.