短網址生成算法原理與 PHP 實現（Base32 編碼 + MD5 哈希）

前言

短網址服務將長 URL 映射為 6-8 位短碼，核心在于哈希函數與進制編碼的結合。本文介紹一種基於 MD5 + Base32 的經典算法，並提供可直接用於生產環境的 PHP 實現，支持碰撞備選碼生成。

算法原理

1. 對輸入 URL 計算 MD5，得到 128 位（16 字節）摘要。
2. 將 16 字節劃分為 4 段，每段 4 字節（32 位）。
3. 每段取低 30 位（`0x3FFFFFFF`），作為一個無符號整數。
4. 該整數按 5 位一組切分（30 位可得 6 組），每組值範圍 0-31，映射 Base32 字符表（a-z, 0-5），得到 6 字符短碼。
5. 4 段共生成 4 個候選短碼，首選第一個，碰撞時依次備選，極大降低衝突概率。

PHP 核心實現

function shorturl(string $input): array {
    // Base32 字符表 (32 個字符)
    $base32 = [
        'a','b','c','d','e','f','g','h',
        'i','j','k','l','m','n','o','p',
        'q','r','s','t','u','v','w','x',
        'y','z','0','1','2','3','4','5'
    ];

    $hex = md5($input);           // 32 字符十六進制字符串
    $output = [];

    // 每 8 個十六進制字符 = 4 字節 = 32 位
    for ($i = 0; $i < 4; $i++) {
        $subHex = substr($hex, $i * 8, 8);
        // 十六進制字符串轉整數，取低 30 位
        $int = 0x3FFFFFFF & (1 * ('0x' . $subHex));

        $out = '';
        // 取 6 次，每次 5 位
        for ($j = 0; $j < 6; $j++) {
            $val = 0x0000001F & $int;  // 取低 5 位
            $out .= $base32[$val];
            $int >>= 5;                // 右移 5 位
        }
        $output[] = $out;
    }
    return $output;  // 返回 4 個候選短碼
}

測試與輸出示例

$urls = [
    'https://www.example.com/1',
    'https://www.example.com/2'
];

foreach ($urls as $url) {
    $codes = shorturl($url);
    echo "Input : $url\n";
    foreach ($codes as $idx => $code) {
        echo ($idx === 0 ? 'Output: ' : '        ') . "$code\n";
    }
    echo "\n";
}

輸出：

Input : https://www.example.com/1
Output: h0xg4r
        bdr3tw
        osk2d3
        4azfqa

Input : https://www.example.com/2
Output: tm5kxb
        ceoj2s
        yw3dvl
        nrmrxl

輸入僅差一字符，輸出完全不同，體現了雪崩效應；同一輸入多次調用結果穩定一致。

碰撞處理與安全增強

• 碰撞概率：單碼空間 32⁶ = 1,073,741,824。若數據庫已有 n 條記錄，衝突概率約 n / 10⁹。4 碼備選使實際衝突幾乎為零。
• 數據庫去重：實際使用時，按優先序遍歷 4 個碼，首個不存在於表中者入庫。
• 防猜測/防枚舉：
  1. 打亂 `$base32` 字符順序或替換為其他 URL-safe 字符。
  2. 加入私鑰：`md5('secret_prefix' . $input . 'secret_suffix')`。
  3. 對 `$val` 異或固定值：`$out .= $base32[$val ^ 18];`。

總結

該算法無需分佈式 ID 生成器（如 Snowflake），無中心協調，極適合中小型短鏈服務。PHP 實現簡潔高效，配合 Redis/Memcached 緩存熱點映射，可支撐高併發場景。