您现在的位置：程式碼之家 >> 編程語言 > >> 網頁程式設計 >> PHP 程式設計 >> PHP 綜合知識

PHP 生成短網址三大核心算法實現與對比

編輯：PHP 綜合知識

短網址核心需求分析

短網址服務核心要求：短碼唯一、生成極快、碰撞率極低、可逆/不可逆按需、支持自定義後綴。本文實現並對比三種主流算法。

算法一：隨機碼生成 (不可逆、需查重)

class RandomShortUrl {
    protected $charset = 'abcdefghijkmnpqrstuvwxyz23456789'; // 排除易混淆字符
    protected $length = 6;
    protected $pdo;
    
    public function __construct(PDO $pdo, int $length = 6) {
        $this->pdo = $pdo;
        $this->length = $length;
    }
    
    public function generate(string $longUrl): string {
        $maxAttempts = 10;
        for ($i = 0; $i < $maxAttempts; $i++) {
            $code = $this->randomCode();
            // 檢查碰撞
            $stmt = $this->pdo->prepare("SELECT id FROM short_urls WHERE code = ?");
            $stmt->execute([$code]);
            if (!$stmt->fetch()) {
                // 存儲映射
                $stmt = $this->pdo->prepare("INSERT INTO short_urls (code, long_url, created_at) VALUES (?, ?, NOW())");
                $stmt->execute([$code, $longUrl]);
                return $code;
            }
        }
        throw new Exception("生成唯一碼失敗，請增加長度或字符集");
    }
    
    protected function randomCode(): string {
        $code = '';
        $max = strlen($this->charset) - 1;
        for ($i = 0; $i < $this->length; $i++) {
            $code .= $this->charset[random_int(0, $max)];
        }
        return $code;
    }
    
    // 6 位 32 進制: 32^6 ≈ 10 億組合
    // 7 位: 32^7 ≈ 340 億
}

算法二：Base32/62 編碼 (不可逆、基於哈希)

class HashShortUrl {
    protected $base32 = '0123456789abcdefghijklmnopqrstuv'; // 32 字符
    protected $base62 = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'; // 62 字符
    protected $pdo;
    
    public function __construct(PDO $pdo) {
        $this->pdo = $pdo;
    }
    
    /**
     * MD5 + Base32 截取 (類似新浪短網址)
     * 將長 URL MD5 後分段編碼，生成 4 組 6 字符碼，任選一組
     */
    public function generateMd5Base32(string $longUrl): array {
        $md5 = md5($longUrl); // 32 字符十六進制
        $codes = [];
        
        for ($i = 0; $i < 4; $i++) {
            // 每次取 8 位十六進制 = 32 位二進制
            $hex = substr($md5, $i * 8, 8);
            $int = hexdec($hex) & 0x3FFFFFFF; // 30 位
            
            $code = '';
            for ($j = 0; $j < 6; $j++) {
                $idx = $int & 0x1F; // 取低 5 位 (0-31)
                $code .= $this->base32[$idx];
                $int >>= 5;
            }
            $codes[] = $code;
        }
        
        // 檢查可用性 (實際應用中通常預生成或允許碰撞覆蓋)
        return $codes; // 返回 4 個備選碼
    }
    
    /**
     * CRC32 + Base62 (極簡、單碼)
     * 適合非安全場景，碰撞率約 1/40億
     */
    public function generateCrc32Base62(string $longUrl): string {
        $crc = crc32($longUrl);
        // CRC32 可能為負數，轉無符號
        $unsigned = sprintf('%u', $crc);
        return $this->base62Encode($unsigned);
    }
    
    protected function base62Encode($num): string {
        $code = '';
        while ($num > 0) {
            $rem = $num % 62;
            $code = $this->base62[$rem] . $code;
            $num = floor($num / 62);
        }
        return $code ?: '0';
    }
    
    protected function base62Decode(string $code): int {
        $num = 0;
        $len = strlen($code);
        for ($i = 0; $i < $len; $i++) {
            $num = $num * 62 + strpos($this->base62, $code[$i]);
        }
        return $num;
    }
}

算法三：自增 ID + Base62 (可逆、極高性能)

class AutoIncrementShortUrl {
    protected $base62 = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
    protected $pdo;
    
    public function __construct(PDO $pdo) {
        $this->pdo = $pdo;
    }
    
    /**
     * 核心邏輯：插入數據庫獲取自增 ID -> Base62 編碼
     * 優點：無碰撞、極快、可逆解碼獲取 ID 反查
     * 缺點：ID 可預測、洩露業務量
     */
    public function generate(string $longUrl): string {
        $stmt = $this->pdo->prepare("INSERT INTO short_urls (long_url, created_at) VALUES (?, NOW())");
        $stmt->execute([$longUrl]);
        $id = $this->pdo->lastInsertId();
        
        return $this->idToCode($id);
    }
    
    public function resolve(string $code): ?string {
        $id = $this->codeToId($code);
        $stmt = $this->pdo->prepare("SELECT long_url FROM short_urls WHERE id = ?");
        $stmt->execute([$id]);
        return $stmt->fetchColumn() ?: null;
    }
    
    protected function idToCode(int $id): string {
        if ($id === 0) return '0';
        $code = '';
        while ($id > 0) {
            $code = $this->base62[$id % 62] . $code;
            $id = (int)($id / 62);
        }
        return $code;
    }
    
    protected function codeToId(string $code): int {
        $id = 0;
        for ($i = 0, $len = strlen($code); $i < $len; $i++) {
            $id = $id * 62 + strpos($this->base62, $code[$i]);
        }
        return $id;
    }
}

綜合對比與選型指南

維度	隨機碼	哈希編碼 (MD5/CRC32)	自增 ID + Base62
唯一性保證	需查重/重試	極低碰撞概率	數據庫主鍵保證 100%
生成性能	中 (查重開銷)	極高 (純計算)	高 (單次 INSERT)
可逆性	不可逆	不可逆	完全可逆
碼長穩定性	固定長度	固定長度	隨 ID 增長 (1→2→3...字符)
安全性/不可預測	高	中 (MD5 可彩虹表)	低 (ID 連續可枚舉)
自定義後綴支持	易 (檢查唯一即可)	難 (需反向計算)	難 (ID 固定)
分布式擴展	需協調 (Redis 集合)	天然分布式	需分布式 ID (Snowflake)
適用場景	營銷活動、需自定義碼	內部工具、非核心業務	核心短鏈服務、高併發

生產級增強方案

1. 混合策略：自增 ID + 隨機前綴

class HybridShortUrl {
    protected $base62 = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
    protected $pdo;
    protected $randomPrefixLength = 2; // 2 字符隨機前綴 = 62^2 = 3844 組合
    
    public function generate(string $longUrl): string {
        $stmt = $this->pdo->prepare("INSERT INTO short_urls (long_url) VALUES (?)");
        $stmt->execute([$longUrl]);
        $id = $this->pdo->lastInsertId();
        
        $prefix = $this->randomPrefix();
        $code = $this->idToCode($id);
        
        return $prefix . $code;
    }
    
    protected function randomPrefix(): string {
        $prefix = '';
        for ($i = 0; $i < $this->randomPrefixLength; $i++) {
            $prefix .= $this->base62[random_int(0, 61)];
        }
        return $prefix;
    }
    
    // 解碼時去除前綴
    public function resolve(string $code): ?string {
        $idCode = substr($code, $this->randomPrefixLength);
        $id = $this->codeToId($idCode);
        // ... 查詢數據庫
    }
}

2. 分布式 ID 生成 (Snowflake 算法)

class SnowflakeIdGenerator {
    protected $workerId;      // 0-31 (5 bits)
    protected $datacenterId;  // 0-31 (5 bits)
    protected $sequence = 0;  // 0-4095 (12 bits)
    protected $lastTimestamp = -1;
    protected $epoch = 1609459200000; // 2021-01-01 00:00:00 UTC 毫秒
    
    public function __construct(int $workerId, int $datacenterId) {
        $this->workerId = $workerId & 0x1F;
        $this->datacenterId = $datacenterId & 0x1F;
    }
    
    public function nextId(): int {
        $timestamp = $this->currentTimeMillis();
        
        if ($timestamp < $this->lastTimestamp) {
            throw new Exception("時鐘回撥，拒絕生成 ID");
        }
        
        if ($timestamp === $this->lastTimestamp) {
            $this->sequence = ($this->sequence + 1) & 0xFFF;
            if ($this->sequence === 0) {
                $timestamp = $this->waitNextMillis();
            }
        } else {
            $this->sequence = 0;
        }
        
        $this->lastTimestamp = $timestamp;
        
        return (($timestamp - $this->epoch) << 22)
            | ($this->datacenterId << 17)
            | ($this->workerId << 12)
            | $this->sequence;
    }
    
    protected function currentTimeMillis(): int {
        return (int)(microtime(true) * 1000);
    }
    
    protected function waitNextMillis(): int {
        $timestamp = $this->currentTimeMillis();
        while ($timestamp <= $this->lastTimestamp) {
            $timestamp = $this->currentTimeMillis();
        }
        return $timestamp;
    }
}

// 使用 Snowflake ID + Base62
$generator = new SnowflakeIdGenerator(1, 1); // worker=1, datacenter=1
$id = $generator->nextId(); // 64位長整數
$code = base62Encode($id);  // 短碼約 11 字符

3. 緩存層加速 (Redis)

class CachedShortUrl {
    protected $redis;
    protected $pdo;
    protected $ttl = 86400 * 30; // 30 天
    
    public function getLongUrl(string $code): ?string {
        // 1. 讀 Redis 緩存
        $longUrl = $this->redis->get("short:$code");
        if ($longUrl !== false) return $longUrl;
        
        // 2. 回源數據庫
        $stmt = $this->pdo->prepare("SELECT long_url FROM short_urls WHERE code = ?");
        $stmt->execute([$code]);
        $longUrl = $stmt->fetchColumn();
        
        if ($longUrl) {
            $this->redis->setex("short:$code", $this->ttl, $longUrl);
        }
        return $longUrl ?: null;
    }
    
    public function create(string $longUrl, string $customCode = ''): string {
        $code = $customCode ?: $this->generateCode($longUrl);
        
        // 原子性檢查並設置 (Lua 腳本)
        $lua = "
            if redis.call('EXISTS', KEYS[1]) == 0 then
                redis.call('SETEX', KEYS[1], ARGV[2], ARGV[1])
                return 1
            else
                return 0
            end
        ";
        $result = $this->redis->eval($lua, 1, "short:$code", $longUrl, $this->ttl);
        
        if ($result) {
            // 異步寫入 MySQL (隊列)
            $this->queue->push('save_short_url', ['code' => $code, 'url' => $longUrl]);
            return $code;
        }
        throw new Exception("代碼已存在: $code");
    }
}

數據庫表設計

CREATE TABLE `short_urls` (
    `id` BIGINT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
    `code` VARCHAR(20) NOT NULL COMMENT '短碼',
    `long_url` TEXT NOT NULL COMMENT '原始長網址',
    `custom` TINYINT NOT NULL DEFAULT 0 COMMENT '是否自定義碼',
    `clicks` INT UNSIGNED NOT NULL DEFAULT 0 COMMENT '點擊次數',
    `created_at` TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
    `expired_at` TIMESTAMP NULL DEFAULT NULL COMMENT '過期時間',
    UNIQUE KEY `uk_code` (`code`),
    INDEX `idx_created` (`created_at`),
    INDEX `idx_expired` (`expired_at`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

重定向服務實現

// redirect.php - 短網址跳轉入口
$code = $_GET['code'] ?? '';
if (!$code) { http_response_code(400); exit('Invalid code'); }

$shortUrl = new CachedShortUrl($redis, $pdo);
$longUrl = $shortUrl->getLongUrl($code);

if ($longUrl) {
    // 異步增加點擊數
    $redis->incr("clicks:$code");
    // 301 永久重定向 (SEO 傳遞權重) 或 302 臨時
    header("Location: $longUrl", true, 301);
    exit;
}

http_response_code(404);
include '404.php';