哈希冲突

冲突事故：我以为只是运气差

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

我当时的第一反应是：换一个更好的哈希算法，或者把截取长度从 6 位加到 8 位，应该就没事了吧？

但直觉告诉我，这个问题没那么简单。我需要把哈希冲突这件事从头到尾搞清楚。万一将来服务需要做分布式部署，多台机器同时生成短码，冲突问题只会更复杂。

我打开浏览器，开始搜索。很快，一个令人不安的数学结论出现在我眼前。

生日悖论：568 亿也不够用

我查到了一个叫生日悖论的数学结论，它让我意识到自己之前对冲突概率的估计错得离谱。

经典问题：一个房间里需要多少人，才有 50% 的概率出现两人生日相同？

直觉告诉我们，一年 365 天，怎么也得 180 个人以上吧？

答案是 23 人。

23 个人，只有 365 个可能值中的 23 个，就有 50% 的概率撞车。这完全违背直觉，但数学不会说谎。原理是这样的：

第 1 个人的生日不冲突概率：   365/365 = 100%
第 2 个人与前面不冲突概率：   364/365 ≈ 99.7%
第 3 个人与前面不冲突概率：   363/365 ≈ 99.5%
...
第 23 个人与前面不冲突概率：  343/365 ≈ 94.0%

23 个人全部不冲突的概率：
365/365 × 364/365 × 363/365 × ... × 343/365 ≈ 49.3%

至少有一对冲突的概率 = 1 - 49.3% = 50.7%  ✅

每一个新加入的人，都要和之前所有人比对的不是一对，而是一对一对地产生新的配对。23 个人两两配对有 23×22/2 = 253 对——远比想象中多。这就是冲突概率飙升的根源。

把同样的逻辑搬到短链接上：6 位 Base62 有 62^6 ≈ 568 亿种可能，看起来巨大无比。但如果用生日悖论的公式，50% 冲突阈值大约是 √(568亿 × ln2) ≈ 198 万。

也就是说——只需要存入不到 200 万条 URL，就有 50% 的概率出现冲突。568 亿的空间，才用了万分之零点三。

用数据说话：冲突概率到底有多高

我不信邪，写了个脚本算了一遍：

def collision_probability(n, d):
    """
    计算 n 个元素在 d 个可能值中至少有一个冲突的概率

    n: 元素数量（URL 数量）
    d: 可能值数量（62^6 ≈ 568 亿）
    """
    # P(无冲突) = d/d × (d-1)/d × (d-2)/d × ... × (d-n+1)/d
    # P(冲突) = 1 - P(无冲突)
    p_no_collision = 1.0
    for i in range(n):
        p_no_collision *= (d - i) / d
    return 1 - p_no_collision

d = 62 ** 6  # 56,800,235,584

print(f"10 万 URL:   {collision_probability(100_000, d):.6%}")
print(f"100 万 URL:  {collision_probability(1_000_000, d):.6%}")
print(f"500 万 URL:  {collision_probability(5_000_000, d):.6%}")
print(f"1000 万 URL: {collision_probability(10_000_000, d):.6%}")
print(f"1 亿 URL:    {collision_probability(100_000_000, d):.6%}")

# 输出：
# 10 万 URL:   0.000009%
# 100 万 URL:  0.000877%
# 500 万 URL:  0.021919%
# 1000 万 URL: 0.087581%
# 1 亿 URL:    8.008816%

数据清楚地告诉我：

• 10 万条：基本不会冲突，概率 0.000009%
• 100 万条：仍然很低，但已经开始出现非零概率
• 1000 万条：接近 0.1%，每一千次操作就有一次冲突
• 1 亿条：8%，几乎可以确定会发生

我的服务如果做大了，几百万条 URL 是完全有可能的。到那时冲突就不是”小概率事件”，而是”一定会发生的事故”。

更关键的是——这只是哈希方案的冲突概率。它和用什么哈希算法（MD5、SHA256、MurmurHash）无关，只取决于截取后的空间大小。

四种解决方案

搞清楚问题的严重程度后，我系统地研究了所有可能的应对方案。

方案 A：增加短码长度

最直接的做法——从 6 位扩展到 7 位、8 位。

# 6 位：568 亿种可能
d_6 = 62 ** 6    # 56,800,235,584

# 7 位：3.5 万亿种可能
d_7 = 62 ** 7    # 3,521,614,606,208

# 8 位：218 万亿种可能
d_8 = 62 ** 8    # 218,340,105,584,896

# 1 亿条 URL 时的冲突概率
print(f"6 位: {collision_probability(100_000_000, d_6):.4%}")  # 8.01%
print(f"7 位: {collision_probability(100_000_000, d_7):.6%}")  # 0.14%
print(f"8 位: {collision_probability(100_000_000, d_8):.10%}") # 0.0023%

简单有效，但代价也很明显：短码变长了。从 short.url/abc123 变成 short.url/abc12345——虽然只多了两位，但作为”短链接”，每一厘米都很珍贵。而且它只是推迟了问题，并没有从根本上消除冲突。

方案 B：使用更好的哈希算法

MD5 的碰撞抗性确实不行。换 MurmurHash 呢？它是专门为哈希表设计的非加密哈希，分布更均匀，速度也更快。

import mmh3  # MurmurHash3

def generate_murmur_code(url, length=6):
    """用 MurmurHash3 生成短码"""
    hash_int = mmh3.hash(url) & 0xFFFFFFFF  # 转为无符号 32 位整数
    return to_base62(hash_int)[:length]

但问题在于——截断之后，任何哈希算法的优势都会被抹平。 截取 6 位 Base62，只保留了约 35.8 位的信息量。不管你用的是什么神级哈希，35.8 位就是 35.8 位，空间就那么大，冲突概率由截取长度决定，和算法无关。

更好的哈希只能让分布更均匀，但均匀分布不等于不冲突。均匀分布下的生日悖论冲突概率依然存在。

方案 C：自增 ID + Base62

这是我最终选择的路。

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

    def shorten(self, long_url):
        # 检查是否已存在
        existing = db.query(
            "SELECT short_code FROM url_mapping WHERE long_url = ?",
            (long_url,)
        )
        if existing:
            return existing[0]

        # 自增 ID，永不冲突
        self.counter += 1
        short_code = to_base62(self.counter)

        db.execute(
            "INSERT INTO url_mapping (short_code, long_url) VALUES (?, ?)",
            (short_code, long_url)
        )
        return short_code

# ID=1 → "1",  ID=62 → "10",  ID=568亿 → "zzzzzz"

自增 ID 的核心优势是数学上绝对唯一——1、2、3……每个数字天然不同，不需要任何冲突检测。配合 Base62 编码后，100 万变成 4c92（4 位），1 亿变成 6LAzd（5 位），都比我之前用哈希截断的 6 位还短。

但它有两个弱点：

• 暴露业务量：短码是 4c92，反编码就知道你只有几万条链接。竞争对手一眼就能推算出你的规模。
• 单点瓶颈：分布式环境下，多台机器争抢同一个计数器是个麻烦事。

第一个问题我可以接受——Base62 编码后的短码看起来像随机字符串，外行人不会去反推。第二个问题……将来再说。

方案 D：分布式 ID（Snowflake）

如果将来服务做大，需要多台服务器同时生成短码，自增 ID 的单点问题就得解决。Twitter 的 Snowflake 方案是一个经典的答案。

┌──────────────────────────────────────────────────┐
│  1 bit  │    41 bits     │  10 bits  │  12 bits  │
│  符号位  │    时间戳       │  机器 ID   │  序列号    │
│  (固定0) │ (毫秒级精度)    │ (1024台)  │ (4096/毫秒)│
└──────────────────────────────────────────────────┘

每台机器有自己的 ID，时间戳保证全局有序，序列号保证同一毫秒内不重复。这样每台机器可以独立生成 ID，不需要中央协调，也不会冲突。

class SnowflakeID:
    def __init__(self, machine_id):
        self.machine_id = machine_id
        self.sequence = 0
        self.last_timestamp = -1

    def next_id(self):
        timestamp = current_millis()
        if timestamp == self.last_timestamp:
            self.sequence = (self.sequence + 1) & 0xFFF  # 12 位序列号
        else:
            self.sequence = 0
            self.last_timestamp = timestamp

        return (timestamp << 22) | (self.machine_id << 12) | self.sequence

Snowflake 生成的 ID 是 64 位整数，转成 Base62 后大约 11 个字符——比 6 位长了不少。但它在分布式环境下保证唯一性，这是自增 ID 做不到的。

方案对比

我把四种方案放在一起对比：

没有银弹。每一种方案都在不同维度上做了取舍。

我的最终方案

综合考虑，我选了自增 ID + Base62，原因很简单：

class URLShortener:
    BASE62 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

    def __init__(self):
        self.counter = 0
        self.url_to_code = {}
        self.code_to_url = {}

    def _to_base62(self, num):
        if num == 0:
            return self.BASE62[0]
        result = ""
        while num > 0:
            num, rem = divmod(num, 62)
            result = self.BASE62[rem] + result
        return result

    def shorten(self, long_url):
        # 去重：相同 URL 返回已有短码
        if long_url in self.url_to_code:
            return self.url_to_code[long_url]

        # 自增 ID → Base62，永远不冲突
        self.counter += 1
        short_code = self._to_base62(self.counter)

        self.url_to_code[long_url] = short_code
        self.code_to_url[short_code] = long_url
        return f"https://short.url/{short_code}"

    def expand(self, short_code):
        code = short_code.split("/")[-1]
        return self.code_to_url.get(code)

# 测试
s = URLShortener()
print(s.shorten("https://example.com/a"))  # https://short.url/1
print(s.shorten("https://example.com/b"))  # https://short.url/2
print(s.shorten("https://example.com/a"))  # https://short.url/1 （去重）

为什么是这个方案？三个理由：

1. 简单可靠：自增 ID 天然唯一，不需要任何冲突检测或重试逻辑。代码少，bug 就少。
2. 足够短：Base62 编码后，前 568 亿条链接都在 6 位以内。我的服务不可能短时间内用完。
3. 可演进：将来需要分布式，可以直接切换到 Snowflake 或数据库号段模式，短码生成逻辑不变。

我把哈希方案和自增 ID 的核心区别总结了一下：

短码生成搞定了，但数据存在哪？

经过哈希算法的调研、Base62 编码的实现、冲突问题的深入分析，短码生成的逻辑终于尘埃落定。自增 ID + Base62，简单、可靠、够用。

但一个完整的问题一直悬在我心头：这些短码和长 URL 的映射关系，存在哪里？

我目前用的是 Python 字典——程序一重启，所有数据全没了。生产环境需要真正的数据库。但选什么数据库？SQLite？MySQL？Redis？每种选择的性能、可靠性和复杂度都完全不同。

更关键的是：如果短链接服务要做跳转，每次访问都要查一次数据库。SQLite 真的扛得住每秒几千次的查询吗？

练习题

练习 1

6 位 Base62 有 568 亿种组合，看起来很大。请用生日悖论公式计算：存入多少条 URL 时，冲突概率会超过 50%？

n ≈ √(2 × d × ln2)

n ≈ √(2 × 56,800,235,584 × 0.693)
  ≈ √78,728,006,599
  ≈ 2,805,854

练习 2

设计一个完整的冲突处理流程：假设你坚持使用哈希方案（而非自增 ID），如何在生产环境中应对冲突？

import hashlib

class RobustHashShortener:
    def __init__(self):
        self.db = Database()

    def shorten(self, long_url: str) -> str:
        # 1. 预防：检查是否已存在
        existing = self.db.get_by_long_url(long_url)
        if existing:
            return existing

        # 2. 生成 + 检测 + 重试
        max_retries = 5
        for salt in range(max_retries):
            short_code = self._hash_with_salt(long_url, salt)

            try:
                # 3. 依赖数据库唯一索引做最终检测
                self.db.insert(short_code, long_url)
                return f"https://short.url/{short_code}"
            except IntegrityError:
                # 唯一索引冲突，加盐重试
                continue

        # 4. 兜底：重试耗尽，使用自增 ID
        counter = self.db.next_counter()
        return to_base62(counter)

    def _hash_with_salt(self, url: str, salt: int) -> str:
        data = f"{url}:{salt}" if salt else url
        hash_int = int(hashlib.md5(data.encode()).hexdigest()[:8], 16)
        return to_base62(hash_int)[:6]