A service truncates each key's digest to 32 bits as a fingerprint; why are collisions eventually unavoidable?
answer
- count the values, not the function
- the target space is finite
- no one-to-one map into fewer slots
- k bits gives 2^k fingerprints
- forced at 2^k plus one distinct keys
basics
~20 sA 32-bit fingerprint has only 2^32 possible values, so any 2^32 + 1 distinct keys must contain two that share one. That is the pigeonhole principle; a better function cannot avoid it, only a wider field delays it.
solid answer
~40 sFingerprinting maps keys into a finite set of values, and 32 bits gives exactly 2^32 = 4,294,967,296 of them. The pigeonhole principle says no one-to-one map exists from a larger finite set into a smaller one, so once the number of distinct keys passes 2^32, at least two of them land on the same fingerprint. Nothing about the function changes this: uniformity, cryptographic strength and cost all affect *where* collisions land and how hard they are to produce deliberately, but none of them adds values to a 32-bit field. The practical consequence is that a fingerprint match is a filter, never a decision — confirm it with a full comparison of the underlying keys. Widening the field raises the threshold, since each extra bit doubles the space, but never removes it.
go deeper
Recall the shape of the argument: k bits means 2^k possible values, and more distinct keys than values forces a repeat. Name the pigeonhole principle and give the threshold for the width in the question.
Explain that the conclusion rests on the two counts alone, so no property of the function alters it, and that each extra bit doubles the value space and therefore doubles the threshold.
Show the operational consequence: a fingerprint match gates a full comparison, deduplication on fingerprints alone loses records, and width is chosen against the lifetime distinct-key count rather than today's volume.
Frame it as a design constraint rather than a defect. Because no function removes the case, the system owes an explicit answer for what happens on a collision, and the width choice is a cost trade against that answer.
## The setting A **fingerprint** here is a fixed-width value computed from a key and stored in place of it: a routing tag, a dedupe marker, a cheap pre-filter in front of an expensive comparison. Suppose the field is 32 bits wide and a stream of distinct keys is fingerprinted into it. The interesting question is not whether the function is any good. It is how many distinct values the field can hold at all. Thirty-two bits hold exactly `2^32 = 4,294,967,296` distinct patterns. The keys form one set, the fingerprints another, and the function is a map from the first into the second. The **pigeonhole principle** states that if a finite set of size N is mapped into a set of size M with N greater than M, then some target value receives at least two sources; equivalently, **no injective (one-to-one) map exists from a larger finite set into a smaller one**. Take N to be the number of distinct keys and M to be 2^32, and the conclusion is immediate: past 4,294,967,296 distinct keys, two of them share a fingerprint. This is arithmetic about two counts, not a claim about any particular function. ## Why the function is irrelevant to the threshold Engineers reach instinctively for the function when they hear *collision*, and that instinct is misplaced for this claim. What the function controls is how much **sooner than the threshold** collisions appear in practice, and how hard it is for someone to manufacture one on purpose. What it cannot control is the size of the output space. A perfectly uniform function and a badly skewed one have the same forced threshold, because the threshold is set by the width alone. The negative direction of the map is the one that stays sound: because the function is deterministic, **equal keys always produce equal fingerprints**, so *different fingerprints prove different keys*. Only the positive direction — equal fingerprints — carries no conclusion. ## Width and threshold | Fingerprint width | Distinct values | Distinct keys that force a repeat | |---|---|---| | 16 bits | 65,536 | 65,537 | | 24 bits | 16,777,216 | 16,777,217 | | 32 bits | 4,294,967,296 | 4,294,967,297 | | 64 bits | about 1.8 x 10^19 | one more than that | Each bit dropped halves the space, so truncation is not a small economy. Taking the leading 32 bits of a 256-bit digest is a reduction of the value space by a factor of 2^224, and the point at which a repeat is forced falls by the same factor. ## What follows for the code around it - **A fingerprint match gates a comparison, it does not replace one.** Where equality matters, the match selects candidates and a full comparison of the keys decides. - **Deduplication keyed on fingerprints alone silently loses data.** Two distinct records that collide are treated as one, and the loss leaves no error behind to notice. - **We have never seen a collision** is a statement about how many distinct keys have been through the system so far, not evidence that the field is wide enough for the next order of magnitude. - **Size the width against the lifetime distinct-key count, with margin.** The forced threshold is where collisions become certain, not where they start. - **Decide the collision behaviour up front** — chain, compare, reject, or widen — because the case cannot be designed away. ## What the argument does not claim Three limits are worth stating explicitly, because each is a common over-reading: 1. **It says nothing below the threshold.** Fewer distinct keys than values means no repeat is *forced*; it does not mean none occurs. How likely one is at that point is a question about probability, not about counting, and it is answered by a different kind of argument. 2. **It names no pair.** The argument proves that two colliding keys exist and gives no way to point at them; finding them is a separate search over the data. 3. **It is not a verdict on the function.** A collision above the threshold is expected behaviour of every function of that width, so treating one as a defect report misreads the situation. ## The same count elsewhere The identical argument settles a family of fixed-width design questions: short public identifiers drawn from a limited alphabet and length, bucket indexes over a fixed table size, and sequence numbers that wrap within a fixed field. In every case the design question is the same one — how many distinct things will pass through, against how many distinct values the field can represent — and the answer never depends on how cleverly the value is derived.
- Does using a cryptographic digest instead of a fast one change when collisions become unavoidable?No. The threshold is fixed by output width alone: a k-bit output has 2^k values, so 2^k + 1 distinct keys force a repeat whichever function produced them. Cryptographic strength makes collisions hard to find deliberately and keeps the spread even; it adds no values to the output space.
- If two records share a fingerprint, what may you conclude about the records themselves?Only that the map sent them to the same value. They may be equal or entirely unrelated, so a match is evidence to check rather than a decision. The opposite direction is sound: different fingerprints prove the records differ, because a deterministic function sends equal inputs to equal outputs.
- What exactly is given up by truncating a wide digest to its leading bits?Value count, by a factor of two per bit discarded. Cutting a 256-bit digest to 32 bits shrinks the space from 2^256 to 2^32 and moves the forced threshold down by the same factor. Collisions stop being a theoretical property and become something ordinary traffic will reach.
saying these in an interview costs you the question
- Claims a good enough function makes collisions impossible
- Treats equal fingerprints as proof that two records are equal
- Believes collisions only begin once every value has been used
- Says widening to 64 bits removes collisions rather than deferring them
- Confuses the forced threshold with the point where a collision is merely likely
- Reports a collision above the threshold as a defect in the function