In a hash index, what happens when two different key values map to the same bucket, and what does the index do when a bucket runs out of space?
answer
- collision is normal, comparison decides
- chaining = cheap writes, longer probes
- linear / extendible hashing = incremental splits
- load factor drives chain length
- duplicate-heavy keys: splitting cannot help
basics
~20 sColliding keys simply share a bucket; the engine stores both and resolves it by comparing actual keys on read. When a bucket fills it chains an overflow page, or the index splits buckets to spread entries. Long chains turn constant-cost probes into linear scans.
solid answer
~50 sCollisions are normal, not an error. Any hash maps a huge key space onto a small bucket space, so distinct keys share buckets by design. The index stores every colliding entry in that bucket and the reader disambiguates by comparing the real key values — which is why a hash index always needs the key (or a row fetch) to confirm a match. When a bucket is full there are two families of answer. **Overflow chaining**: link an extra page to the bucket and keep appending. Cheap to write, but the probe now walks the chain, so cost degrades from one page read toward linear. **Splitting**: dynamic schemes such as linear hashing or extendible hashing add buckets incrementally, rehashing a small slice of entries so the average chain stays near one page. The failure mode to name in an interview is skew: a low-cardinality or heavily duplicated key concentrates entries into a few buckets, splitting cannot help because the entries genuinely share a hash, and the index degenerates.
go deeper
Know that collisions are expected, both keys live in the same bucket, and the engine compares real keys to pick the right one.
Add overflow chaining versus splitting, what load factor means, and why long chains erode the constant-cost promise.
Talk about diagnosis — index reads per probe, rebuild versus redesign — and why skewed or low-cardinality keys are the wrong candidates for hashing.
Frame it as a distribution assumption baked into the access method: the structure's performance contract holds only while key cardinality and skew stay within the assumed envelope, so it needs monitoring or a different design.
## Two different things are both called "collision" It is worth separating them: 1. **Bucket collision** — two distinct keys reduce to the same bucket number, e.g. because `h(a) mod N == h(b) mod N` even though `h(a) != h(b)`. This is overwhelmingly common: with `N` buckets and far more distinct keys, it is guaranteed. 2. **Hash-value collision** — two distinct keys produce the identical hash output. Rare with a wide hash, but possible, and it matters for indexes that store only the hash rather than the key. Both are resolved the same way at read time: compare the actual key values. If the index stores full keys, the comparison happens inside the index; if it stores only hashes to keep entries small, the engine must fetch the candidate rows and compare there, paying extra I/O for false candidates. Either way, a hash match is a *candidate*, never a proof. Duplicate keys are a third case and not a collision at all — many rows legitimately share one key value, and they land in the same bucket by definition. ## Handling a full bucket: chaining The simplest scheme is **overflow chaining** (separate chaining). Each bucket is a page; when it fills, allocate another page and link it. Inserts stay cheap. Reads must now walk the chain, testing every entry, so a bucket with a five-page chain costs five page reads instead of one. As chains grow the structure slides from constant-cost toward linear scanning of a slice of the index, which is precisely the property that justified choosing hash in the first place. Chains also complicate deletes: removing entries leaves holes, and space is not reclaimed until the chain is compacted or the index is rebuilt. ## Handling a full bucket: splitting Static hashing fixes the bucket count at build time, so growth is absorbed entirely by chains — acceptable only if the data size is known and stable. Real engines use **dynamic hashing**: - **Linear hashing** grows the bucket array one bucket at a time in a fixed round-robin order, using two hash functions during the transition (one for already-split buckets, one for the rest). No global rebuild; growth is incremental and cheap. - **Extendible hashing** keeps a directory indexed by the top `d` bits of the hash. Splitting one bucket increments that bucket's local depth and, only when necessary, doubles the directory. Lookups stay two accesses — directory then bucket. Both keep the average chain near one page as the table grows, at the cost of extra bookkeeping and, during splits, extra writes. ## Load factor The knob behind all of this is the **load factor**: entries divided by capacity. Low load factor wastes space; high load factor lengthens chains and probes. Engines target a fill ratio and split when it is exceeded. If an index is bulk-loaded and then grows heavily, expect degradation until splits catch up — which is one reason a hash index can look excellent in a benchmark and mediocre months later. ## The failure mode that matters: skew Splitting redistributes entries by *hash value*. If the skew comes from genuinely duplicated key values — a status column with three values, a tenant column where one tenant owns most rows — every duplicate shares the same hash and therefore the same bucket no matter how many times you split. You end up with a handful of enormous overflow chains and a structure that answers the common value by scanning a long chain and then fetching a huge number of rows. The practical rule follows: hash indexes want high-cardinality, evenly distributed keys — identifiers, emails, tokens, content hashes. Low-cardinality columns are the wrong candidates, and for the frequent values a full table scan usually wins anyway. ## Adversarial input One more consideration for user-controlled keys: if the hash function is predictable, a caller can craft many values that land in one bucket and turn probes into linear scans. Engines mitigate with strong or seeded hash functions. It is a rare question, but naming it signals depth. ## What to say in an interview Collisions are expected and resolved by key comparison; full buckets are handled by chaining and, in modern engines, by incremental splitting; the metric to watch is load factor and average chain length; and the structural weakness is duplicate-heavy or skewed keys, which splitting cannot fix.
- If the index stores only the hash of the key rather than the key itself, what changes?Entries become small and fixed-width, which is attractive for long keys such as URLs, and more entries fit per page. But the index can no longer confirm equality on its own: every hash match becomes a candidate row that must be fetched and compared, so false candidates cost real I/O. It also means the index can never be used to answer a query from the index alone.
- How would you notice a degraded hash index in production?Equality lookups that used to be flat start scaling with table size or with the popularity of the key value, and index reads per lookup climb well above one page. That points at long overflow chains — either the load factor has outgrown the bucket count or the key distribution is skewed. The fix is a rebuild if it is load factor, and a different index or a different key if it is skew.
saying these in an interview costs you the question
- Treating a collision as an error or data-corruption condition
- Believing a good hash function eliminates collisions entirely
- Assuming bucket splitting fixes skew caused by duplicated key values
- Saying probes stay O(1) no matter how long the overflow chain grows
- Thinking deletes automatically reclaim overflow pages