Equivalence Classes & Closure

## Two halves of one contract A grouping key is a value used to decide 'same customer' and to file the row under that decision. Any structure that buckets by a digest of the key relies on two separate promises, and interviewers probe them together because breaking either one produces the same symptom: a row that is in the structure and cannot be found. 1. **The equality check is an equivalence relation.** Reflexive — a key equals itself. Symmetric — if `a` equals `b` then `b` equals `a`. Transitive — if `a` equals `b` and `b` equals `c` then `a` equals `c`. 2. **The hash agrees with equality, in one direction.** Equal keys must produce the same hash. Unequal keys may produce the same hash, and inevitably will. ## Why equality itself must be an equivalence Lookup answers the question 'is there a stored key equal to this probe?', and a bucketed structure answers it by comparing the probe against *some* of the stored keys — the ones filed in the same bucket, in whatever order they sit there. That answer is only meaningful if 'equal to' partitions the key space into classes: - Break **symmetry** — the classic case is a case-folding key that considers itself equal to a plain text key but not the reverse — and the verdict depends on which value happens to be the probe and which the stored entry. Two structures built from the same rows then disagree. - Break **transitivity** — a key that compares 'close enough' rather than exactly — and membership depends on which stored key is compared first, which is an artefact of insertion order. - Break **reflexivity** — a key whose comparison short-circuits to false on an absent field — and the structure cannot find a row using the very key it was filed under. ## The one-way hash rule | Statement | Does the contract require it? | Why | |---|---|---| | Equal keys produce equal hashes | **Yes** | otherwise the probe is sent to a bucket that does not hold the entry, and the lookup misses a row that is present | | Unequal keys produce unequal hashes | **No** | the digest range is finite and the key space is not, so collisions are unavoidable by counting alone | | Equal hashes imply equal keys | **No** | a shared bucket only means 'compare these'; the equality check is still what decides | | The hash reads only fields equality reads | **Yes, in effect** | a digest that mixes in a field equality ignores can differ for two equal keys, which breaks the first row of this table | The asymmetry is the whole point: the digest is a **necessary** filter, not a **sufficient** one. It narrows the candidates; equality decides. A candidate who says 'different values must hash differently' has inverted the requirement into one no function can satisfy. ## Stability while the key is in use The contract is not only about a single comparison; it is about a comparison repeated over time. A stored key must keep answering the same way for as long as it is filed. Two ways teams break this: - **Mutating a compared field in place.** The entry keeps the bucket computed at insert time. A probe carrying the new value hashes elsewhere and finds nothing; a probe carrying the old value reaches the right bucket and then compares unequal against the mutated stored key. The row is unreachable by either value, re-inserting creates a duplicate, and a full scan still shows it — which is exactly the confusing signature that gets escalated. - **Letting the digest depend on something outside the key's own content.** Ecosystems differ here: some environments derive digests for text in a way that varies between processes, others do not. That is harmless inside one run and fatal the moment a digest is persisted or used to choose a shard, because the same key routes to different destinations on different machines. A durable partition key must be derived from the key's content by a specified function, not from whatever digest the runtime happens to hand you. ## Where this bites in a merge pipeline Grouping keys are usually small derived values: a normalized email, a normalized phone, a composite of a few cleaned fields. Two consequences follow from the contract rather than from any particular structure. First, normalization must happen **before** the key is built, not inside the comparison, so that equality stays a plain comparison of stored content. Second, the key should be treated as immutable once created — build a new key rather than editing a filed one — because immutability is the cheapest way to satisfy the stability clause and the only way that survives a later refactor by someone who has not read this contract.