Detecting Hash Collisions in MD5

Problem How would you detect repetition (collisions) produced by a hashing function like MD5?

Be ready to discuss

• The definition: a collision is two distinct inputs producing the same digest - guaranteed to exist by the pigeonhole principle for any fixed-width hash.
• The straightforward detection: maintain a map from digest to input, and on insert check whether that digest already maps to a different input.
• Why comparing the inputs matters: a repeated digest for identical input is a duplicate, not a collision - conflating the two is the common mistake.
• Scaling the detection: a hash set keyed by digest with chaining, or sorting the digests and scanning for adjacent equals when the set doesn't fit in memory.
• Bloom filters as a cheap pre-filter: constant space, no false negatives, and false positives only trigger the expensive exact check.
• The birthday paradox: collisions become likely at roughly 2^(n/2) hashes, so MD5's 128 bits means expected collisions around 2^64 random inputs - not 2^128.
• MD5 is cryptographically broken: chosen-prefix collisions are constructible in seconds on commodity hardware, so it offers no collision resistance against an adversary.
• The distinction that matters: MD5 and SHA-1 are unsafe for signatures, certificates, and deduplication of untrusted data, but remain fine as fast non-adversarial checksums.
• What to use instead: SHA-256 or BLAKE3 for collision resistance, and bcrypt/scrypt/Argon2 for passwords - a fast hash is the wrong tool there entirely.