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