短链接的核心算法

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

原理

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

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

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

实现

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

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

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

/// 获取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)
}

测试

跑个测试看看：

#[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()
        );
    }
}