现在到处都可以看到短网址。许多短消息将包含短 URL。点击短网址链接可以直接跳转到对应的长链接地址。其背后的原理其实很简单。服务器将存储短链接和长链接。对应关系，当收到短链请求时，程序会去程序中找到对应的长链，然后返回给浏览器，让浏览器重定向到长链地址，这就是整个过程

要知道如何优化短链接性能，首先要了解：短链是如何产生的？

短链接地址一般为域名+随机字符串，如下所示

如何从原始长链接生成短链接？哈希算法正好可以解决这个问题

Hash算法的特点是可以将任意长度的地址串转换为固定长度的哈希值。比如MD5，SHA的内部算法就是Hash算法，

这两种算法的逆破解难度很大，对应的内部也涉及到大量的计算。用于短网址，不考虑被破解的可能性

所以主要关注的是算法的效率和冲突的概率。

MurmurHash 是一种 Hash 算法，以效率高、冲突概率低而著称。 Redis、Google 的 guava 和 apache 的 commons-codec 都有这个算法的内部实现

这里我们选择MurmurHash中32bits的生成方式去生成短链接，我复制了谷歌的实现代码

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);

    }

}

我们使用这个算法对这个 URL 进行哈希处理并得到结果：-1251719704

这是一串十进制整数值。如何将其转换为字符串？我们可以将其转换为十六进制。常用的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

通用解决方案（如何优化短链接性能）:

高性能短链接（短网址）算法，计算出来的字符串和域名可以拼接起来

这样我们就成功得到了一个短链URL，只需保存短链和长链的映射关系

6位十六进制数可以表示568亿个数字，足够了

如果有Hash冲突怎么办？

一般情况下，为了防止相同的短链出现在数据库中，我们会以新生成的短链作为查询条件来查询数据库，看是否存在相同的短链

如果有，别着急，看看我们处理的长链的地址与这条短链对应的长链是否相同。如果相同表示传入的长链是重复的，那么我们可以直接直接取这个短链。使用，无需再次储存。

如果不一样，说明有冲突。这时候我们可以在长链中加入一串特殊字符，然后进行哈希运算。如果这次没有冲突，我们可以用这个特殊字符拼接长链。与短链一起存储在数据库中

下次收到短链请求后，截断特殊字符再重定向

确定哈希冲突优化

以上方法判断是否发生哈希冲突，效率不是很高。您必须每次都查询数据库。事实上，哈希冲突的概率很低。当没有冲突时，就会有性能损失。如何优化它

我们可以为表中的短链列添加唯一索引。在程序中计算好短链后，我们就不需要查表直接保存了。如果成功，则说明不存在Hash冲突。是不是一样。然后重新计算——保存...

这样做的好处是，在没有哈希冲突的情况下，总的 SQL 语句执行次数会大大减少。只有发生哈希冲突时才需要重新操作，哈希冲突的概率很小。

还可以使用bloom filter优化sql条数。首先，构建一个存储短链的布隆过滤器。每次生成短链时，使用布隆过滤器判断是否重复。这种方法还可以减少sql查询次数

总结

我总结一下如何优化短链接性能，这个算法的核心思想

通过高效的哈希算法生成哈希值，将哈希值转换为十六进制，然后得到一个短网址后缀。

hash冲突的解决方法是给URL加一个固定的后缀，进行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();

    }