Hashing, Search Keys and Collisions

17.1.1 PLAIN — in simple words#

1. A hash function follows a rule to turn an input into an output value. Deterministic means that the same input under the same rule produces the same output.
2. This can help choose a storage bucket or produce a compact fingerprint of bytes. The function does not understand whether the input represents an order, a photograph or a lie.
3. Different inputs can produce the same output when the output space is smaller than the possible input space. This is a collision, not necessarily a malfunction.
4. The meaning of “same input” must be explicit. Text with different encodings, newline conventions or invisible characters can have different bytes even when a screen looks similar.

17.1.2 PLAIN — a picture in your head#

1. Mira assigns folders to four trays using the remainder of the folder number divided by four. Folder 10 goes to tray 2; folder 14 also goes to tray 2.
2. The tray number is a routing clue, not the folder’s full identity.
3. Where the comparison breaks: practical hash functions mix input bits in more sophisticated ways, and cryptographic hashes have additional security goals. The remainder rule demonstrates determinism and collisions only.

17.1.3 PLAIN — a worked example#

1. Define the toy function h(k) = k mod 4 for non-negative integer keys. Then h(2)=2, h(6)=2, h(10)=2, while h(3)=3.
2. The outputs tell us which tray to inspect. They cannot tell us whether keys 2 and 6 are equal, because those different inputs deliberately share the same result.
3. For byte fingerprints, Python’s standard SHA-256 interface can compute a digest:

import hashlib
fingerprint = hashlib.sha256(b"abc").hexdigest()
print(fingerprint)

4. The expected hexadecimal digest is ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad. The code hashes the three bytes for abc, not a file containing those bytes plus a newline. [S99] [S100]

17.1.4 PLAIN — what is really happening inside#

1. A hash algorithm consumes a precisely represented input and computes an output according to fixed operations. Changing one input byte gives a different input to that algorithm, even if the application considers two records equivalent.
2. Encoding and framing therefore belong before hashing. Concatenating fields without boundaries can lose distinctions: ab followed by c and a followed by bc both produce abc.
3. A digest cannot restore distinctions erased before the hash function received the bytes. Length prefixes, explicit field names or a reviewed canonical encoding can preserve the intended boundaries.
4. A semantic equality policy may deliberately ignore some differences, such as harmless formatting. That policy must be defined separately; it is not supplied automatically by using a cryptographic function.

17.1.5 TECHNICAL — the engineer’s version#

1. A hash is a mapping from an input domain to an output space. Fixed-length digests cannot be injective over an unbounded input domain; the pigeonhole principle guarantees that some distinct inputs share an output.
2. SHA-256 produces a 256-bit digest under the Secure Hash Standard. Its security goals are different from the convenience goals of an ordinary in-memory bucket function. [S100]
3. Specify the algorithm identifier, input encoding, framing and any canonicalisation version when storing a digest intended for later verification. “Hash of the order” is underspecified when one implementation hashes pretty-printed JSON and another hashes a different byte representation.
4. Python’s hash() is not a portable persisted content digest. In particular, string and byte hashes use process-level randomisation, and the data model defines equality/hash relationships rather than a universal cross-process wire value. [S108]

17.1.6 WORDS — remember these#

1. Hash function: a rule making an organising or checking value — a deterministic mapping under specified parameters and input representation. Digest: a compact fingerprint of bytes — a fixed-length output of a hash algorithm, whose meaning depends on the exact input bytes and algorithm. Framing: make field boundaries unambiguous — an encoding convention that preserves where components begin, end and differ in type or length.

17.2.1 PLAIN — in simple words#

1. A bucket groups entries whose hash-based route leads to the same place. Several different keys may belong there.
2. Correct collision handling keeps enough information to distinguish those keys. A lookup checks the original key, not just the bucket number or shortened hash.
3. A collision is not the same as a duplicate key. Keys 2 and 6 collide under our toy function but remain separate keys. Inserting key 2 twice raises a different question: replace its value, reject the insertion or store several values?
4. Choose that duplicate-key policy explicitly. A hash table’s storage mechanics do not decide the business meaning of repeated requests.

17.2.2 PLAIN — a picture in your head#

1. Tray 2 contains folders numbered 2, 6 and 10. Dev searches inside the tray until he finds the exact folder number.
2. Putting every folder that shares a tray into one combined folder would destroy information. Throwing away later folders would be equally wrong.
3. Where the comparison breaks: implementations may use linked chains, arrays, probing or other layouts instead of a literal tray. Some do not store a separate container object for each bucket. The invariant is correct discrimination of keys, not a particular picture.

17.2.3 PLAIN — a worked example#

1. Insert (2, 'red'), (6, 'blue') and (10, 'green') into a toy table with four buckets. All three entries route to bucket 2.
2. Lookup 6 checks bucket 2 and compares keys: 2 is not 6; 6 is 6, so return blue. Lookup 14 visits the same bucket and returns not found after checking all three different keys.
3. If the implementation returned the first entry merely because the bucket matched, lookup 6 would incorrectly return red. This is an exact counterexample to treating hash equality as key equality.
4. A second insertion of key 6 with value navy needs a chosen policy. In our dictionary-style toy it replaces the value for key 6; it must not alter entries for keys 2 or 10.

17.2.4 PLAIN — what is really happening inside#

1. With separate chaining, a bucket points to a collection of entries that share the route. With open addressing, collisions lead to a defined sequence of alternative slots in one array.
2. Open-addressed deletion needs care. Turning a removed slot into an ordinary never-used slot can prematurely stop a later search for an entry placed farther along the same probe sequence.
3. Resizing changes routing when the number of buckets changes. Entries must be re-established under the new arrangement; copying only the bucket labels is not enough.
4. Equality comparison and hash computation must agree on the key contract. If two keys compare equal but route inconsistently, lookup can fail to find an existing equal key.

17.2.5 TECHNICAL — the engineer’s version#

1. Chaining and open addressing are collision-resolution strategies, not different definitions of equality. Expected constant-time hash-table operations require assumptions about distribution, load and the cost of hashing and comparing keys.
2. The load factor is entry count divided by bucket or slot capacity under the implementation’s convention. Higher load can increase chain lengths or probe lengths; acceptable thresholds depend on the design.
3. Python requires equal objects used as hashable keys to have equal hashes. Mutable equality-relevant state is incompatible with a stable key unless the type carefully preserves the required contract. [S108]
4. The chapter’s toy explicitly compares original keys. This establishes collision correctness for the exercised representation; it does not establish resistance to adversarial inputs or bounded latency for arbitrarily large keys.

17.2.6 WORDS — remember these#

1. Collision: different inputs share one hash result — equality of hash outputs without equality of original inputs. Load factor: how full the hash structure is — entries divided by the relevant bucket or slot count under a stated convention. Probe sequence: alternative places checked after a collision — a defined traversal of slots in an open-addressed hash table.

17.3.1 PLAIN — in simple words#

1. Hash tables are naturally suited to exact-key questions: “Is this order identifier present?” or “What value belongs to this key?”
2. A normal hash route does not preserve the original order of keys. Nearby order numbers can land in unrelated buckets. Asking for all keys between two numbers therefore needs another strategy or a broad examination.
3. The key’s equality rule matters. Are uppercase and lowercase identifiers different? Are two differently formatted timestamps the same instant? Decide before building the route.
4. A fast lookup can still answer the wrong question when the application chose the wrong key or ignored part of its scope.

17.3.2 PLAIN — a picture in your head#

1. The four trays group folders by a remainder, not by consecutive number ranges. Folder 3 and folder 4 go to different trays; folder 2 and folder 10 share one.
2. To list every folder numbered 5 through 12, Dev cannot simply start at one tray and stop at the next as he could with sorted shelves.
3. Where the comparison breaks: some programming-language dictionaries preserve insertion order for iteration. That is not sorted-key order and does not turn their hash lookup mechanism into a B-tree range index.

17.3.3 PLAIN — a worked example#

1. Suppose a new exercise tracks receipts by (branch_id, receipt_no). (BR-A,17) and (BR-B,17) must remain distinct keys even though the receipt number is equal.
2. Hashing only the number and comparing only that number would conflate them. Hashing the number alone but retaining and comparing the complete tuple could remain logically correct, yet might create unnecessary collisions.
3. The safest specification states both the complete key and its equality rule, then chooses a suitable hash representation of that key.
4. For a range such as receipts 10–20 within BR-A, an ordered composite structure may better match the question. A hash table can still answer by examining entries, but ordinary exact-key routing does not directly provide the ordered range.

17.3.4 PLAIN — what is really happening inside#

1. Hash lookup narrows the candidate region using a derived value, then performs equality checks. Ordered lookup narrows regions using comparison boundaries. These are different information structures.
2. If equality normalises case or Unicode representations, the hash path must respect that equality. Normalising only during final comparison while routing raw unequal representations can violate the equal-key contract.
3. Normalisation can also be wrong for the domain. Lowercasing an opaque case-sensitive token destroys distinctions. “Make matching easier” is not sufficient authority to merge identities.
4. Keep identifiers immutable when used as keys, or explicitly remove and reinsert entries under a changed key. A key that silently changes after insertion can become unreachable through the expected route.

17.3.5 TECHNICAL — the engineer’s version#

1. Hash access primarily supports equality semantics; ordinary hashing does not preserve total order or neighbourhoods. PostgreSQL’s hash index is equality-oriented and uses a lossy stored hash representation requiring rechecking of candidates. This differs from an in-memory language dictionary. [S101]
2. A hash function and an equality comparator form a joint contract. Equal keys must have compatible routing; unequal keys are allowed to collide and must remain distinguishable by the equality check. [S108]
3. Expected O(1) lookup is not an unconditional worst-case guarantee. It excludes neither long collision chains nor the cost of computing a hash over a long input. State the assumptions when discussing complexity.

17.3.6 WORDS — remember these#

1. Equality contract: the rule for deciding that two keys are the same — a domain-specific equivalence relation that hashing and comparison must respect. Expected complexity: cost under specified distribution assumptions — an average or probabilistic bound, not a guarantee for every input. Lossy index entry: a representation that does not retain all distinguishing information — an entry requiring rechecking against fuller data to establish a match.

17.4.1 PLAIN — in simple words#

1. A fast bucket function tries to spread ordinary keys usefully. A cryptographic hash additionally aims to make certain deliberate manipulations computationally infeasible under a defined security model.
2. A cryptographic digest can help detect that bytes differ from a trusted expected digest. It does not tell you that the bytes are truthful, safe to execute or written by a particular person.
3. If an attacker can replace both a file and the untrusted digest displayed beside it, comparing the two does not establish authenticity. The expected value needs a trustworthy origin.
4. Encryption, message authentication and password storage are different tasks. Calling all of them “hashing” hides important requirements.

17.4.2 PLAIN — a picture in your head#

1. A parcel’s recorded weight can reveal that it changed, but matching weight does not prove the contents or sender. A cryptographic digest is a far stronger byte fingerprint than weight, yet the question “who supplied the expected fingerprint?” remains.
2. A signed receipt or a message-authentication mechanism addresses a different relationship: who could have authorised or produced the evidence under the relevant key system.
3. Where the comparison breaks: cryptographic security is not based on physical weight or a tamper-evident sticker. It depends on precise algorithms, key handling, threat assumptions and computational limits. The analogy must not be used to design a new security protocol.

17.4.3 PLAIN — a worked example#

1. Mira stores a backup file and a SHA-256 digest in a separately controlled manifest. Later, recomputing the digest can detect a byte mismatch relative to that manifest.
2. A match supports “these bytes have this digest, consistent with the trusted recorded value,” subject to the algorithm’s security assumptions. It does not establish that the backup includes every required table or that restoration succeeds.
3. Copying the file and digest into the same publicly writable folder weakens the origin claim: someone able to replace both can create a new matching pair.
4. The recovery exercise in Chapter 31 therefore combines byte checks with a real isolated restore and business reconciliation. Each check answers a different question.

17.4.4 PLAIN — what is really happening inside#

1. Cryptographic hash goals include difficulty finding an input for a chosen digest, a different input matching a given input’s digest, or any pair of distinct inputs with the same digest. These are related but distinct attack goals.
2. An unkeyed digest has no secret. Anyone can calculate one for any bytes. Authenticity requires a trusted channel, a signature, a properly used message-authentication construction or another explicit source of trust.
3. A keyed message-authentication code verifies possession of a key under its protocol assumptions. It is not a public signature from a uniquely identified person when several parties share that key.
4. Ordinary fast hashes are also not complete password-storage systems. Password verification needs a purpose-designed, reviewed construction and appropriate operational controls; storing a bare general-purpose digest does not supply them.

17.4.5 TECHNICAL — the engineer’s version#

1. Distinguish preimage resistance, second-preimage resistance and collision resistance. A 256-bit output length is not a promise that every attack requires 2^256 work; generic collision reasoning has a different scale. [S100]
2. Verification must bind the algorithm, exact bytes and trusted expected value. A checksum can detect accidental corruption while offering no meaningful adversarial collision resistance. A cryptographic digest still requires provenance when used for authenticity.
3. Do not improvise a MAC by concatenating a secret and message and calling a hash function. Use a standard reviewed authentication construction and protocol. This book does not introduce a home-made cryptographic scheme.
4. A digest’s byte-level equality evidence does not replace semantic validation, malware analysis, access control, retention review or restore testing.

17.4.6 WORDS — remember these#

1. Preimage resistance: hard to work backwards from a digest — computational difficulty of finding an input producing a specified hash output. Collision resistance: hard to deliberately find two matching fingerprints — computational difficulty of finding distinct inputs with equal digests under the algorithm’s security assumptions. Message authentication code: a keyed check on a message — an integrity and authenticity mechanism for parties sharing a key, not automatically a public signature.

17.5.1 PLAIN — in simple words#

1. A hash table works well when keys spread across its available locations under the workload it actually receives. Poor distribution creates crowded regions and longer searches.
2. Uniform-looking ordinary data is not a guarantee against deliberately chosen inputs. A service accepting untrusted keys must consider resource limits and the hash design’s threat model.
3. Random-looking digests also do not eliminate collisions mathematically. A finite output space eventually forces repetition; the useful question is how likely or difficult a collision is at the relevant scale.
4. Probabilistic estimates need assumptions. State whether outputs are being modelled as independent and uniformly distributed, and do not present the model as a proof about every input source.

17.5.2 PLAIN — a picture in your head#

1. Four trays receive folder numbers ending in a pattern that always gives remainder two. The trays exist, but three remain empty while one becomes crowded.
2. Adding more trays without changing the relationship between inputs and routing may not solve the underlying concentration.
3. Where the comparison breaks: real hash designs can randomise or key their mixing, and resize policies change the structure. A simple remainder function is intentionally a counterexample, not a model of every language runtime’s protection.

17.5.3 PLAIN — a worked example#

1. For n independently uniform outputs in a space of size M, there are n(n-1)/2 distinct pairs. Each pair has collision probability 1/M. The expected number of colliding pairs is therefore n(n-1)/(2M).
2. This expectation is not itself always the probability of at least one collision. When the expectation is small, it approximates that probability; a common birthday approximation is 1 - exp(-n(n-1)/(2M)).
3. For 100,000 outputs in a 32-bit space, the expected colliding-pair count is about 1.164, and the birthday approximation gives an at-least-one-collision probability around 68.8 percent.
4. For one billion outputs in a 256-bit space, the small-probability pair estimate is about 4.32 × 10^-60. This is conditional mathematical reasoning under the uniform model, not a guarantee about a flawed implementation or compromised trust chain.
5. The lesson is not “a long digest makes every system safe.” A wrong encoding, missing key comparison or replaced manifest can break the application without requiring a cryptographic collision at all.

17.5.4 PLAIN — what is really happening inside#

1. Collision frequency and lookup cost depend on both the hash output and how the table maps that output into its present capacity. Bucket reduction, resizing and equality checks all matter.
2. Resource attacks can also use huge keys or huge numbers of distinct keys. A collision-resistant digest does not bound memory consumption or the cost of hashing gigabytes of input.
3. Bound accepted input size, operation counts and memory growth at the application boundary. These are operational protections, not replacements for a correct key contract.
4. Test distribution with representative skew and deliberately concentrated toy inputs. Keep security claims separate from ordinary benchmark results; a fast sample does not establish adversarial robustness.

17.5.5 TECHNICAL — the engineer’s version#

1. The birthday calculations are original derivations from a uniform finite-space model. Expected colliding pairs follow linearity of expectation; the exponential probability expression is an approximation, not an exact identity for arbitrary n and M.
2. Hash-table worst cases and cryptographic collision attacks are different analyses. A runtime may use keyed or randomised hashing to make predictable collision patterns harder, while still enforcing application-level resource limits. Python documents process randomisation for string and byte hashes. [S108]
3. A persisted partition or identity mapping needs stable, versioned behaviour. A deliberately process-randomised runtime hash is not suitable as an undocumented cross-process routing contract.

17.5.6 WORDS — remember these#

1. Birthday effect: collisions become plausible before the space is full — pair growth causes collision probability to rise around the square root of a uniform output-space size. Adversarial input: data chosen to exploit assumptions — inputs deliberately selected to cause incorrectness, excessive resource use or other unwanted behaviour. Uniform model: assume every output is equally likely — a mathematical distribution assumption whose applicability must be justified separately.

17.6.1 PLAIN — in simple words#

1. Storage systems use hashes for several jobs: locating a bucket, comparing content, choosing a partition and building summaries that rule out some unnecessary searches.
2. Each job needs a separate contract. A partition hash should route the same key consistently under the active mapping. A content digest should identify exact bytes under a named algorithm. Neither automatically proves a business record’s meaning.
3. Some structures deliberately permit false positives while avoiding false negatives under their own assumptions. They can tell the system “definitely not here” or “possibly here,” with a later exact check required.
4. These mechanisms save work by narrowing possibilities. They do not justify discarding the original identity or skipping required verification.

17.6.2 PLAIN — a picture in your head#

1. A warehouse guide can route a box to a building, a checklist can suggest whether a product might be inside, and a sealed manifest can identify an exact file of records. All are guides, but they answer different questions.
2. Treating “possibly present” as “definitely the right record” confuses a filter with an answer.
3. Where the comparison breaks: probabilistic filters and distributed routing have precise algorithms and update rules. The warehouse picture does not prove their error bounds, deletion support or behaviour during reconfiguration.

17.6.3 PLAIN — a worked example#

1. A toy membership summary has eight bits initially zero. For integer key k, set bit k mod 8. Inserting keys 1 and 9 sets the same bit, number 1.
2. Querying 3 finds bit 3 unset and can conclude that 3 was not inserted into this correctly maintained toy summary. Querying 17 finds bit 1 set and can only say “possibly present.” It must check the actual stored keys to reject the false positive.
3. Clearing bit 1 to remove key 1 would also erase the evidence for key 9. This simple bitset therefore does not support arbitrary deletion safely by just clearing the bit.
4. This is a deliberately simplified filter illustration, not a full Bloom-filter implementation or a claim about a production filter’s false-positive rate.

17.6.4 PLAIN — what is really happening inside#

1. Content-addressed storage names an object using a digest or related content identifier. The system must still define how objects are encoded, verified, authorised and retained.
2. Hash partitioning chooses a location from a key and a mapping. When the partition arrangement changes, existing and new readers need an explicit transition protocol; independently recomputing a different modulus can make records appear missing.
3. Hash joins build a hash structure on one input and probe it with another, still checking join keys and preserving the required multiplicity. They do not normalise away valid duplicates.
4. Sorted storage systems may use probabilistic membership filters to avoid reading runs that cannot contain a key. A positive result usually requires further search; a negative result is safe only under the filter’s maintained assumptions and versioned encoding.

17.6.5 TECHNICAL — the engineer’s version#

1. Separate hash-based routing, candidate generation, integrity checking and authentication. Their correctness and security requirements are not interchangeable.
2. A lossy database hash index rechecks candidate values; PostgreSQL documents this explicitly for its hash method. A hash join likewise requires equality verification and correct duplicate handling. [S101] [S65]
3. The toy bitset’s no-false-negative claim holds only for insert-only maintenance with the exact stated mapping and uncorrupted state. It does not survive arbitrary clearing, changed encodings or lost updates.
4. Chapters 29 and 35 return to filters and partitioning inside larger designs. Preserve the boundary learned here: a compact derived value helps navigate evidence but does not replace the evidence’s identity and meaning.

17.6.6 WORDS — remember these#

1. False positive: a possible match that is not actually present — a positive candidate result rejected by a later exact check. Content addressing: name bytes by a content-derived identifier — object identification based on a specified representation and digest scheme. Hash partitioning: choose a data region from a key’s hash — routing through a versioned mapping from derived values to partitions.