Interview prompt
Explain hash tables: from keys to buckets to an engineer who understands the surrounding system but has not used this technique. Walk from its contract to a concrete operation, then discuss where it fails or becomes expensive.
A strong answer
A hash table transforms a key into a hash value and uses part of that value to select a bucket or slot. The table then checks key equality because hashes can collide: equal hashes do not prove equal keys. Correctness therefore depends on both a stable hash/equality contract and collision handling.
With separate chaining, each bucket holds a collection of entries. With open addressing, collisions probe other slots according to a rule. As occupancy rises, probe sequences or bucket chains tend to grow, so implementations resize around a chosen load factor. Resizing reassigns entries because bucket positions depend on table capacity.
A complete answer also calls out the assumptions that control correctness. Expected constant-time lookup relies on assumptions about hash distribution and workload; adversarial keys can create long chains or probe clusters. Mutable keys are dangerous when their hash changes after insertion. Hash tables also do not inherently preserve sorted order and may use more memory than a compact array.
Close by describing one representative test or measurement. Explain why a map must compare the original key after a hash match. Then describe what goes wrong if a key object changes a field used by its hash after insertion.
Follow-up questions
Answer the follow-ups in the frontmatter. Use the linked article for the concept and the trace to make the explanation concrete.