Why must a hash function be deterministic, and what breaks when it mixes in state outside the key?

## What the table actually needs A hash function maps a key of arbitrary size to a fixed-width integer. A hash table then reduces that integer to a slot index — classically `index = h(key) mod m` for a table of `m` buckets — and stores the entry there. The crucial point is that a hash table has no search mechanism. A sorted structure can compare its way to an entry; a hash table cannot. It knows only one thing about where your entry lives: the number the hash function produced at insert time. Lookup, delete, and update all work by recomputing that number and going straight to the slot. Therefore the function must satisfy one absolute rule before anything else: > For the same key contents, the hash function returns the same value, every call, for as long as the entry is in the table. This is determinism. It is a *correctness* property, not a performance property. Break it and the table does not report an error — the entry is simply never found again, while continuing to consume a slot and to count toward the table's occupancy. Repeat the insert and you get a second copy of a key that already exists. This is the quietest failure mode in the whole structure. ## Where non-determinism sneaks in Candidates who have only ever used built-in hashes assume non-determinism is exotic. It is not. Real sources include: - **Folding in a counter or a clock reading.** Usually written by someone who has heard "a good hash looks random" and concluded that more randomness per call is better. - **Hashing identity rather than contents.** If the hash is derived from where an object sits in memory rather than from the bytes that define it, two separately constructed but structurally identical keys hash differently. Lookups by a freshly built key miss even though an equal key is stored. - **Hashing over an unordered inner collection by iteration order.** If a key contains a set-like member and the hash concatenates members in whatever order iteration produces, the hash changes when the internal layout changes. - **Reading uninitialised bytes.** Hashing a raw record including padding bytes that were never assigned gives different values for records that are logically equal. ## Determinism is not uniqueness, and not sufficiency Two confusions are worth naming explicitly. First, determinism does not mean collision-freedom. A hash compresses an unbounded key space into a fixed-width integer, so distinct keys *must* sometimes share a value — that is arithmetic, not a defect. The table handles it by keeping a set of colliding entries per slot and confirming the match with a full key comparison. Second, determinism alone does not make a hash usable. `h(key) = 0` never varies and never lies, yet every operation degrades to scanning a single bucket, so a table of n entries gives O(n) lookups. The full requirement is usually stated as three properties: **deterministic** (correctness), **uniform** (values spread across the output range so buckets fill evenly, which is what buys expected constant-time operations), and **cheap** (the hash runs on every single operation, so its cost sits on the critical path). ## How long must determinism hold? Within one running process, for the life of the table — that is what the table itself needs, and it is the answer expected in an interview. A stronger promise is needed the moment a hash value escapes memory: a fingerprint written to a file, a precomputed index shipped alongside data, a value compared against one produced by a different build. Built-in hashes generally make no guarantee of stability across library versions, and some runtimes deliberately vary them between processes. If you persist a hash value, pin the algorithm in code you control, write the constants down, and version them, so the value you stored last month still means the same thing today. Otherwise the stored values quietly stop matching after an upgrade — the same disappearing-entry failure, just spread across a release boundary.