短链接的核心算法

987594
2021/11/26 04:36:27

原理

原始链接 --> 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)
}

利用 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>()
}

其后,将这些取得的字符进去反转,然后将反转的结果转换成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()
        );
    }
}