现在到处都可以看到短网址。许多短消息将包含短 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();
    }

以上就是关于《如何优化短链接性能？附解决方案》的全部内容了，感兴趣的话可以点击右侧直接使用哦！》》在线短链接生成器