The model
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.
A concrete walk-through
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.
Costs and failure cases
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.
Check your understanding
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.