高性能短链(短网址)算法

短网址介绍

短网址现在可以说是随处可见，很多短信内部都会包含短网址，点击短网址链接可以直接跳到对应的长链接地址，背后的原理其实很简单，服务端会存储短链和长链的对应关系，当接受到短链请求后，程序会去程序中查找对应的长链然后给浏览器返回给浏览器并且让浏览器重定向到长链地址，这就是整个流程

短链如何生成？

短链接地址一般都是域名+随机字符串，像下面这种

http://t.cn/2Die9G
http://t.cn/KePG6n

那怎么通过一个原始的长链接生成一个短链接呢，通过hash算法正好可以解决这个问题
Hash算法的特点是可以将一串任意长的地址转化成固定长度的hash值。比如MD5，SHA内部算法用到的就是Hash算法，

这两种算法反向破解难度很高，相应的其内部也要涉及到大量的计算。用来做短网址不需要考虑被破解的可能性

所以主要关注点在于算法的效率和冲突概率。
MurmurHash 是一种Hash算法，因为效率高和冲突概率低而出名，Redis，Google的guava，apache的commons-codec内部都有这种算法的实现

在这里我们选择MurmurHash中32bits的生成方式，我把Google的实现copy了下来

public class HashUtil {

    private static final int c1 = 0xcc9e2d51;
    private static final int c2 = 0x1b873593;
    private static final int r1 = 15;
    private static final int r2 = 13;
    private static final int m = 5;
    private static final int n = 0xe6546b64;

    private static final int DEFAULT_SEED = 0;


    private static int hash32(byte[] key, int seed) {
        int hash = seed;
        final int len = key.length;
        int i = 0;
        int k = 0;
        for (; i + 4 <= len; i += 4) {
            k = ((key[i + 3] & 0xff) << 24)
                    | ((key[i + 2] & 0xff) << 16)
                    | ((key[i + 1] & 0xff) << 8)
                    | (key[i] & 0xff);
            k *= c1;
            k = Integer.rotateLeft(k, r1);
            k *= c2;

            hash ^= k;
            hash = Integer.rotateLeft(hash, r2);
            hash = hash * m + n;
        }

        int k1 = 0;
        switch (len - i) {
            case 3:
                k1 = (key[i + 2] & 0xff) << 16;
            case 2:
                k1 |= (key[i + 1] & 0xff) << 8;
            case 1:
                k1 |= key[i] & 0xff;
                k1 *= c1;
                k1 = Integer.rotateLeft(k1, r1);
                k1 *= c2;
                hash ^= k1;
        }

        hash ^= len;
        hash ^= hash >>> 16;
        hash *= 0x85ebca6b;
        hash ^= hash >>> 13;
        hash *= 0xc2b2ae35;
        hash ^= hash >>> 16;

        return hash;
    }

    public static int hash32(String str) {
        return hash32(str.getBytes(), DEFAULT_SEED);
    }


}

我们用这个算法来对https://time.geekbang.org/column/article/80850 这个网址进行hash运算会得到结果：-1251719704
这是一串十进制的整型值，那怎么将它转换为字符串呢，我们可以将其转换为62进制，62进制常用的合法字符有0～9、a～z、A～Z 这样 62 个字符。
我将转换的算法也贴出来

private static String to62HEX(int num) {
        num = Math.abs(num);
        String chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

        StringBuilder sb = new StringBuilder();
        int remainder;

        while (num > 62 - 1) {
            remainder = Long.valueOf(num % 62).intValue();
            sb.append(chars.charAt(remainder));
            num = num / 62;
        }

        sb.append(chars.charAt(Long.valueOf(num).intValue()));
        return sb.reverse().toString();
    }

通过上面的算法可以将-1251719704转换为：1mI5tu，将计算出来的字符串和域名进行拼接

http://t.cn/1mI5tu

于是我们就成功的得到了，一个短链网址，将此短链和长链的映射保存即可

6位62进制的数可以表示568亿个数，已经够用了

出现Hash冲突怎么办

一般情况下为了防止数据库中出现相同短链，我们会用刚生成的短链作为查询条件去数据库中查询看是否有相同的短链，

如果有也不必着急，再看一下这个短链对应的长链我们正在处理的长链地址是否一样，如果一样说明传入的长链是重复的，那我们可以直接拿这个短链直接用，不用再进行存储一次。

如果不一样，那就说明发生了冲突，此时我们可以给长链加一串特殊的字符，然后再进行hash运算，如果此次不冲突我们可以将长链和这个特殊字符拼接起来和短链一并存储到数据库中
下次接受到短链请求后，把特殊字符截取掉，然后再进行重定向

判断Hash冲突优化

像上面那种方式判断是否产生Hash冲突其实效率不是很高，每次都要先查询一遍数据库，其实Hash冲突概率很低，在不发生冲突的时候就会产生性能上的损耗，那怎么优化呢

我们可以给表中的短链这一列加上唯一索引，我们在程序中计算完短链之后不用在查表，直接进行保存，如果成功，说明没有Hash冲突，如果有在判断长链是否也相同。然后再重新计算-保存...

这样做的好处就是在没有hash冲突的情况下总的sql语句执行次数会大大减少。只是在hash冲突的时候在进行重新运算即可，而且hash冲突概率本来就很小

还可以借助布隆过滤器来优化sql次数，先构建一个存储短链的布隆过滤器，每次 生成短链都用布隆过滤器判断是否重复，这种方式也可以减少sql的查询次数

总结

我来总结一下此算法的核心思路
通过高效率hash算法生成hash值，将hash值进行62进制转换然后就会得到一个短网址的后缀。
对于hash冲突的解决办法就是给网址拼上固定后缀在进行hash运算，直到不重复为止。

我大概测试了一下，生成100万个短链只需要200毫秒，效率还是很高的，测试代码如下

public class ShortUrlTest {

    public static void test(){
        int size = 1000000;
        String[] urls = new String[size];

        for (int i = 0; i < size; i++) {
            urls[i] = "https://time.geekbang.org/column/article/80850" + UUID.randomUUID().toString();
        }
        System.out.println("数据填充完成");

        long l = System.currentTimeMillis();
        for (String s : urls) {
            String shortUrl = ShortUrlGenerate.generate(s);
        }
        System.out.println(System.currentTimeMillis() - l);
    }

    public static void main(String[] args) {
        test();
    }

public class ShortUrlGenerate {

    public static String generate(String originalUrl) {
        return to62HEX(HashUtil.hash32(originalUrl));
    }


    /**
     * 10进制转26进制
     *
     * @param num
     * @return
     */
    private static String to62HEX(int num) {
        num = Math.abs(num);
        String chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

        StringBuilder sb = new StringBuilder();
        int remainder;

        while (num > 62 - 1) {
            remainder = Long.valueOf(num % 62).intValue();
            sb.append(chars.charAt(remainder));
            num = num / 62;
        }

        sb.append(chars.charAt(Long.valueOf(num).intValue()));
        return sb.reverse().toString();
    }

以上内容参考：
https://time.geekbang.org/column/article/80850