本章将对短链接的原理及实现算法进行讲解。
原理
有关 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
,然后通过取模、整除的方式将哈希值进行“退位”,并获得其在字典对应的字符。
其后,将这些取得的字符进去反转,然后将反转的结果转换成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()
);
}
}