短链接生成

使用的什么方式生成短链接？

通过 Hash 算法将原始连接转换成一个 Hash 码，使用了 Google 出品的 MurmurHash 算法。因为生成的 Hash 码是十进制的，整体较长不利于短链接传播。为此，我们将十进制转换为 62 进制，也就是咱们最终的短链接。

1. MurmurHash 算法

对于选择哈希函数，有很多人可能会提到使用 MD5、SHA 等加密算法。其实我们并不关心反向解密的难度，更重要的是关注哈希的运算速度和冲突概率。

最终推荐使用由 Google 开发的 MurmurHash 算法。MurmurHash 是一种非加密型哈希函数，适用于一般的哈希检索操作。与其他流行的哈希函数相比，MurmurHash 在处理规律性较强的键时具有更好的随机分布特性。由于它是非加密型的，相比 MD5、SHA 等加密算法，MurmurHash 的性能要高得多（实际上是 MD5 等加密算法的十倍以上）。正是由于这些优点，尽管它于 2008 年问世，但目前已广泛应用于 Redis、MemCache、Cassandra、HBase、Lucene 等许多知名软件中。

我们使用 Hutool 里的工具类，不过他的底层也是使用的 Google 算法。

2. 进制转换

Base62 编码是将数据转换为只包含数字和字母的一种方法。它使用了 62 个字符，分别是 0-9、a-z、A-Z，可以作为 URL 短链接、文件名等场景的字符串表示，相对于 16 进制或 64 进制等其他编码，Base62 具有更高的可读性和稳定性。

private static final char[] CHARS = new char[]{
        '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
        'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
        'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'
};
private static final int SIZE = CHARS.length;

private static String convertDecToBase62(long num) {
    StringBuilder sb = new StringBuilder();
    while (num > 0) {
        int i = (int) (num % SIZE);
        sb.append(CHARS[i]);
        num /= SIZE;
    }
    return sb.reverse().toString();
}

假设我们使用的是 26 个字母的大小写，加上 10 个数字，那么对于短链接可以表示的最大组合数量为：

N = 4，组合数为 62 ^ 4 = 14_776_336，1477 万左右。

N = 5，组合数为 62 ^ 5 = 916_132_832，9.16 亿左右。

N = 6，组合数为 62 ^ 6 = 56_800_235_584，568 亿左右。

为什么会冲突？

哈希函数将输入的数据映射为一个固定长度的哈希值，而不同的输入可能会映射为相同的哈希值，这被称为哈希冲突。

在短链接生成过程中，原始长链接经过哈希函数进行计算，生成一个哈希值。如果两个不同的原始长链接经过哈希计算后得到相同的哈希值，那么它们将生成相同的短链接。

这种情况通常是由于哈希函数的输出空间有限，而输入空间却是无限的。因此，无论哈希函数的设计有多好，仍然存在一定的概率会出现冲突。

为什么使用原始链接和 UUID 生成短链接？

生成的短链接是需要保障在当前域名下唯一的，那这个唯一又如何体现呢？每次查询数据库中已有短链接数据来判断是否唯一么？性能有点低，我们使用了布隆过滤器来进行判断。

当我们发现冲突后，将原始长链接与一个随机生成的 UUID 字符串拼接，通过拼接后的内容继续查询布隆过滤器，直到不存在为止。

String originUrl = requestParam.getOriginUrl();
originUrl += UUID.randomUUID().toString();
String shorUri = HashUtil.hashToBase62(originUrl);

如果一直冲突怎么办？

一直冲突的概率是很小的，但是针对这种概率事件，我们就要考虑到极端情况。为此，我们在代码加了一个判断变量，如果超过指定次数，就抛出异常。

private String generateSuffix(ShortLinkCreateReqDTO requestParam) {
    int customGenerateCount = 0;
    String shorUri;
    while (true) {
        if (customGenerateCount > 10) {
            throw new ServiceException("短链接频繁生成，请稍后再试");
        }
        String originUrl = requestParam.getOriginUrl();
        originUrl += UUID.randomUUID().toString();
        shorUri = HashUtil.hashToBase62(originUrl);
        if (!shortUriCreateCachePenetrationBloomFilter.contains(createShortLinkDefaultDomain + "/" + shorUri)) {
            break;
        }
        customGenerateCount++;
    }
    return shorUri;
}