What does the simple uniform hashing assumption claim, and when do real keys violate it?

## The assumption, stated exactly Simple uniform hashing (SUHA) is the modelling assumption behind essentially every hash-table cost claim you will be asked to state. It says: for a table with `m` buckets, each key that gets stored is equally likely to hash to any one of the `m` buckets, and keys' bucket choices are independent of each other. It is an assumption about a *probability model*, not a claim you can verify by looking at a table. From it the standard results follow. With separate chaining and `n` entries, the expected number of entries in the bucket you probe is the load factor `alpha = n/m`, so an unsuccessful search costs `Theta(1 + alpha)` expected and a successful one the same order. Keep `alpha` bounded by a growth policy and both are expected O(1). Under the same assumption, when `n` keys go into `n` buckets the *longest* chain is not constant — it is `Theta(log n / log log n)` in expectation. Even the ideal model produces buckets several times the average, which is a useful thing to know before you go looking for a bug. ## Who supplies the uniformity The most common misreading is that SUHA is a hope about your data — that it holds if your keys "look random" and fails if they look structured. That is backwards in practice. Real keys are almost never uniform: region codes share prefixes, identifiers are sequential, timestamps are dense, paths repeat directory segments. The job of a hash function is to destroy that structure. A function with good avalanche behaviour — where flipping one input bit changes about half the output bits — maps a structured key set to output values that behave, for indexing purposes, like uniform ones. So the assumption is a property of the *pair* (key set, hash-and-index pipeline), and the pipeline is the part you control. ## How it actually fails Three realistic failure shapes, none of which needs an attacker: 1. **The index derivation throws away the mixed bits.** Tables sized as a power of two typically take the index from the low bits of the hash. If the hash function preserves input structure in the high bits and the keys differ mainly there, all that entropy is masked off. This is why implementations add a finalisation step that folds high bits down into low ones before masking, and why prime-sized tables using a modulus are more forgiving of a mediocre hash. 2. **The hash ignores part of the key.** A hash that samples only a prefix or only a bounded number of characters will collide every key sharing that prefix — a genuine hazard for keys like hierarchical region or postal codes, where a five-character code's first two characters name the region and thousands of codes share them. 3. **A cheap, near-identity hash on numeric keys.** Using the raw numeric value as the hash is fine when values are dense and the table is prime-sized, and terrible when the values are multiples of a stride that shares a factor with the table size, which lands them all on a fraction of the buckets. Mainstream runtimes hedge this differently for the same reason: Java's hash map folds a value's high bits into its low bits before masking, while Python's dict leaves the value alone and instead perturbs the probe sequence with the unmasked bits, so displaced keys stop marching in lockstep. Two routes, one goal — make the index depend on the whole hash. ## The distinction candidates miss: frequency is not collision If a table keyed by region code receives a million records for the same dense metro code, that is **not** a collision problem. A map stores one entry per distinct key; the millionth insert of the same key overwrites or updates the entry it already has. Neither the entry count, the load factor, nor any chain grows. Skewed *access* frequency is a cache and contention story, not a hashing one. What matters for SUHA is how the **distinct** keys distribute — so the question to ask about the region-code table is how many distinct codes exist and whether the pipeline scatters them, not how popular any one of them is. ## What to do about it Diagnose by measuring, not by guessing: sample the bucket-occupancy distribution and compare it with the model. Under SUHA at `alpha` near one, most buckets hold zero to a few entries and the maximum sits near `log n / log log n`. A distribution with a handful of buckets holding orders of magnitude more, and vast empty stretches, points at the hash or at the index derivation — not at bad luck. The fixes are of a piece: mix the whole key, fold the high bits into the index, and choose a table size that does not collude with the keys' stride.