哈希算法

那次事故之后

上次短码冲突的事故让我心有余悸。两个不同的长链接，居然生成了同一个短码。用户点击后跳到了别人的页面——这种 bug 发生一次就够要命了。

我花了一个晚上研究哈希算法。不是那种走马观花的浏览，而是真的打开 Python，一行一行跑代码，搞清楚到底哪里出了问题。

先从最根本的问题开始：如何把一个任意长度的 URL，变成一个固定长度的短标识符？ 长链接可能几百上千个字符，但短码只有 6-8 个字符的空间。中间这个”压缩”的过程，怎么才能保证不丢信息、不出错？

最直觉的答案就是——哈希函数。

输入（任意长度） → 哈希函数 → 输出（固定长度）

"https://example.com/very/long/path" → MD5 → "b10a8db164e0754105b7a99be72e3fe5"
"https://example.com/short"           → MD5 → "27b843d58f5a78936ab363b5e7b7f410"

不管输入多长多短，输出的长度永远一样。这正是我需要的。

我用 MD5 生成的短码为什么冲突？

我之前的方案很简单：对 URL 算 MD5，截取前 6 位，搞定。

import hashlib

def generate_short_code(url, length=6):
    """截取 MD5 哈希的前 N 位"""
    full_hash = hashlib.md5(url.encode()).hexdigest()
    return full_hash[:length]

# 示例
print(generate_short_code("https://www.example.com"))  # "b10a8d"
print(generate_short_code("https://www.example.com/")) # "66f0cf"
# 多了一个斜杠，哈希完全不同（雪崩效应）

MD5 本身有几个好用的特性，这些特性让我一开始觉得它很靠谱：

1. 确定性：同一个 URL，不管算多少次，结果都一样。这意味着相同的链接不会生成两个不同的短码。
2. 雪崩效应：输入哪怕只差一个字符，输出也天差地别。上面那个例子，多了一个 /，哈希值从 b10a8d 变成了 66f0cf，完全不相关。
3. 不可逆：没法从哈希值反推出原始 URL。用户看到短码，猜不出原始链接长什么样。
4. 速度快：微秒级就能算完。对于一个每秒可能处理上千个请求的短链接服务来说，这点很重要。

这些特性看起来完美。但问题不在 MD5 本身，而是出在我接下来的操作上——截断。

MD5 输出 32 个十六进制字符，也就是 128 位。32 个字符的”短链接”一点也不短——short.url/b10a8db164e0754105b7a99be72e3fe5，比我原来的 URL 还长。

所以我截取了前 6 位。这正是事故的根源。

截断之后的碰撞概率

我用生日悖论的公式算了一笔账。6 位十六进制，可能的组合数是 16^6 = 16,777,216，大约 1677 万。

def collision_probability(n, d):
    """
    n 个元素在 d 个可能值中的冲突概率
    基于生日悖论
    """
    p_no_collision = 1.0
    for i in range(n):
        p_no_collision *= (d - i) / d
    return 1 - p_no_collision

d_16_hex = 16 ** 6  # 6 位 16 进制：1677 万

print(f"存了 1000 条:  {collision_probability(1000, d_16_hex):.6%}")
print(f"存了 1 万条:   {collision_probability(10000, d_16_hex):.6%}")
print(f"存了 10 万条:  {collision_probability(100000, d_16_hex):.6%}")

# 输出：
# 存了 1000 条:  0.029708%
# 存了 1 万条:   2.878517%
# 存了 10 万条:  95.181672%

10 万条 URL，冲突概率就飙到了 95%。 难怪我出事了。这才几千条数据就开始撞车，我居然之前一直没注意到。

哈希碰撞并不是什么小概率黑天鹅，而是数学上必然会发生的事情。有限的空间（1677 万个坑），装越来越多的 URL，迟早撞车。这就像鸽笼里塞鸽子——笼子不够，必然有两只挤在一起。更让人不安的是，由于生日悖论，冲突不需要等到空间用完才出现，远在此之前就会大规模爆发。

我试了不同截取长度，整理了一张表：

6 位十六进制完全不够用。如果换成 62 进制，同样的 6 位，空间从 1677 万暴涨到 568 亿——但这需要先解决编码问题（下一节再说）。

常见哈希算法对比

我把能找到的哈希算法都过了一遍：

短链接不需要加密安全性，我不怕别人”破解”我的短码。我只需要：快速计算、低冲突率、输出长度合适。

所以 MD5 或 MurmurHash 理论上是不错的选择——前提是截取长度够用。

我试了 SHA256，碰撞确实更少

我接着尝试了 SHA256，想看看更强的哈希算法能不能解决问题。

import hashlib

def generate_sha256_code(url, hex_length=8):
    """用 SHA256 生成短码"""
    full_hash = hashlib.sha256(url.encode()).hexdigest()
    return full_hash[:hex_length]

url = "https://www.example.com/page1"

md5_code = hashlib.md5(url.encode()).hexdigest()[:8]
sha256_code = hashlib.sha256(url.encode()).hexdigest()[:8]

print(f"MD5:    {md5_code}")     # MD5:    c4ca4238
print(f"SHA256: {sha256_code}")  # SHA256: 50d858e0

SHA256 的输出是 64 个十六进制字符，比 MD5 的 32 个多了一倍。截取前 8 位的话，碰撞概率确实更低——因为即便截断，每次哈希都是在一个更大的”指纹空间”里取样。

但问题没变：不管哈希算法多强，截取之后的空间还是有限的。 8 位十六进制就是 16^8 ≈ 42.9 亿种可能，和算法是 MD5 还是 SHA256 无关。

而且 SHA256 的计算速度比 MD5 慢大约 3-5 倍。短链接服务是要扛高并发的，每个请求都要做一次哈希计算，这个开销不能忽视。

我在心里列了个账：

结论让我有点沮丧：换更强的哈希算法，并不能从根本上解决截断碰撞的问题。 碰撞率取决于截取后的空间大小，而不是哈希算法本身。SHA256 确实比 MD5 更安全、更抗碰撞——但那是指完整输出。一旦截断，安全性优势就消失了。

我需要换一个完全不同的思路。

哈希 vs 自增 ID：我终于理解了根本矛盾

那天晚上我盯着屏幕发呆，突然意识到一个更深层次的问题。

哈希方案的冲突是概率问题，不是技术问题。 不管我用 MD5、SHA256 还是 MurmurHash，不管截取 6 位还是 8 位——只要 URL 足够多，冲突迟早会发生。这是数学规律，不是代码 bug。

那有没有一种方案，永远不会冲突？

有。自增 ID。

class CounterShortener:
    def __init__(self):
        self.counter = 0

    def shorten(self, long_url):
        self.counter += 1
        # 第 1 个链接 → 1，第 2 个 → 2，第 100 万个 → 1000000
        # 永远不会重复
        return str(self.counter)

shortener = CounterShortener()
print(shortener.shorten("https://example.com/a"))  # "1"
print(shortener.shorten("https://example.com/b"))  # "2"
print(shortener.shorten("https://example.com/c"))  # "3"

自增 ID 简单粗暴：1、2、3……每个数字都是唯一的，永远不会撞车。就像排队取号——每个人拿到的号码一定不一样。不用算哈希，不用担心碰撞，不用搞什么加盐重试。

但它有一个致命的缺点：暴露业务量。 看到短码是 1000000，就知道你只有 100 万条链接。看到短码是 15，就知道你这个服务刚上线。竞争对手扫一眼就能推算出你的用户规模。这就像餐厅门口的取号机，看到前面排到 800 号，就知道今天生意不错。

而且纯数字的短码太长了。100 万是 7 位数，1 亿是 9 位数——一点都不”短”。

我把两种方案的优缺点摆在一起：

两种方案各有各的坑。纯哈希会冲突，纯自增会暴露数据。我需要一个能兼顾两者优点的方案。

那天晚上快凌晨两点了，我终于想通了一件事——如果能用自增 ID 保证唯一性，再用一种高效的编码把数字”伪装”成看起来随机的字符串，不就两全其美了吗？

我的决定：自增 ID + Base62 编码

想了一晚上，我做了决定：用自增 ID 保证唯一性，用 Base62 编码让短码更短、更不可预测。

class URLShortener:
    BASE62 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

    def __init__(self):
        self.url_to_short = {}
        self.short_to_url = {}
        self.counter = 0

    def _to_base62(self, num):
        """将 10 进制数转换为 62 进制字符串"""
        if num == 0:
            return self.BASE62[0]

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

        return base62_str

    def shorten(self, long_url):
        # 检查是否已存在（去重）
        if long_url in self.url_to_short:
            return self.url_to_short[long_url]

        # 自增 ID + Base62 编码
        self.counter += 1
        short_code = self._to_base62(self.counter)

        # 存储双向映射
        self.url_to_short[long_url] = short_code
        self.short_to_url[short_code] = long_url

        return f"https://short.url/{short_code}"

    def restore(self, short_code):
        return self.short_to_url.get(short_code)

# 使用示例
shortener = URLShortener()

url = "https://www.example.com/very/long/url/with/many/parameters"
print(shortener.shorten(url))
# https://short.url/4fcVwD   ← 比纯数字短多了

print(shortener.restore("4fcVwD"))
# https://www.example.com/very/long/url/with/many/parameters

为什么选这个方案？

• 自增 ID 永远不会冲突——数学上绝对唯一，不用再担心碰撞
• Base62 编码让数字更短——1000000 变成 4fcVwD，6 个字符搞定
• 62 进制有 568 亿种组合——6 位足够用很久
• 看不出业务量——4fcVwD 比 1000000 难猜多了

这不是完美的方案——自增 ID 在分布式环境下需要额外处理——但至少它从根本上消除了哈希碰撞的噩梦。

选择 Base62 不是随便拍脑袋的

做下决定的那一刻，我知道自己只是把问题往下推了一层。

Base62 只有 62 个字符（0-9, a-z, A-Z），为什么不用 64 个？为什么不用 36 个？为什么不用其他符号？

6 位 Base62 的空间是 568 亿，6 位 Base36 只有 21 亿，差了 27 倍。多出来的 26 个大写字母，让短码短了一大截。但多加 + 和 /（变成 Base64）呢？这两个字符在 URL 里有特殊含义，会引发编码问题。

背后的数学很讲究。 字符集的每一个选择，都在影响短码的长度、安全性和 URL 兼容性。

下一节，我需要把 Base62 的原理彻底搞清楚。

练习题

练习 1

为什么 MD5 适合短链接生成，但不适合密码存储？

练习 2

如果截取 MD5 哈希的前 6 位（16 进制），最多能表示多少个不同的短链接？什么时候冲突概率会超过 50%？

16^6 = 16 × 16 × 16 × 16 × 16 × 16 = 16,777,216 ≈ 1677 万

阈值 ≈ √(16^6 × ln2) ≈ √(16,777,216 × 0.693) ≈ √11,625,816 ≈ 3409