写在前面：
基于非加密型MurmurHash算法，BLOOM过滤器，数据库唯一索引确保短链的生成是唯一的，且综合考虑使用强随机的UUIDv4版本(默认)使得hash分布更加均匀。实测本机单线程Java环境下可支持1s内生成130w左右的短链数量。
大概流程：
首先我们会使用UUID默认的uuid.randomuuid.tostring,生成一个长度128位的字符串。例如：
Generated UUID: 7a8a3461-34bf-426a-ba76-1c0541e03fdf
然后我们把这个UUID和我们的原始链接例如"https://www.baidu.com"拼接:
"7a8a3461-34bf-426a-ba76-1c0541e03fdfhttps://www.baidu.com"
对这一串进行murmurhash32()得出一个32位的计算值:
1789923922
然后对这个值进行base62之后:
1x8Kyg
兜底：
极小概率下我们生成的短链会重复，我们使用布隆过滤器来兜底，布隆过滤器返回不存在那就说明这个链接一定不存在，存在hash的冲突假设在1%，那么我们的568亿也还剩下568*0.99=562.32亿可用。
一定能生成568亿个短链吗？如果不能如何解决？
虽然 6 位 Base62 的编码空间为 568 亿，但由于 MurmurHash32 只能生成 42 亿个唯一的哈希值，因此 实际存储的短链数量上限为 42 亿。
采用MurmurHash128或者64，生成之后截取前6位，都有可能发生冲突，需判断（布隆过滤器）。
存储1亿条短链：
假设一条短链数据133字节，包含短链的各种描述信息。
133 字节/条 × 100,000,000 条 = 13,300,000,000 字节 ≈ 12.38 GB
布隆过滤器的配置
hashIterations（哈希函数数量） ：10
expectedInsertions（预期插入元素数量） ： 100000000
falseProbability（误判率）： 0.001
总大小： 171.39mb
参考计算网站：https://hur.st/bloomfilter/
发散思考：腾讯存储40亿qq号，限制1GB，能用布隆过滤器吗？
不能。存储40亿个元素简单的bitmap需要：476.84 MB
复杂的布隆过滤器需要4.79 GB
原因：布隆过滤器需要增加位数组大小来避免哈希冲突，底层是通过多个哈希函数来实现的，因为用了多个哈希函数，比如
str1计算得出槽位在1，2，3；
str2计算得出槽位在2，3，4；
只要有一位不同就可以说明两个str不同。
鉴于这个原理我们就要扩大数组大小，这样才能更加均匀的分布。
130w怎么测出来的？
一下数据均基于本机环境测试。R5-5600H 6核心12线程 4GHZ
1s内murmurhash32可计算大约5000万次
1s内uuid.randomuuid可生成大约166万次
综合之后：
第一次测试：
单线程测试中...
单线程 1 秒内 MurmurHash32 + Base62 操作次数: 1299483
多线程测试中...
多线程 1 秒内 MurmurHash32 + Base62 操作次数: 1527258
第二次测试：
单线程测试中...
单线程 1 秒内 MurmurHash32 + Base62 操作次数: 1422073
多线程测试中...
多线程 1 秒内 MurmurHash32 + Base62 操作次数: 1543755
第三次测试：
单线程测试中...
单线程 1 秒内 MurmurHash32 + Base62 操作次数: 1418979
多线程测试中...
多线程 1 秒内 MurmurHash32 + Base62 操作次数: 1558930综合来看单线程下在130w-140w
这里给出测试代码：
public class MurmurHashBenchmark {
private static final char[] CHARS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".toCharArray();
private static final int SIZE = CHARS.length;
private static final long TEST_DURATION_NANOS = 1_000_000_000L; // 1 秒 = 1_000_000_000 纳秒
public static void main(String[] args) {
System.out.println("单线程测试中...");
int singleThreadOps = testSingleThread();
System.out.println("单线程 1 秒内 MurmurHash32 + Base62 操作次数: " + singleThreadOps + "\n");
System.out.println("多线程测试中...");
int multiThreadOps = testMultiThread();
System.out.println("多线程 1 秒内 MurmurHash32 + Base62 操作次数: " + multiThreadOps);
}
/**
* 单线程测试：计算 1 秒内能执行多少次 MurmurHash32 + Base62
*/
private static int testSingleThread() {
long startTime = System.nanoTime();
int count = 0;
while (System.nanoTime() - startTime < TEST_DURATION_NANOS) {
String input = UUID.randomUUID().toString();
String base62Hash = hashToBase62(input);
count++;
}
return count;
}
/**
* 多线程测试：计算 1 秒内能执行多少次 MurmurHash32 + Base62
*/
private static int testMultiThread() {
AtomicInteger count = new AtomicInteger(0);
long startTime = System.nanoTime();
ForkJoinPool.commonPool().submit(() ->
IntStream.range(0, Runtime.getRuntime().availableProcessors())
.parallel()
.forEach(i -> {
while (System.nanoTime() - startTime < TEST_DURATION_NANOS) {
String input = UUID.randomUUID().toString();
String base62Hash = hashToBase62(input);
count.incrementAndGet();
}
})
).join();
return count.get();
}
/**
* MurmurHash32 计算 + Base62 编码
*/
private static String hashToBase62(String str) {
int i = MurmurHash.hash32(str);
long num = i < 0 ? Integer.MAX_VALUE - (long) i : i;
return convertDecToBase62(num);
}
/**
* 10 进制转 Base62
*/
private static String convertDecToBase62(long num) {
StringBuilder sb = new StringBuilder();
while (num > 0) {
sb.append(CHARS[(int) (num % SIZE)]);
num /= SIZE;
}
return sb.reverse().toString();
}
}