Module 3: Data Model and Short Code Generation

4. Generating the code with a hash: collisions measured

Next →

Description

When you ask someone to invent how to generate a shortener's short code, they almost always propose the same thing, and it's a good idea: "run the URL through a hash function, keep a few characters, and that's the code". It's elegant —the same URL always gives the same code, without storing a counter, without coordination— and that's why it's the first of the three strategies we study. In this lesson you implement it, run it, and measure its Achilles' heel with a real simulation: collisions. By the end you'll be able to say, with a number you saw come out in the terminal, exactly when and how much this strategy collides, and why the pure hash isn't enough as-is.

This is the module's first "pure execution" lesson. We're not going to quote "collisions are a problem" as a textbook slogan; we're going to generate tens of thousands of distinct URLs, hash them into a short code, and count how many clash. The number that comes out —and it will come out high when the code is short— is the reason no serious shortener uses a pure hash without more, and understanding it with the simulation in front of you is worth ten explanations.

Connection to the module: this is the first of the three lessons on code generation (4, 5, and 6). Here we attack the hash strategy; lesson 5 attacks counter + base62 and random + verification; lesson 6 implements in depth the base62_encode/base62_decode that all three share. Lesson 7 puts them in a table and decides. Notice the thread: each strategy has one characteristic problem, and the hash strategy's is this lesson's —the collisions—. Knowing it with the measured number is what lets you, in lesson 7, not choose it for its pretty side while ignoring its cost.

Two people, the same nickname

Imagine that at the entrance to an enormous party you decide to give each guest a short three-letter nickname, and the rule for making the nickname is to take the first three letters of their name. María arrives and she's "MAR". Carlos arrives and he's "CAR". The system works, it's fast, and you don't need to keep any list: the nickname comes from the name. Until Mariana arrives —and she's also "MAR"—. Now you have two different people with the same nickname. If someone shouts "MAR, someone's looking for you!", both turn around. That's a collision: two different inputs produce the same short output.

Hashing a URL is exactly that nickname rule, with mathematics instead of letters. A hash function takes an input of any size (the long URL) and produces a fixed-size output (a large number). Good hash functions like MD5 or SHA-256 produce outputs that look random and spread very well —two almost identical URLs give completely different hashes—. But the complete hash is enormous (128 bits for MD5), and a 7-character base62 code can't store that much information. So you have to truncate: keep a part of the hash. And truncating is like keeping the first three letters of the name: the fewer letters (fewer bits) you keep, the more people share a nickname. Truncating guarantees there will be collisions; the only question is how often.

The reason collisions are inevitable when truncating has a name: the pigeonhole principle. If you have more pigeons than holes, at least two pigeons share a hole, no way around it. Enlace is going to create billions of URLs (the pigeons), and if the truncated code only has, say, 2¹⁶ = 65,536 possible values (the holes), it's obvious that a great many URLs will fall into the same hole. Truncating little is having few holes. The quantitative question —how many collisions, exactly, for how many holes?— is what we're going to measure.

The birthday problem: you collide sooner than you think

Before the simulation, a warning that surprises almost everyone and that's the key to understanding the numbers to come. Intuition says: "there are 65,536 holes, so there won't be collisions until I have about 65,536 URLs, right?". False, and by a lot. Collisions start much sooner, and the reason is the famous birthday problem.

The classic version: in a room with only 23 people, the probability that two share a birthday is already greater than 50%, even though there are 365 possible days. Why so soon? Because you're not looking for someone to match one fixed date; you're looking for any pair to match, and the number of pairs grows with the square of the people. With 23 people there are 253 possible pairs, and each pair is a chance to clash. The rule of thumb is that collisions become likely when the number of elements approaches the square root of the number of holes, not the number of holes. For 65,536 holes, the square root is 256: around 256 URLs already start to clash appreciably, not 65,536.

This is exactly the opposite of what intuition promises, and that's why you have to see it measured. Keep it as a rule: truncating a hash collides at the square root of the space, not at the whole space. Now let's check it.

Worked example: I measure the collision rate for real

We're going to implement the hash strategy and measure its collisions. The plan: generate N URLs all distinct, hash each one with MD5, keep the lowest n_bits of the hash (that simulates "truncating" to a code of a certain size), and count how many times two different URLs fall into the same truncated value. Since the input URLs are all distinct by construction, any clash is the truncation's fault, not the data's.

# collisions.py — I measure the collisions of a truncated hash, for real.
import hashlib


def truncated_hash(url: str, n_bits: int) -> int:
    """MD5 of the URL, keeping only the lowest n_bits."""
    digest = hashlib.md5(url.encode()).digest()
    full = int.from_bytes(digest, "big")   # the complete hash, 128 bits
    mask = (1 << n_bits) - 1               # a mask of n_bits ones
    return full & mask                     # the lowest n_bits of the hash


def simulate(n_urls: int, n_bits: int):
    """Generates n_urls distinct ones, truncates them to n_bits, counts collisions."""
    seen = {}
    collisions = 0
    for i in range(n_urls):
        url = f"https://example.com/article/{i}"    # all distinct
        code = truncated_hash(url, n_bits)
        if code in seen:
            collisions += 1                # this hole was already taken
        else:
            seen[code] = url
    space = 1 << n_bits                     # available holes = 2^n_bits
    return collisions, space


print(f"{'n_urls':>8} {'n_bits':>7} {'space':>16} {'collisions':>11} {'rate':>8}")
for n_bits in (16, 24, 32):
    for n_urls in (1000, 10000, 50000):
        collisions, space = simulate(n_urls, n_bits)
        rate = collisions / n_urls
        print(f"{n_urls:>8,} {n_bits:>7} {space:>16,} {collisions:>11,} {rate:>7.2%}")
    print()

What to expect. Running this with Python 3.14.0 gives, exactly:

  n_urls  n_bits            space  collisions     rate
   1,000      16           65,536           6   0.60%
  10,000      16           65,536         696   6.96%
  50,000      16           65,536      14,902  29.80%

   1,000      24       16,777,216           0   0.00%
  10,000      24       16,777,216           5   0.05%
  50,000      24       16,777,216          67   0.13%

   1,000      32    4,294,967,296           0   0.00%
  10,000      32    4,294,967,296           0   0.00%
  50,000      32    4,294,967,296           0   0.00%

Read this table slowly, because it's the heart of the lesson. Notice the row that screams: at 16 bits (65,536 holes), with 50,000 URLs, almost 30% clash —14,902 collisions—. That means that if Enlace used a code so short it only had 65,536 possible values, one in three new links would step on an existing one. Unacceptable. And look at the birthday confirmation: with just 1,000 URLs in 65,536 holes —when intuition would say "impossible for them to clash, there are 65 times more holes than URLs"— there are already 6 collisions. They clash at the square root (256), not at the total.

Now look at what happens when you enlarge the space. At 24 bits (16.7 million holes), 50,000 URLs produce only 67 collisions (0.13%): much better, but there are still some. At 32 bits (4,294 million holes), the 50,000 URLs don't clash even once in this run. The numeric lesson is clear: the more bits you keep (longer code), the fewer collisions, and the relationship isn't linear —adding bits helps a lot because it doubles the holes each time—. But "fewer collisions" isn't "zero collisions": as long as you truncate, the pigeonhole still rules, and with enough URLs (Enlace's billions) even 32 bits would clash.

How many bits does Enlace's 7-character base62 code have? Since 62⁷ = 3,521,614,606,208, and that's between 2⁴¹ and 2⁴², a 7-char base62 code is equivalent to ~41.7 bits of space. It's larger than the 32 bits of the last row, so it would collide even less. But —and this is the point that closes the lesson— with the 6 billion URLs Enlace creates in 5 years, the birthday problem hits even at 41.7 bits: the square root of 62⁷ is ~1.88 million, so long before reaching 6 billion links, two different URLs will produce the same truncated hash. The pure hash is going to collide at Enlace's scale. The question is no longer "does it collide?", but "what do you do when it collides?".

What you add to the hash to make it usable (and why it stops being "pure")

The truncated hash isn't discarded; it's fixed, and fixing it reveals why the strategy, in its usable form, is no longer as simple as it sounded. There are two classic patches, and both have a cost:

Patch 1: detect the collision and retry. Before storing, you check whether the code already exists (exists(short_code), the by-key operation from lesson 3). If it exists and points to another URL, you have a collision: you add something to the input —a suffix, a counter, a "salt"— and re-hash until you find a free spot. This works, but notice what you just lost: the pretty property of "the same URL always gives the same code" breaks, because now the code depends on the order in which the URLs arrived and how many collisions there were before. And you gained an extra read (the verification) per write. As soon as you put verification and retry, the hash strategy starts to look a lot like the "random + verification" strategy from lesson 5 —in fact, with a good hash, they're almost the same.

Patch 2: use a longer code. If you make the code long enough (more bits), collisions become rare. But "rare" isn't "never" (the pigeonhole doesn't forgive at scale), so you still need patch 1 as backup, and on top of that you sacrifice the brevity, which is exactly what a shortener sells.

Here's the honest conclusion of the lesson: the pure hash seems to solve the generation for free, but as soon as you make it robust to collisions (and at Enlace's scale you have to), you add a verification per write and lose its initial elegance. It's not a bad strategy —with verification, it's perfectly viable—, but it's not the magic shortcut it appeared to be. There's one more reason to distrust "same code for the same URL", which sounds like an advantage: it means anyone can predict the code of a known URL by hashing it themselves, and that two users who shorten the same URL share a link (and therefore share the click counter and the analytics), which is sometimes not what you want.

flowchart TD
    A["long_url"] --> B["hash(long_url)<br/>MD5/SHA — 128 bits"]
    B --> C["truncate to ~42 bits<br/>= 7 chars base62"]
    C --> D{"does the code already exist<br/>for ANOTHER url?"}
    D -->|no| E["store: short_code ready"]
    D -->|"yes (collision)"| F["add salt / suffix<br/>and re-hash"]
    F --> C

That "collision → re-hash" loop is the real price of the hash strategy. In lesson 5 you'll see that a simple counter never enters that loop (it can't collide), and in lesson 7 we'll put that contrast on the scales.

Common mistakes

Believing that a good hash "doesn't collide". What happens: someone chooses SHA-256 (an excellent cryptographic hash) and concludes that, being so good, there won't be collisions in their short code. They forget that the complete hash hardly collides, but the short code uses a truncated version, and the truncated one collides according to the pigeonhole no matter how good the original hash is. Why it happens: the hash quality is confused with the code size. How to detect it: if your code has N bits, the collisions depend on N, not on whether you used MD5 or SHA-256. How to fix it: remember that truncating is the problem; a perfect hash truncated to 16 bits still clashes 30% with 50k inputs, as you measured. The hash quality ensures uniform distribution, not absence of collisions.

Underestimating collisions by ignoring the birthday. What happens: someone sizes the code space thinking "I need as many holes as URLs" and falls short by an enormous factor, because collisions start at the square root of the space, not at the whole space. With 65,536 holes it already clashes with 256 URLs, not with 65,536. Why it happens: linear intuition ignores that what collides are pairs, which grow with the square. How to detect it: if your reasoning says "there are N holes, I can handle ~N elements", you're missing the square root. How to fix it: for collisions to be rare, the space must be the square of the number of elements, not equal. Enlace has 6 billion elements; for them to barely clash it would need a space on the order of (6 billion)² —much more than 62⁷—, which is why even the 7-char hash needs verification.

Selling "same URL, same code" as a pure advantage. What happens: someone chooses hash "because that way the same URL always gives the same code, and I don't duplicate". They ignore two consequences: that the collision verification breaks that property anyway (two URLs that clash can't both have "their" code), and that the property, when maintained, makes the codes predictable (anyone hashes a known URL and guesses its code) and shared (two users who shorten the same URL share a link, clicks, and analytics). Why it happens: only the good side is seen. How to detect it: ask yourself "is it good for me that the code be predictable from the URL, and that two users share a link?". Often the answer is no. How to fix it: if you really want to deduplicate identical URLs, do it with an explicit "URL → already-assigned code" table, not as a side effect of the hash; and if you don't want it, the pure hash imposes it on you.

Exercises

Exercise 1 — Predict, then measure. Before running anything, predict with the birthday rule: in a space of 2²⁰ holes (1,048,576), around how many URLs do you expect to start producing appreciable collisions? Then, modify the lesson's simulation to try n_bits = 20 with n_urls at 500, 1000, and 2000, and compare your prediction with the measured rate.

See solution

The birthday rule says collisions become appreciable near the square root of the space. For 2²⁰ = 1,048,576 holes, the square root is 2¹⁰ = 1,024. So you expect to start seeing appreciable collisions around ~1,000 URLs, not near a million.

Running simulate(n, 20) for n = 500, 1000, 2000, you'll see few collisions at 500 (well below the root), a few starting to appear around 1,000 (near the root), and notably more at 2,000 (above the root). The exact numbers vary with the URL set, but the pattern —collisions that take off near √space = 1,024, not near 1,048,576— is robust. The moral: to estimate when a truncated hash clashes, look at the square root of the space, not its size.

Exercise 2 — How many bits does Enlace need to barely collide without verification? Enlace creates 6 billion URLs in 5 years. Using the rule "for collisions to be rare, the space must be on the order of the square of the number of elements", estimate how many bits the code would need for the pure hash (without verification) to barely collide, and compare it with the ~42 bits of a 7-char base62 code. What do you conclude?

See solution

For 6 billion ≈ 6 × 10⁹ elements to barely collide, the space should be on the order of (6 × 10⁹)² = 3.6 × 10¹⁹. In bits: log₂(3.6 × 10¹⁹) ≈ 65 bits. That is, the code would need ~65 bits for the pure hash to barely clash without verification.

A 7-char base62 code has ~42 bits (62⁷ ≈ 2⁴¹·⁷). 42 is much less than 65, so Enlace's 7-char code is too short for the pure hash to avoid collisions without verification at the scale of 6 billion. To reach ~65 bits you'd need ~11 base62 chars (62¹¹ ≈ 2⁶⁵·⁵), which would destroy the brevity a shortener sells.

Conclusion: at Enlace's scale, with a short code, the hash has to carry collision verification —there's no shortcut. This is exactly what pushes toward the counter (which never collides, lesson 5) or toward random + verification (lesson 5), and what lesson 7 will weigh.

Exercise 3 — The "same URL, same code" property: advantage or problem? Describe a concrete scenario where the same URL always producing the same code is an advantage, and another where it's a problem. Then say how you'd obtain the advantage (deduplicating identical URLs) without paying the problem (predictable/shared codes).

See solution

Advantage: an internal system that shortens URLs from a fixed catalog and wants the same URL to always resolve to the same code, to avoid creating thousands of different codes pointing at the same destination and to save storage. There, "same URL → same code" deduplicates for free.

Problem: a public shortener where two users shorten https://my-startup.com/secret-launch. With a pure hash, both receive the same code, so they share the link, the click counter, and the analytics —user A sees user B's clicks—. Worse: a competitor can guess the code of a known URL simply by hashing it themselves, without having shortened it. Predictability and sharing are real privacy and product problems.

How to have the advantage without the problem: if you want to deduplicate, do it explicitly with a "long_url → already-assigned code" table or index: when shortening, you check whether that URL already has a code and, if it does, you reuse it; if not, you generate a new one with a counter or random (not derived from the URL's hash). That way you control the deduplication as a product decision, the code isn't predictable from the URL, and users who don't want to share can request their own code. The deduplication stops being a side effect of the hash algorithm and becomes a policy you choose.

Summary and next step

You implemented, ran, and measured the hash generation strategy. The idea is seductive —derive the code from a hash of the URL, without a counter or coordination— but its Achilles' heel is collisions, and you saw them with a number: at 16 bits (65,536 holes) with 50,000 URLs, 29.80% clash; and because of the birthday problem, they clash at the square root of the space (with 1,000 URLs in 65,536 holes there are already 6 collisions), not when the space fills up. Enlarging the code helps a lot (at 32 bits, 0 collisions with 50k URLs) but never reaches "guaranteed zero": at Enlace's 6 billion URLs, even ~42 bits collides. And you saw that fixing the hash with verification + retry adds a read per write, breaks the "same URL → same code" property, and brings it close to the random + verification strategy —that is, it stops being the free shortcut it appeared to be.

Before moving on you should be able to: explain why truncating a hash guarantees collisions (the pigeonhole); state the birthday rule (you clash at the square root of the space) and use it to estimate; cite the rate you measured (29.80% at 16 bits with 50k URLs); and explain the two costs of making the hash robust (verification per write and loss of the "same URL, same code" property).

What comes next is the strategy that never collides. In lesson 5 you meet the global counter + base62: a number that goes 1, 2, 3, … and is converted into a short code —impossible for two to clash because each one is unique by construction—. But it's not free: you'll see its two costs (the sequential, guessable code, and the global counter as a single coordination point) and the third route, random + verification, with its retry rate measured against the giant 62⁷ space you already know.

Resources

← Previous3. SQL vs NoSQL for EnlaceNext →5. Global counter + base62 (and random + verification)