如何设计一个短链接系统

前言

文章有点长，大概需要花费10分钟左右，如果你读完，设计一个短链系统，面试、实战，轻松拿捏！

短链接

短链接 是一种将长URL地址转换为较短、易于记忆的链接的技术。它通过使用特定的算法或服务将长链接压缩成更短的形式，以便在限制字符长度或需要更简洁的场景下使用。

原始网址：https://cloud.tencent.com/developer/article/2378083
短网址：http://xx.cn/dFz1S

短链使用场景

短信

电商平台发送短信给用户，短信内容带链接，产生的问题：

1. 节约成本 导致短信内容过长，短信费用翻倍。各大短信平台短信费用计算规则，短信内容小于70个字，算一条短信，超过70个字，短信按68个字算一条。如果把长链接转换为短链接大大的节约了短信费用成本。
2. 增加体验 短信内容带长链接，一般是营销短信。如果短信内容带这么长的链接，一般用户不会点击，误以为是垃圾短信，用户转化率偏低，失去营销的意义。同时用户体验也不友好，如果换成短链，提升用户体验，用户转化率也得到提升

内容分享

内容分享平台，比如微博平台，一条微博的信息有字数限制，使用长链接会占用大量的字数，使用短链，能节约字数，内容描述的信息更丰富

二维码

二维码 的内容是一段文本，这些文本通过不同的前缀可以被手机识别为不同的数据类型

影响二维码复杂度的两个属性分别是 内容长度 与 容错率 。

那长链接转换为短链接内容长度大大减少，二维码的复杂度就得到降低，我们以下面对应的长链接与短链接为例进行演示：

原始网址：https://cloud.tencent.com/developer/article/2378083
短网址：http://xx.cn/dFz1S

生成的二维码的效果如下：

看上去，明显短链生成的二维码复杂度低很多，也提升了扫码识别的性能

短链接请求流程

短网址服务的一个核心功能，就是把原始的长网址转化成短网址。除了这个功能之外，短网址服务还有另外一个必不可少的功能。那就是，当用户点击短网址的时候，短网址服务会将浏览器 重定向 为原始网址。这个过程是如何实现的呢？

URL重定向

上面提到了重定向，那什么是重定向呢？

重定向 是指当浏览器请求一个 URL 时，服务器返回一个 重定向 指令，告诉浏览器地址已经变了，麻烦使用新的 URL 再重新发送新请求。这个重定向响应有一个以 3 开头的状态码 ，并且有一个 Location 头字段 表示要重定向到的位置。

浏览器接收到这个重定向之后，会立即加载 Location 中指定的 URL。通常这一过程耗时极短，用户基本注意不到这个过程。

重定向过程如下图所示：

重定向响应有一个以 3 开头的状态码，状态码如图：

满足短 URL 重定向要求的 HTTP 重定向响应码有 301 和 302 两种

301 表示 永久重定向 ，即浏览器一旦访问过该短 URL，就将重定向的原始长 URL 缓存在本地，此后不再请求短 URL 生成器，直接根据缓存在浏览器（HTTP 客户端）的长 URL 路径进行访问。

302 表示 临时重定向 ，每次访问短 URL 都需要访问短 URL 生成器。一般说来，使用 301 状态码可以降低服务器的负载压力，但无法统计短 URL 的使用情况，比如：pv、uv的统计，因此选择使用 302 状态码构造重定向响应

短链生成方案

通过哈希算法生成短链接

哈希算法可以将一个不管多长的字符串，转化成一个长度固定的哈希值。我们可以利用哈希算法，来生成短网址。

哈希算法有很多，我们只需要关注哈希算法的两个关键点 计算速度 和 冲突概率 。

能够满足这样要求的哈希算法有很多，其中比较著名并且应用广泛的一个哈希算法，那就是 MurmurHash 。

MurmurHash 算法提供了两种长度的哈希值，一种是 32bits，一种是 128bits。为了让最终生成的短网址尽可能短，我们可以选择 32bits 的哈希值

Google Guava工具包已经实现了MurmurHash算法，直接引入使用即可：

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>30.1-jre</version>
</dependency>

示例：

package com.example.demo;
import com.google.common.hash.Hashing;
import java.nio.charset.Charset;
public class ShortUrl {
    public static void main(String[] args) {
        String longUrl = "https://cloud.tencent.com/developer/article/2378083";
        int hashValue = toHash(longUrl);
        System.out.println(hashValue);
     * 通过MurmurHash算法把长链接转换为32bit
     * @param longUrl
     * @return
    public static int toHash(String longUrl){
        int hashValue =  Hashing.murmur3_32().hashString(longUrl, Charset.defaultCharset()).asInt();
        return hashValue;
}

运行结果：

长链接：https://cloud.tencent.com/developer/article/2378083  hash值:580086598

如何让短链接更短

通过 MurmurHash 算法得到的短网址： http://xx.cn/580086598 ,还是很长，那怎么办呢？再介绍一种种算法Base62

Base62编码 是由10个数字、26个大写英文字母和26个小写英文字母组成，多用于安全领域和短URL生成。

Base62 索引表：

为了让哈希值表示起来尽可能短，我们可以将通过 MurmurHash 得到的 10 进制的哈希值转化成 62 进制

如何做呢？

还记得十进制转二进制的算法么，除二取余，然后倒序排列，高位补零。转62进制也类似，不断除以62取余数，然后倒序。

算法如下：

package com.example.demo;
import com.google.common.hash.Hashing;
import java.nio.charset.Charset;
public class ShortUrl {
    private static final String BASE62_CHARS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    public static void main(String[] args) {
        String longUrl = "https://cloud.tencent.com/developer/article/2378083";
        int hashValue = toHash(longUrl);
        String result = String.format("长链接：%s  hash值:%d",longUrl,hashValue);
        System.out.println(result);
        String base62Number = convertToBase62(hashValue);
        String shortUrl = String.format("hash值：%d  base62:%s",hashValue,base62Number);
        System.out.println(shortUrl);
     * 通过MurmurHash算法把长链接转换为32bit
     * @param longUrl
     * @return
    public static int toHash(String longUrl){
        int hashValue =  Hashing.murmur3_32().hashString(longUrl, Charset.defaultCharset()).asInt();
        return hashValue;
     * 10进制转换为62进制
     * @param decimalNumber
     * @return
    public static String convertToBase62(long decimalNumber) {
        StringBuilder sb = new StringBuilder();
        while (decimalNumber > 0) {
            int remainder = (int) (decimalNumber % 62);
            sb.insert(0, BASE62_CHARS.charAt(remainder));
            decimalNumber /= 62;