短链接的核心算法

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

原理

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

有关 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)
}

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

首先定义了 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)
}

测试

跑个测试看看：

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