Design a URL Shortener: Sequential Codes vs Real Hash Collisions

A URL shortener’s whole job is compressing a long string into a short one you can always map back — the interesting design decision is how you generate that short code.

Sequential ID, base62-encoded: never collides, always guessable

import string

ALPHABET = string.digits + string.ascii_lowercase + string.ascii_uppercase  # base62, 62 chars

def encode(n):
    if n == 0:
        return ALPHABET[0]
    chars = []
    base = len(ALPHABET)
    while n > 0:
        n, rem = divmod(n, base)
        chars.append(ALPHABET[rem])
    return "".join(reversed(chars))

class SequentialShortener:
    def __init__(self, start_id=1):
        self.next_id = start_id
        self.urls = {}

    def shorten(self, long_url):
        code = encode(self.next_id)
        self.urls[code] = long_url
        self.next_id += 1
        return code

shortener = SequentialShortener(start_id=60)
print(shortener.shorten("https://example.com/a"))
print(shortener.shorten("https://example.com/b"))
print(shortener.shorten("https://example.com/c"))
print(shortener.shorten("https://example.com/d"))

$ python sequential_shortener.py
Y
Z
10
11

Starting the counter at 60 (instead of 1) makes the carry visible immediately: 60 and 61 are still single base62 digits (Y, Z — the alphabet is digits, then lowercase, then uppercase, 62 symbols total), but 62 has to roll over into two digits, the same way 9 rolls over into 10 in decimal. Anyone who shortens two URLs a minute apart and gets back Y and Z has just learned the codes are sequential — incrementing either one finds the next real shortened URL.

Hash-based codes: unguessable, but collisions are mathematically guaranteed

import hashlib

def short_hash(url, salt=""):
    return hashlib.md5((url + salt).encode()).hexdigest()[:2]  # 2 hex chars = 256 possible codes

class HashShortener:
    def __init__(self):
        self.codes = {}  # code -> long_url

    def shorten(self, long_url):
        salt = ""
        attempt = 0
        while True:
            code = short_hash(long_url, salt)
            if code not in self.codes:
                self.codes[code] = long_url
                if attempt > 0:
                    print(f"  {long_url} -> {code} (needed {attempt} retry(s))")
                else:
                    print(f"  {long_url} -> {code}")
                return code
            if self.codes[code] == long_url:
                return code
            attempt += 1
            salt = str(attempt)
            print(f"  collision on {code!r} ({self.codes[code]!r} already has it) - retrying with salt {salt!r}")

shortener = HashShortener()
shortener.shorten("https://example.com/page-4")
shortener.shorten("https://example.com/page-11")

$ python hash_shortener.py
  https://example.com/page-4 -> 5c
  collision on '5c' ('https://example.com/page-4' already has it) - retrying with salt '1'
  https://example.com/page-11 -> 8c (needed 1 retry(s))

page-4 and page-11 are genuinely different URLs, but truncating MD5 to just 2 hex characters leaves only 256 possible codes — page-11 really does hash to the same 5c that page-4 already claimed. The fix isn’t to avoid collisions (with a small enough code space, you can’t); it’s to detect the collision and retry with a salted input until a free code turns up. A production system uses a longer code (6-7 base62 characters gives billions of values), which makes collisions rare rather than absent — the retry logic here is the same logic that code would still need, just triggered far less often.

Practice

import string
ALPHABET = string.digits + string.ascii_lowercase + string.ascii_uppercase

def encode(n):
    if n == 0:
        return ALPHABET[0]
    chars = []
    base = len(ALPHABET)
    while n > 0:
        n, rem = divmod(n, base)
        chars.append(ALPHABET[rem])
    return "".join(reversed(chars))

# Z is index 61 in ALPHABET (0-9, then a-z, then A-Z)
z_index = ALPHABET.index("Z")
print(f"Z's numeric ID: {z_index}")
print(f"Next code: {encode(z_index + 1)}")

$ python predict_next.py
Z's numeric ID: 61
Next code: 10

import hashlib

def short_hash(url, length=3):
    return hashlib.md5(url.encode()).hexdigest()[:length]

for url in ["https://example.com/page-4", "https://example.com/page-11"]:
    print(f"{url} -> {short_hash(url)}")

$ python wider_hash.py
https://example.com/page-4 -> 5c6
https://example.com/page-11 -> 5c3

import hashlib

def short_hash(url):
    return hashlib.md5(url.encode()).hexdigest()[:2]

seen = {}
for i in range(1, 500):
    url = f"https://example.com/item-{i}"
    code = short_hash(url)
    if code in seen:
        print(f"Collision: {seen[code]!r} and {url!r} both hash to {code!r}")
        break
    seen[code] = url

$ python find_another_collision.py
Collision: 'https://example.com/item-6' and 'https://example.com/item-15' both hash to '92'

import hashlib

def short_hash(url, salt=""):
    return hashlib.md5((url + salt).encode()).hexdigest()[:2]

class HashShortener:
    def __init__(self):
        self.codes = {}

    def shorten(self, long_url):
        salt = ""
        attempt = 0
        while True:
            code = short_hash(long_url, salt)
            if code not in self.codes:
                self.codes[code] = long_url
                return code
            if self.codes[code] == long_url:
                return code
            attempt += 1
            salt = str(attempt)

shortener = HashShortener()
first = shortener.shorten("https://example.com/page-4")
second = shortener.shorten("https://example.com/page-4")
print(f"first call: {first}, second call: {second}, same code: {first == second}")

$ python idempotent_shorten.py
first call: 5c, second call: 5c, same code: True