Use a table with 8 slots holding eve in slot 4 and bob in slot 5. Insert amy, whose hash maps to slot 5. A hash function picks the candidate slot; equality on the stored key decides the result.
1. Compute a hash from the key
Hash amy to a number such as 96,717. The value depends only on the key's bytes, so the same key always hashes the same way, and different keys may still collide.
2. Select a bucket or slot
With capacity 8, mask the hash: 96717 & 7 = 5. Slot 5 is amy's home, but it already holds bob. The table must not overwrite; it must resolve the collision.
3. Check key equality
Compare bob with amy: different keys, so this entry is not a match. Equal hashes would not prove equality either, which is why the table always compares the original keys.
4. Resolve collisions or resize
With linear probing, step to slot 6. It is empty, so store amy there. Two entries now sit past their home slots, lengthening future probes. When the load factor, entries divided by slots, passes about 0.75, the table doubles to 16 slots and rehashes every entry, because slot positions depend on capacity.
5. Return the value or absence
A later lookup for amy repeats the walk: hash to slot 5, find bob, compare unequal, probe slot 6, compare equal, return the value. A lookup for a missing key stops at the first empty slot. For the full contract, continue with Hash Tables.
Hardware, runtime, and observability notes
When tracing Trace Inserting amy Where Slot 5 Is Taken in a live production environment (subsystem: memory, primary layer: runtime), keep the following step-level cost model and diagnostic checklist in mind:
- Step 1 (runtime): Compute a hash from the key — verifies state invariants before advancing the execution pointer.
- Step 2 (runtime): Select a bucket or slot — verifies state invariants before advancing the execution pointer.
- Step 3 (runtime): Check key equality — verifies state invariants before advancing the execution pointer.
- Step 4 (runtime): Resolve collisions or resize — verifies state invariants before advancing the execution pointer.
- Step 5 (runtime): Return the value or absence — verifies state invariants before advancing the execution pointer.
Every transition across the runtime boundary carries both a direct CPU/memory cost (cache-line fills, descriptor lookups, lock acquisitions, or context switches) and a tail-latency queueing risk under contention. To verify this trace on your own service, capture latency histograms and hardware/kernel counters across each step boundary, compare cold-cache versus warm-cache execution paths, and confirm that error or timeout branches release all acquired descriptors, locks, and buffers cleanly.