🎓 A1Learner
🔍
0 of 42 lessons completed

Generating Short Codes

Base62 is a way of writing short codes with 62 symbols, the letters and the digits. This lesson designs the codes, the heart of the high-level design step.

A counter becomes a code

A count becomes a code by writing the count in base62. The printout shows small counts becoming short codes, one code per count.

alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

def encode(number):
    if number == 0:
        return alphabet[0]
    code = ""
    while number > 0:
        code = alphabet[number % 62] + code
        number = number // 62
    return code

for count in [0, 1, 25, 61, 62, 12345]:
    print(count, "->", encode(count))

Two links, one bucket

A toy hash in this demo sends each link to a bucket from its length. Two different links land in the same bucket, so the code collision is visible in the printout.

def toy_bucket(url):
    return len(url) % 4

store = {}
urls = ["https://example.com/cats", "https://example.com/dogs"]

for url in urls:
    bucket = toy_bucket(url)
    print(url, "lands in bucket", bucket)
    if bucket in store:
        print("collision: bucket", bucket, "already holds", store[bucket])
    else:
        store[bucket] = url

Check the store, then retry

The fix checks the store before keeping a code. A taken bucket is skipped until a free one is found, so every link keeps a different bucket.

def toy_bucket(url):
    return len(url) % 4

store = {}

def add(url):
    bucket = toy_bucket(url)
    while bucket in store:
        print(url, "finds bucket", bucket, "taken")
        bucket = bucket + 1
    store[bucket] = url
    print(url, "kept in bucket", bucket)

add("https://example.com/cats")
add("https://example.com/dogs")
add("https://example.com/fish")

Example

alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

def encode(number):
    if number == 0:
        return alphabet[0]
    code = ""
    while number > 0:
        code = alphabet[number % 62] + code
        number = number // 62
    return code

codes = []
for count in range(1000, 1005):
    codes.append(encode(count))

for code in codes:
    print("code:", code)
print("codes made:", len(codes))
print("different codes:", len(set(codes)))

Key points

  • Base62: a way of writing codes with 62 symbols, lowercase letters, uppercase letters, and digits.
  • Counter codes: codes made by counting up and writing each count in base62.
  • Hash: a function that turns any input into a value of a fixed size.
  • Code collision: two different long links ending up with the same short code.
  • Check and retry: a taken code is spotted in the store and the generator tries again.
  • Six characters: 6 characters give 56,800,235,584 codes, enough for 568 days at the daily write count.

In this example, 5 counts become 5 different codes. Counting up cannot repeat a code, so counter codes never collide.

Note

7 characters give 3,521,614,606,208 codes and last about 96 years, so 7 characters are the comfortable choice.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

Why are 7-character codes the comfortable choice?