短链接的核心算法

本章代码在01/实现短网址算法分支。

原理

有关 murmur3 的介绍可以参见Murmur 哈希

实现

使用 murmur3 计算出原始链接的 32 位哈希

/// 获取URL的哈希值
fn get_hash(url: &str) -> u32 {
    murmur3::hash32(url.as_bytes())
}

/// 通过指定的种子获取URL的哈希值
fn get_hash_with_seed(url: &str, seed: u32) -> u32 {
    murmur3::hash32_with_seed(url.as_bytes(), seed)
}

利用 fasthash::murmur3::hash32() 可以很方便的实现这个功能。相应的，它还提供了 hash32_with_seed()，利用这个方法，可以指定计算哈希时使用的种子。如果将seed指定为0，那么它的计算结果和 hash32()一样。

将 32 位哈希转成 base62 的字符串形式

/// 将u32类型转成base62
fn u32_to_62(hash: u32) -> String {
    let dict = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    let mut n = hash;
    let mut chars: Vec<char> = vec![];
    while n > 0 {
        let i = (n % 62) as usize;
        let c = dict.chars().nth(i).unwrap();
        chars.push(c);
        n /= 62;
    }
    chars.reverse();
    chars.into_iter().collect::<String>()
}

首先定义了 base62 要用到的字符，我们称它为“字典”。然后将这个字典打散成一个个独立的char，然后通过取模、整除的方式将哈希值进行“退位”，并获得其在字典对应的字符。

其后，将这些取得的字符进去反转，然后将反转的结果转换成String。

生成短链接

有了上面两步，短链接已经可以生成出来了：

/// 获取URL对应的短链接
pub fn short_url(url: &str) -> String {
    let hash = get_hash(url);
    u32_to_62(hash)
}

/// 通过指定的种子获取URL对应的短链接
pub fn short_url_with_seed(url: &str, seed: u32) -> String {
    let hash = get_hash_with_seed(url, seed);
    u32_to_62(hash)
}

测试

跑个测试看看：