Why do hash tables that index by bit masking XOR a hash's high bits downward?
answer
- which bits does the mask keep?
- where does entropy sit in composed keys?
- two hashes differing only above the mask
- one shift, one XOR, cheap on purpose
- it moves entropy, it cannot create it
basics
~20 sA power-of-two mask reads only the low bits, so hashes differing solely up high would collide every time. XOR-ing the high half down folds that entropy into the bits the mask reads, for one shift and one XOR.
solid answer
~50 sBecause the index step throws most of the hash away. With a power-of-two capacity the table keeps only the low bits, so two keys whose hashes differ only above the mask width land in the same slot every time — and that pattern is common, because real keys often pack a tag, a scope id or an aligned address into one end of the value. XOR-ing the high half into the low half mixes that entropy into the bits the mask reads, at the price of a shift and an XOR. It is deliberately cheap damage control, not a hash function: it cannot invent entropy, so keys that already share a full hash still collide, and a hash that clusters everywhere stays clustered. Tables that index with a remainder skip the step, because a remainder already blends every bit.
code
pseudocode · 12 lines// capacity is a power of two; the mask keeps only low bits
mask = capacity - 1 // capacity 16 -> mask = 0x0F
h = hash(key) // a 32-bit value
h = h XOR (h >> 16) // fold the high half down
index = h AND mask
// scope-tagged identifiers put the entropy up high:
// hash(a) = 0x0003_0007
// hash(b) = 0x0004_0007
// without the fold: both index to slot 7
// with the fold: 0x0007 XOR 0x0003 -> slot 4
// 0x0007 XOR 0x0004 -> slot 3go deeper
Recall that the table uses only part of the hash to choose a slot, and that mixing high bits downward is a cheap step so that keys differing only high up do not pile into one slot.
Explain the mechanics: how wide the mask is, which bits survive it, what one shift and one XOR buy, and why the step is pointless when the index comes from a remainder.
Be ready to diagnose the failure it guards against — probe or bucket-length histograms skewed while the load factor looks healthy — and to say when you would replace the fold with a stronger finalizer.
Own the contract with key authors. A masked engine silently depends on hash quality it does not control; decide whether you spend instructions per lookup defending against that, or push the requirement onto every key type and enforce it.
## The mask is a lossy filter Indexing by mask means `index = hash AND (capacity - 1)`. For a table of 1024 slots that is ten bits. A hash is typically 32 or 64 bits wide. The index step therefore discards 22 or 54 bits of whatever the hash computed — and it discards the *same* bits for every key, deterministically. Any structure that lives in the discarded region is invisible to the table. That sounds like a corner case until you look at how real hashes are built. Consider a symbol table inside an interpreter, keyed by identifiers that are qualified by the scope they were declared in. A tempting way to hash such a key is to combine the scope id and the name hash by shifting one into the upper half of the word. Every identifier in the program now differs from its namesakes only in bits the mask never reads: a small table sees one slot per identifier name, with every scope's copy piled into it. Similar shapes appear whenever keys are composed rather than opaque — record ids built as `region << 20 | sequence`, memory addresses whose low bits are zero because of alignment, timestamps with a constant epoch offset in the high bits, packed enum-plus-counter values. ## What the fold does The standard remedy is one line before the mask: XOR the top half of the hash into the bottom half. Each bit of the low half becomes the parity of two originally independent bits, so information that lived only above the mask is now visible below it. Work the trace in the fragment attached to this question. With capacity 16 the mask keeps four bits. Two keys hash to `0x0003_0007` and `0x0004_0007`. Their low nibbles are both 7, so unfolded they land in slot 7 together, every time, forever. After `h = h XOR (h >> 16)` the low halves become `0x0007 XOR 0x0003 = 0x0004` and `0x0007 XOR 0x0004 = 0x0003`, so the keys index to slots 4 and 3. The high-order difference has been made visible to a filter that could not otherwise see it. ## What the fold does not do This is where candidates over-claim, and where the interviewer is listening. - **It does not add entropy.** XOR is a permutation of the bit pattern, not a source of information. If a hash function maps a thousand distinct keys onto ten distinct values, folding produces ten distinct values still. The fold redistributes; it cannot create. - **It does not rescue equal hashes.** Two keys with identical hashes are identical after any deterministic mixing. They will collide, and only collision resolution and key comparison save you. - **It does not make a bad hash good.** A finalizer strong enough to guarantee avalanche behaviour costs several multiplies and shifts. One shift and one XOR is chosen precisely because it is nearly free on the critical path — it is insurance against the most common accident, not a cryptographic-grade mixer. - **It does not help remainder-indexed tables.** A remainder by a prime already involves every bit of the input, so the fold buys nothing there and merely costs instructions. ## Choosing the shift distance The shift is usually half the hash width — 16 for a 32-bit hash, 32 for a 64-bit one — because that maximises how much of the untouched region gets folded into the region the mask reads, with one operation. Shifting by less leaves the top bits still unread on a small table; shifting by more folds only a sliver. Some designs fold twice, or fold and then multiply, trading a couple more instructions for better mixing. All of these are points on one dial: instructions per operation versus tolerance of structured hashes. Runtimes make different calls on where that mixing happens. Java's hash map folds the top half of a key's hash down before masking, while Python's dictionary leaves the hash value alone and instead perturbs the *probe sequence* with the bits the initial index ignored, so unread high bits still influence where a colliding key ends up. Same problem, two placements of the fix. ## Diagnosing the failure it prevents When the fold is missing (or the hash is pathological anyway), the symptom is distinctive: lookup cost climbs while the load factor looks perfectly healthy. Occupancy says the table is half full; probe counts or bucket lengths say a handful of slots hold most of the entries. The useful instrumentation is a histogram of bucket lengths or of probes per lookup, not the load factor. The fix is upstream — a better hash for that key type — with the fold being only the engine's cheap first line of defence. ## How to answer at interview Say what the mask discards, name a key shape whose entropy lives there, describe the fold in one sentence, and then volunteer the limits — no new entropy, no rescue for equal hashes, useless for remainder indexing. The limits are the part that separates a memorised answer from an understood one.
- Give a key shape where the fold changes nothing at all.Two kinds. First, keys whose hashes are already well distributed — a strong mixing hash leaves entropy in every bit, so folding neither helps nor hurts beyond its two instructions. Second, keys whose hashes are outright equal: XOR is deterministic, so identical inputs stay identical and the collision survives. The fold only helps when real differences are sitting above the mask.
- Why fold rather than run a proper mixing function on every hash?Cost on the critical path. A shift and an XOR are close to free next to the memory access the lookup is about to make; a strong finalizer is several multiplies and shifts, which can rival the rest of the operation on small tables with cached keys. Engines that already demand high-quality hashes from key types skip the fold entirely.
- How would you spot a table suffering from unspread hashes in production?Lookup latency rises with table size while the load factor stays normal — the giveaway that occupancy is fine but distribution is not. Instrument probes per lookup, or dump a histogram of bucket lengths: a healthy table shows a tight distribution around one, a skewed one shows a few slots holding most entries. Then fix the key type's hash.
saying these in an interview costs you the question
- Says the fold makes any hash function good enough
- Thinks XOR-ing bits adds entropy to the hash
- Believes spreading separates keys with equal hashes
- Claims remainder-indexed tables need the same fold
- Assumes real-world hashes always have uniform low bits