萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 短網址生成演算法:CRC32 + Base62 編碼原理與實作

短網址服務 (如 bit.ly, tinyurl) 核心在於將長網址映射為短代碼。本文介紹基於 CRC32 雜湊 + Base62 編碼 的無狀態短網址生成演算法,無需資料庫儲存對應關係,適合分散式、高併發場景。

演算法原理

  1. CRC32 雜湊:將長網址字串計算為 32 位無符號整數 (0 ~ 4,294,967,295)
  2. Base62 編碼:將整數轉為 0-9, A-Z, a-z (62 字元) 進位制字串,長度大幅縮短
  3. 無狀態:相同網址永遠產生相同短碼,無需資料庫查詢/寫入

核心實作

<?php
class ShortUrl
{
    private const BASE62_CHARS = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';

    /**
     * 生成短碼
     * @param string $url 原始長網址
     * @return string 短碼 (如: "aB3f9K")
     */
    public static function encode(string $url): string
    {
        // 1. CRC32 雜湊 (取無符號整數)
        $crc = sprintf('%u', crc32($url));

        // 2. Base62 編碼
        $code = '';
        $num = (int)$crc; // PHP 整數在 64 位系統足夠容納 32 位
        if ($num === 0) return '0';

        while ($num > 0) {
            $rem = $num % 62;
            $code = self::BASE62_CHARS[$rem] . $code; // 字首插入
            $num = (int)($num / 62);
        }
        return $code;
    }

    /**
     * 解碼短碼回原始 CRC32 值 (無法反推原 URL,僅供驗證)
     */
    public static function decode(string $code): int
    {
        $num = 0;
        $len = strlen($code);
        for ($i = 0; $i < $len; $i++) {
            $char = $code[$i];
            $val = strpos(self::BASE62_CHARS, $char);
            if ($val === false) throw new InvalidArgumentException("Invalid char: $char");
            $num = $num * 62 + $val;
        }
        return $num;
    }

    /**
     * 產生完整短網址
     */
    public static function makeUrl(string $longUrl, string $domain = 'https://s.example.com'): string
    {
        return rtrim($domain, '/') . '/' . self::encode($longUrl);
    }
}

// 使用範例
$urls = [
    'https://www.example.com/very/long/url/with/many/parameters?foo=bar&baz=qux',
    'https://shop.example.com/product/12345?utm_source=newsletter&utm_medium=email',
    'https://api.example.com/v1/users/98765/profile?fields=name,email,avatar',
];

foreach ($urls as $url) {
    $short = ShortUrl::makeUrl($url);
    echo "$url\n=> $short\n\n";
}

輸出範例

https://www.example.com/very/long/url/with/many/parameters?foo=bar&baz=qux
=> https://s.example.com/1Kq9zR

https://shop.example.com/product/12345?utm_source=newsletter&utm_medium=email
=> https://s.example.com/3mP7vL

https://api.example.com/v1/users/98765/profile?fields=name,email,avatar
=> https://s.example.com/8nQ2wA

碰撞分析與機率

  • CRC32 輸出空間:2³² ≈ 42.9 億
  • 根據生日悖論,產生 **7.7 萬** 個短碼時,碰撞機率達 50%
  • 產生 **30 萬** 時,碰撞機率約 1%
  • 對於中小型應用 ( < 10 萬連結) 碰撞風險極低

碰撞處理策略

<?php
class ShortUrlWithCollisionCheck extends ShortUrl
{
    private PDO $db;

    public function __construct(PDO $db) { $this->db = $db; }

    public function getOrCreate(string $longUrl): string
    {
        $code = self::encode($url);

        // 檢查資料庫是否已存在 (不同長網址產生相同短碼)
        $stmt = $this->db->prepare('SELECT long_url FROM short_urls WHERE code = ?');
        $stmt->execute([$code]);
        $existing = $stmt->fetchColumn();

        if ($existing) {
            if ($existing === $longUrl) return $code; // 同一網址,直接返回
            // 碰撞:加入隨機鹽值重新生成
            return $this->resolveCollision($longUrl, $code);
        }

        // 新短碼,寫入資料庫
        $this->db->prepare('INSERT INTO short_urls (code, long_url, created_at) VALUES (?, ?, NOW())')
                 ->execute([$code, $longUrl]);
        return $code;
    }

    private function resolveCollision(string $url, string $baseCode): string
    {
        for ($i = 1; $i <= 100; $i++) {
            $salted = $url . '#' . $i; // 加入鹽值
            $code = self::encode($salted);
            $stmt = $this->db->prepare('SELECT 1 FROM short_urls WHERE code = ?');
            $stmt->execute([$code]);
            if (!$stmt->fetchColumn()) {
                $this->db->prepare('INSERT INTO short_urls (code, long_url, created_at) VALUES (?, ?, NOW())')
                         ->execute([$code, $url]);
                return $code;
            }
        }
        throw new RuntimeException('Unable to resolve collision after 100 attempts');
    }
}

替代演算法比較

演算法特點碰撞率適用場景
CRC32 + Base62無狀態、極快、碼長 5-7 字元~7.7萬達50%中小型、分散式、無資料庫
MD5 + Base62 (取前 6-8 碼)128 位雜湊、碰撞極低極低大型系統、需極低碰撞
自增 ID + Base62無碰撞、需資料庫、可預測0%集中式、需資料庫、可接受可預測
隨機字串 + DB 查重簡單、碼長固定視長度而定簡單專案、短碼長度固定 (如 6 碼)

安全性考量

  • 枚舉攻擊:短碼可預測/遍歷 → 加入隨機前綴、速率限制、驗證碼
  • 開放重導向:惡意短網址導向釣魚頁 → 域名白名單、安全瀏覽 API 檢查
  • 資料洩露:短碼洩露內部結構 → 避免在短碼編碼內部 ID
copyright © 萬盛學電腦網 all rights reserved