Handling Hash Collisions
You'll learn how to detect and resolve collisions when two different URLs produce the same short code.
The Collision Problem
When using hash-based generation for URL shorteners, two different long URLs might hash to the same short code—just like two books accidentally getting the same call number at a library. Since each short URL must be unique, you need a strategy to handle these collisions before storing the mapping.
Core Idea
Hash collisions occur because you're compressing a large input space (any possible URL) into a smaller output space (your 6-7 character short codes). Think of it like musical chairs: more URLs than available short codes in your truncated hash means some will compete for the same spot.
Detection and Resolution Strategies
Detection: Before storing a new short code, query your database to check if it already exists. If it does, you have a collision.
Resolution approaches:
-
Append a salt: Add a random string to the original URL before hashing again:
hash(original_url + random_salt). Repeat until you find an unused code. -
Incremental suffix: Append an increasing counter: try
hash(url), thenhash(url + "1"),hash(url + "2"), etc. -
Re-hash with modified input: Use the collision result itself as input:
hash(hash(url)). -
Retry with timestamp: Append the current timestamp milliseconds:
hash(url + timestamp).
Practical Considerations
Each collision check requires a database lookup, adding latency. With Base62 encoding over 6 characters, you have ~56 billion possibilities—collisions are rare initially but increase as your namespace fills. Monitor your collision rate; if it climbs above 1-2%, consider lengthening short codes or pre-generating unique IDs instead.
Key Takeaway: Hash collisions in URL shorteners require detection via database lookup and resolution through re-hashing with modified inputs (salt, counter, or timestamp) until a unique short code is found.