Guava 的 MurmurHash 测试与封装简介Guava 自带 MurmurHash 算法直接调用生成 32 位哈希值再封装到工具类背景短链码用 MurmurHash 生成Guava、Jedis 等框架已经集成了这个算法不用从头开发会用即可面试一般不会让你手写 MurmurHash单元测试随机拼接 URL生成 32 位哈希值TestpublicvoidtestMurmurHash(){for(inti0;i50;i){intnum1random.nextInt(1000000);intnum2random.nextInt(1000000);intnum3random.nextInt(1000000);StringoriginalUrlnum1xdclassnum2.netnum3;longmurmur3_32Hashing.murmur3_32().hashUnencodedChars(originalUrl).padToLong();System.out.println(murmur3_32murmur3_32);}}关键 APIAPI说明Hashing.murmur3_32()Guava 的 32 位 MurmurHash 函数com.google.common.hash.HashinghashUnencodedChars(url)对字符串计算哈希返回HashCodepadToLong()把HashCode转成 long测试结果输出类似3638367641、2660229547的 long 值30 多亿32 位哈希值最多 40 多亿个数据量大了冲突率就高可以扩大位数封装到公共模块的CommonUtil/***murmur hash算法*paramparam*return*/publicstaticlongmurmurHash32(Stringparam){longmurmurHash32Hashing.murmur3_32().hashUnencodedChars(param).padToLong();returnmurmurHash32;}为什么要封装成工具类以后可能换成其他哈希算法只需改工具类调用方不用动解耦避免牵一发而动全身短链生成组件 ShortLinkComponent简介组件传入原始 URL先算 MurmurHash再把哈希值转成 62 进制得到短链码整体流程传入原始 URL返回短链码组件加Component交给 Spring 扫描long 型哈希值不直接当短链码转成更短的字符串节省空间图中红色节点是本节新增的进制转换绿色是最终得到的短链码组件代码ComponentpublicclassShortLinkComponent{/***62个字符*/privatestaticfinalStringCHARS0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ;/***生成短链码*paramparam*return*/publicStringcreateShortLinkCode(Stringparam){longmurmurhashCommonUtil.murmurHash32(param);// 进制转换StringcodeencodeToBase62(murmurhash);returncode;}/***10进制转62进制*paramnum*return*/privateStringencodeToBase62(longnum){// StringBuffer线程安全StringBuilder线程不安全StringBuffersbnewStringBuffer();do{inti(int)(num%62);sb.append(CHARS.charAt(i));numnum/62;}while(num0);Stringvaluesb.reverse().toString();returnvalue;}}10 进制转 62 进制除 62 取余余数对应CHARS里的字符图中橙色节点容易漏余数是从低位往高位追加的最后要反转注意点CHARS是 62 个字符0~9 共 10 个 小写 a~z 大写 A~ZStringBuffer线程安全内部加锁StringBuilder线程不安全面试常问这里sb是方法内的局部变量方法栈每个线程独享用StringBuilder也是线程安全的ShortLinkComponent 测试与疑惑解答简介随机 URL 测试短链码生成并解释为什么用 62 进制、短链码是不是固定 6 位测试前的准备测试类加RunWith(SpringRunner.class)、SpringBootTest(classes LinkApplication.class)注入ShortLinkComponent短链服务还没有启动类复制账号服务的启动类改名LinkApplication启动类要放在根包下放到其他目录会有问题注解照搬MapperScan、EnableTransactionManagement、EnableFeignClients、EnableDiscoveryClient、SpringBootApplication第一次运行报错Data sources cannot be empty原因短链服务依赖公共模块公共模块带了 sharding-jdbc启动时会检查数据源配置解决先把账号服务的 shardingsphere 数据源配置复制过来库表还没建只是让项目能启动层级不要放错刚搭微服务时引入 MyBatis 相关依赖就报错也多是因为没配 jdbc 连接单元测试/***测试短链平台*/TestpublicvoidtestCreateShortLink(){for(inti0;i100;i){intnum1random.nextInt(10);intnum2random.nextInt(1000000);intnum3random.nextInt(1000000);StringoriginalUrlnum1xdclassnum2.netnum3;StringshortLinkCodeshortLinkComponent.createShortLinkCode(originalUrl);log.info(originalUrl:originalUrl, shortLinkCodeshortLinkCode);}}测试结果示例原始 URL短链码5xdclass2349606.net68491654gOpNV2xdclass3182358.net708873413YUz0xdclass3940745.net5761123gWIeY9xdclass361362.net6243601yciwC原始链接再长生成的短链码也都在 5~6 位之间为什么用 62 进制不用 64 进制维度62 进制64 进制字符数字 小写字母 大写字母还有/、这样的符号放进 URL可以不符合正常 URL 的字符10 进制转 62 进制可以缩短字符6 位字符就有 560 亿个组合已经满足业务需求短链码是不是固定 6 位不是看业务情况有些短链还会加入其它特殊字符例京东短信里的短链形如3.cn/10-xxxxxx有数字前缀和横杠共 9 位左右横杠位置也不固定阿里云、淘宝的短链也不是固定位数按项目数据量定后续做分库分表改造短链码里要加入库表的基因组件注释里的返回值写的是“db 编码 6 位短链编码”不必拘泥位数和字符集满足业务需求就行量更大就加长到 7、8 位或加入更多字符面试/考试记忆点短链码 原始 URL 先做 MurmurHash再把哈希值转成 62 进制Guava 自带 MurmurHashHashing.murmur3_32().hashUnencodedChars(url).padToLong()32 位哈希值最多 40 多亿个数据量大了冲突率高可以扩大位数哈希算法封装进工具类以后换算法只改一处10 进制转 62 进制除 62 取余查字符表循环到 0 后反转用 62 进制不用 64 进制是因为 64 进制有/、不适合放进 URL为什么转 62 进制缩短字符6 位就有 560 亿个组合量更大就用 7、8 位短链码不一定是固定 6 位分库分表后还要加入库表基因
