Base62 编码

选定方案，但新的问题来了

上一章我选了 MD5 哈希 + 截取的方案来生成短链接码。思路没问题，但 MD5 输出是 16 进制的——每个位置只有 16 种可能（0-9, a-f）。这意味着 6 位 16 进制最多只能表示 1677 万个短链接。

1677 万。听起来不少，但 Reddit 每天就有数百万个新链接。一个稍有名气的服务，几个月就耗尽了。

我需要一个更”紧凑”的编码方式：用同样 6 个字符的长度，塞进更多的信息。答案就是 Base62。

但首先我得搞清楚一个问题——为什么是 62？不是 64，不是 36，偏偏是 62？

为什么是 62？

URL 里能安全使用的字符有哪些？我列了一下：

数字：0-9，共 10 个
小写字母：a-z，共 26 个
大写字母：A-Z，共 26 个

10 + 26 + 26 = 62。

0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ
│← 10 个数字 →││← 26 个小写字母 →││← 26 个大写字母 →│

这 62 个字符在 URL 的路径部分完全安全，不需要任何转义。不多不少，刚好 62 个。

那为什么不用更多字符？因为剩下的字符——+、/、=、?、&、#、%——在 URL 中都有特殊含义。用了它们，浏览器会自动编码，短链接反而变长了。

为什么不用更少字符？比如只用 36 个（0-9 + a-z）？当然可以，但效率会降低。我列了一张对比表：

进制	字符集	6 位能表示的数量
10 进制	0-9	10^6 = 100 万
16 进制	0-9, a-f	16^6 ≈ 1677 万
36 进制	0-9, a-z	36^6 ≈ 21 亿
62 进制	0-9, a-z, A-Z	62^6 ≈ 568 亿

所以 62 是 URL 安全字符的上限。在保证安全的前提下，它能用最少的位数表示最大的数值。

568 亿是什么概念？

我一开始对这个数字没什么直觉。让我算一下 62 的幂次，一步步感受它的增长：

62^1 = 62
62^2 = 3,844
62^3 = 238,328
62^4 = 14,776,336
62^5 = 916,132,832      （约 9.16 亿——已经快赶上中国人口了）
62^6 = 56,800,235,584   （约 568 亿）

568 亿。全球人口约 80 亿，这意味着我可以给地球上的每个人分配 7 个短链接，还绰绰有余。而 16 进制 6 位只能表示 1677 万——差了 3000 多倍。

这让我放心了——即使我的服务做到全球级别，6 位 Base62 也完全够用。

我来写一个 Base62 编码器

原理很简单：和十进制转二进制一样，不断除以 62 取余数，只是”数字”变成了 62 个字符。

class Base62:
    CHARSET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

    @classmethod
    def encode(cls, num):
        """将 10 进制数转换为 Base62 字符串"""
        if num == 0:
            return cls.CHARSET[0]

        base62_str = ""
        while num > 0:
            num, remainder = divmod(num, 62)
            base62_str = cls.CHARSET[remainder] + base62_str

        return base62_str

# 我来验证一下
print(Base62.encode(0))      # "0"
print(Base62.encode(10))     # "a"   —— 10 对应第 11 个字符
print(Base62.encode(62))     # "10"  —— 进位了！就像十进制的 "10"
print(Base62.encode(1000))   # "G8"
print(Base62.encode(12345))  # "3D7"

逻辑是通的：num 不断除以 62，余数就是当前位的字符，商继续下一轮。和手算十进制转二进制完全一样的思路。

解码就是反过来：从左到右，每一位乘以 62 再加当前字符的值。

class Base62:
    CHARSET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

    @classmethod
    def decode(cls, s):
        """将 Base62 字符串转换为 10 进制数"""
        num = 0
        for char in s:
            num = num * 62 + cls.CHARSET.index(char)
        return num

# 验证：编解码应该互为逆运算
print(Base62.decode("0"))      # 0
print(Base62.decode("a"))      # 10
print(Base62.decode("10"))     # 62
print(Base62.decode("G8"))     # 1000
print(Base62.decode("3D7"))    # 12345

往返验证都通过了。encode(decode("G8")) 还是 "G8"，decode(encode(1000)) 还是 1000。编码器没问题。

为什么不用 Base64？

你可能会问：Base64 比 Base62 还多两个字符，不是更紧凑吗？

没错。Base64 的字符集是：

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

62 个字符之外，多了 + 和 /。多两个字符意味着更大的基数，理论上编码更短。但恰恰是这两个字符，在 URL 中会出问题：

+ 在 URL 查询字符串中会被解析为空格
/ 是 URL 路径分隔符，放进短链接码里会导致路径解析混乱

如果我在短链接里用了 +，浏览器可能把它编码成 %2B——一个字符变成了三个，短链接反而不短了。= 是 Base64 的填充字符，也有同样的问题。

特性	Base62	Base64
URL 安全	✅ 直接用	❌ 需要额外编码
编码效率	稍低	稍高（多 2 个字符）
短链接适用性	✅ 完美	❌ 不推荐

Base64 在传输二进制数据（比如邮件附件、图片）时是标准选择。但对于短链接，Base62 是最佳选择——少两个字符换来完全的 URL 安全，这笔交易很划算。

容量规划：算一笔账

理论容量 568 亿，但实际能撑多久？让我算算。

假设我的短链接服务每天新增 1 万条链接（这已经是一个相当活跃的服务了——相当于每天有 1 万个新用户在创建短链接）：

总容量：62^6 ≈ 568 亿
每天新增：10,000 条
可使用天数：568 亿 ÷ 10,000 = 5680 万天 ≈ 155,616 年

15 万年。人类文明有文字记录的历史也不过 5000 年。

我多算几个场景，心里更有底：

每天新增量	6 位能用多久	对应体量
1 万条	15 万年	小众服务
100 万条	1,556 年	中型服务
1 亿条	1.5 年	全球顶级服务

就算是每天 1 亿条这种极端情况，6 位用完之后加到 7 位（62^7 ≈ 3.5 万亿）就能再撑 960 年。

嗯，6 位完全够了。我不用在这个问题上纠结了。

我把 Base62 集成到短链接服务里

现在我把上一章的 MD5 哈希方案和 Base62 编码结合起来：

import hashlib

class URLShortener:
    BASE62 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

    def __init__(self):
        self.db = {}  # 简化：用字典模拟数据库

    def _to_base62(self, num, length=6):
        """转换为 Base62，固定长度"""
        if num == 0:
            return self.BASE62[0] * length

        base62_str = ""
        while num > 0:
            num, remainder = divmod(num, 62)
            base62_str = self.BASE62[remainder] + base62_str

        # 左侧补零（补 BASE62[0]）
        return base62_str.zfill(length)[:length]

    def generate_short_code(self, long_url):
        """生成短链接码"""
        # 1. 计算 MD5 哈希
        md5_hash = hashlib.md5(long_url.encode()).hexdigest()

        # 2. 取前 8 位 16 进制，转为整数
        hash_int = int(md5_hash[:8], 16)

        # 3. 转换为 6 位 Base62
        return self._to_base62(hash_int)

    def shorten(self, long_url):
        """创建短链接"""
        short_code = self.generate_short_code(long_url)
        self.db[short_code] = long_url
        return f"https://short.url/{short_code}"

    def expand(self, short_code):
        """还原长 URL"""
        code = short_code.split('/')[-1]
        return self.db.get(code)

# 测试
shortener = URLShortener()

urls = [
    "https://www.example.com/page1",
    "https://www.example.com/page2",
    "https://www.github.com/user/repo",
    "https://www.stackoverflow.com/questions/12345",
]

for url in urls:
    short = shortener.shorten(url)
    print(f"{url[:40]}... → {short}")

# 输出：
# https://www.example.com/page1... → https://short.url/2xK9pL
# https://www.example.com/page2... → https://short.url/8mN3qR
# https://www.github.com/user/repo... → https://short.url/5tY7wZ
# https://www.stackoverflow.com/questions... → https://short.url/1aB4cD

从长 URL 到 6 位短链接码，流程就是三步：MD5 哈希 → 截取 → Base62 编码。简洁高效。

等等，我在这里其实悄悄做了一个假设——我假设不同的长 URL 一定会产生不同的短链接码。但真的是这样吗？

等等，还有一个问题

我现在的方案是：对长 URL 做哈希，截取后转 Base62。问题在于，MD5 有 128 位，但我只取了前 8 位 16 进制（32 位）再转成 6 位 Base62。信息被丢弃了。

这意味着两个完全不同的 URL，可能在截取后碰巧得到相同的短链接码——这就是哈希冲突。

568 亿的空间虽然大，但根据生日悖论，实际存到几十万条的时候，冲突概率就已经不可忽视了。这不是理论上的担忧，而是一个我必须面对的实际问题。

冲突了怎么办？这是我下一步要解决的问题。

练习题

练习 1

为什么 6 位 Base62 能表示 568 亿种组合？请详细计算。

参考答案

计算过程：

Base62 有 62 个不同的字符，每个位置可以是 62 个字符中的任意一个。

6 位 Base62 的组合数：

62 × 62 × 62 × 62 × 62 × 62
= 62^6
= 56,800,235,584
≈ 568 亿

逐位展开：

62^1 = 62
62^2 = 3,844
62^3 = 238,328
62^4 = 14,776,336
62^5 = 916,132,832      （约 9.16 亿）
62^6 = 56,800,235,584   （约 568 亿）

直观理解：

中国人口约 14 亿，568 亿是它的 40 倍
全球人口约 80 亿，可以给每个人分配 7 个不同的短链接
如果用 7 位，则是 62^7 ≈ 3.5 万亿，数量级再翻 62 倍

练习 2

实现一个 Base62 编码工具类，支持固定长度编码和批量操作。

参考答案

class Base62Encoder:
    CHARSET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    CHAR_MAP = {char: i for i, char in enumerate(CHARSET)}

    @classmethod
    def encode(cls, num):
        """单个数字编码"""
        if num == 0:
            return cls.CHARSET[0]

        result = []
        while num > 0:
            num, remainder = divmod(num, 62)
            result.append(cls.CHARSET[remainder])

        return ''.join(reversed(result))

    @classmethod
    def encode_fixed(cls, num, length=6):
        """固定长度编码，左侧补零"""
        encoded = cls.encode(num)
        return encoded.rjust(length, cls.CHARSET[0])

    @classmethod
    def decode(cls, s):
        """单个字符串解码"""
        num = 0
        for char in s:
            num = num * 62 + cls.CHAR_MAP[char]
        return num

    @classmethod
    def batch_encode(cls, numbers, length=6):
        """批量编码"""
        return [cls.encode_fixed(n, length) for n in numbers]

    @classmethod
    def batch_decode(cls, strings):
        """批量解码"""
        return [cls.decode(s) for s in strings]

# 测试
nums = [1, 100, 1000, 10000, 100000]
encoded = Base62Encoder.batch_encode(nums)
print(encoded)  # ['000001', '00001C', '0000G8', '0001G8', '000Q0S']

decoded = Base62Encoder.batch_decode(encoded)
print(decoded)  # [1, 100, 1000, 10000, 100000]

上一章节哈希算法使用哈希算法生成短链接

下一章节哈希冲突不同 URL 产生相同哈希怎么办？