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