Course contentsShow
← System Design
Lesson 1509 of 1,91937. Real-World System: URL ShortenerFree lesson

Handling Hash Collisions

Detect collisions when two URLs hash to the same short code and implement strategies like appending salt or re-hashing.

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:

  1. 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.

  2. Incremental suffix: Append an increasing counter: try hash(url), then hash(url + "1"), hash(url + "2"), etc.

  3. Re-hash with modified input: Use the collision result itself as input: hash(hash(url)).

  4. 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.