雪花算法替代MurmurHash后的提升（短链接项目中的唯一性设计）

短链接服务的核心功能，是将一个长网址（比如几百个字符的 URL）转换成一个短码，用户访问短码时，服务端会将其重定向回原始的长链接。
考虑到快速生成（防止高并发下，性能变差）和长变短的处理，这里想到了MurmurHash算法+62进制

MurmurHash算法

核心操作是乘法和位运算：

public static int murmur32(byte[] data, int seed) { int len = data.length; int h = seed ^ len; int i = 0; while (len >= 4) { int k = (data[i] & 0xFF) | ((data[i+1] & 0xFF) << 8) | ((data[i+2] & 0xFF) << 16) | ((data[i+3] & 0xFF) << 24); k = k * 0x5bd1e995; k = k ^ (k >> 24); k = k * 0x5bd1e995; h = h * 0x5bd1e995 ^ k; i += 4; len -= 4; } // 处理剩余字节... h = h ^ (h >> 13); h = h * 0x5bd1e995; h = h ^ (h >> 15); return h; }

处理完会得到一个32位的数字，之后进行62进制的处理，能得到一个6位的短码，符合短链接的要求

之后想到了链接的唯一性，如果两个链接通过处理后得到了同一段短码，那么项目就会出错，检查了MurmurHash算法，发现最大输出空间约为43亿，无穷大输入时必然有重复的可能，要么在后续加上兜底处理，要么更改算法

这里采取用雪花算法来替代MurmurHash

雪花算法（Snowflake）是Twitter开源的分布式ID生成算法，生成的ID是一个64位的long整数，结构如下：

这样保证了唯一转换第一步的唯一性，之后再用62进制转换这个64位的数字就能得到一个短码

此时再考虑重复的可能也就只能出现在进制转换了，而62进制有62^6 ≈ 568亿种组合，假设传来1亿数据，也只占1/568，尽管这568亿数据空间的利用率不是100%，对比MurmurHash也是大提升，既保持了高性能，也处理了唯一性问题

谢谢观看