雪花算法替代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[i1] 0xFF) 8) | ((data[i2] 0xFF) 16) | ((data[i3] 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也是大提升既保持了高性能也处理了唯一性问题谢谢观看