短链接的核心算法

本章将对短链接的原理及实现算法进行讲解。

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

原理

原始链接 --> murmur3计算其hash(u32) --> 将hash转成62位的字符表示形式

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

实现

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

将 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，然后通过取模、整除的方式将哈希值进行“退位”，并获得其在字典对应的字符。

生成短链接

测试

跑个测试看看：

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_get_hash() {
        assert_eq!(get_hash("https://axum.rs"), 3506573287);
    }

    #[test]
    fn test_get_hash_with_seed() {
        assert_eq!(
            get_hash_with_seed("https://axum.rs", 0),
            get_hash("https://axum.rs")
        );
        assert_eq!(get_hash_with_seed("https://axum.rs", 0), 3506573287);
        assert_eq!(get_hash_with_seed("https://axum.rs", 100), 888869650);
    }

    #[test]
    fn test_short_url() {
        assert_eq!(short_url("https://axum.rs"), "3PjdTF".to_string());
    }
    #[test]
    fn test_short_url_with_seed() {
        assert_eq!(
            short_url_with_seed("https://axum.rs", 0),
            short_url("https://axum.rs")
        );
        assert_eq!(
            short_url_with_seed("https://axum.rs", 0),
            "3PjdTF".to_string()
        );
        assert_eq!(
            short_url_with_seed("https://axum.rs", 100),
            "Y9BBg".to_string()
        );
    }
}