Which hash-function property keeps near-identical keys like ORD-1041 and ORD-1042 out of one bucket region?
answer
- similar keys, similar hashes, similar buckets
- think about the image of the real key set
- one input bit changing should change many output bits
- a character sum ignores position entirely
- about half the output bits should flip
basics
~20 sThe avalanche property: changing one bit of the key should flip about half the output bits, so structured keys land in unrelated places. Without it, a family of similar keys maps into a narrow band of hash values and fills only a handful of buckets.
solid answer
~50 sThe property is **avalanche**: a single-bit change in the key should flip roughly half the output bits, independently of which bit changed. Real key sets are not random — order identifiers share a prefix, differ in one or two characters, and run sequentially. A weak hash preserves that structure. Summing character codes, for example, maps every identifier of that shape into a band a few hundred wide, so no matter how large the table is, only a few hundred buckets are ever touched and every other slot stays empty. Worse, a sum is order-insensitive, so `ORD-1041` and `ORD-1014` collide exactly. Distinct hash values are not the bar — the *image* of your real key set has to be spread across the whole output range, which is what avalanche delivers by destroying input structure rather than carrying it through.
go deeper
Know that similar keys must not produce similar hashes, and be able to say why summing characters is a bad hash: reorderings collide outright and all keys of one shape crowd into a narrow range.
Explain avalanche precisely — one input bit flipped should flip about half the output bits — and connect it to bucket occupancy through the reduction step. Be ready to describe how you would measure it on real keys.
Diagnose the lopsided-table symptom in production: even lookups, uneven latency, and a hot bucket. Show that you check the specific bits feeding the index rather than eyeballing whole hash values, and that you sample real keys rather than random ones.
Frame it as a risk that scales with the data, not a code defect. Decide when a candidate hash must be validated against production key samples before adoption, and who re-validates when a new key format or data source arrives.
## Uniformity is a claim about your keys, not about all keys A hash function's job after determinism is to make bucket occupancy even. The theoretical statement of simple uniform hashing says each key is equally likely to land in each of the `m` buckets. But you do not get to choose the keys — the application does, and applications generate deeply structured keys: sequential order identifiers, timestamps, identifiers sharing a fixed prefix, paths differing in one segment. So the practical requirement is stronger than "produces a wide range of values in principle". It is: **on the key set this table will actually see, the hash values must be spread across the whole output range.** A function can be perfectly injective and still be terrible, if the image of your real keys occupies a sliver of the range. ## The narrow-image failure Take identifiers of the form `ORD-1041`, `ORD-1042`, `ORD-1043`, and a hash that sums character codes. Every identifier of that shape has the same prefix and eight characters, so the sums differ only by the small variation in the four digits — the entire key set maps into a band a few hundred values wide. Now reduce to a bucket index with `h mod m`. If `m` is larger than that band, only a few hundred buckets can ever be occupied and every other slot is dead memory; if `m` is smaller, keys pile up in a way that has nothing to do with how many keys there are. Either way, growing the table does not help, because the problem is not the reduction step — it is that the hash never used the output range in the first place. The same function has a second defect: a sum ignores position, so `ORD-1041`, `ORD-1014` and `ORD-4011` produce *identical* hashes. These are not near misses, they are exact collisions among keys the business generates constantly. ## What avalanche means precisely Avalanche is the property that flipping any single input bit flips each output bit with probability about one half, and does so independently. Two consequences follow: 1. Keys differing in one character produce hash values with no visible relationship — not adjacent, not offset by a constant, just unrelated. 2. Structure in the input (a shared prefix, a monotone counter, a fixed length) is destroyed rather than carried through to the output. A useful mental check is: if I hand you `h(ORD-1041)`, can you guess anything about `h(ORD-1042)`? Under a good hash the answer is no. Under a character sum the answer is "it is exactly one larger". Measuring it is straightforward and worth mentioning in an interview: hash a large sample of real keys, flip one bit at a time, and count how many output bits change. A function averaging far below half has no avalanche. ## Where the entropy sits in the output Avalanche also has to hold across *all* output bits, and that is where a subtle failure lives. A multiplicative scheme that multiplies the key by a large constant and keeps the product's width pushes most of the mixing upward: the high bits depend on the whole key, while the lowest bits depend on very little, because multiplication only ever propagates carries from low positions to high ones. An engineer who benchmarks such a hash sees output values that look wonderfully varied and concludes it is fine. Then a table that derives its index from the bottom few bits of the value indexes on exactly the part of the output that barely varies — and the keys pile into a handful of buckets while the measured hash values still look random. The lesson is that "the hash values differ" is the wrong measurement; what matters is that the bits *the index is derived from* differ. ## Why the interviewer cares The consequence of poor spread is a shape change in cost. With even occupancy, the expected number of comparisons per lookup is a small constant tied to the load factor. With a heavily skewed distribution, the occupied buckets hold long chains of entries and lookups inside them cost time proportional to the chain length; if the reduction fills a contiguous run of neighbouring slots, schemes that scan neighbouring slots on collision suffer even more, since one dense region slows every probe that enters it. The table still returns correct answers, so nothing alerts — it just stops being a constant-time structure, and does so under exactly the workload that generates the most keys.
- Are distinct hash values for distinct keys enough to guarantee even bucket occupancy?No. Injectivity says nothing about spread. Sequential identifiers hashed to a band of a few hundred consecutive values are all distinct, yet they occupy a few hundred buckets no matter how big the table is. The requirement is that the values of your real keys cover the output range, which is what avalanche produces.
- How would you actually test a candidate hash function before adopting it?Two measurements on real keys, not synthetic ones. First, an avalanche test: flip single input bits and count output-bit changes, expecting about half. Second, a distribution test: hash a large production key sample, reduce to the intended number of buckets, and inspect the occupancy histogram for empty regions and outsized buckets.
- A hash produces widely varying values but the table is still lopsided. What do you check first?Which bits the index is derived from. Some mixing schemes concentrate entropy in the high output bits and leave the low bits nearly constant, so a value that looks random overall carries almost no variation in the part the index actually reads. Measure the variation in those specific bits, not in the value as a whole.
A good hash behaves like a thorough shuffle: two decks differing by one swapped card come out with no resemblance. A weak hash is a single cut — the original order survives, just rotated.
saying these in an interview costs you the question
- Says any function that mixes the input spreads keys fine
- Believes distinct hash values imply even bucket occupancy
- Thinks a bigger table fixes a narrow hash image
- Treats a character sum as an acceptable string hash
- Confuses avalanche with speed or with collision-freedom