⼀个序列md5加密是唯⼀的吗_⾯试官让我利⽤哈希算法、布
隆过滤器设计⼀个短链系统
本⽂将会从以下⼏个⽅⾯来讲解，每个点包含的信息量都不少，相信⼤家看完肯定有收获
短链有啥好处，⽤长链不⾹吗
短链跳转的基本原理
短链⽣成的⼏种⽅法
⾼性能短链的架构设计
为啥要⽤短链表⽰，直接⽤长链不⾏吗，⽤短链的话有如下好外
1、链接变短，在对内容长度有限制的平台发⽂，可编辑的⽂字就变多了
最典型的就是微博，限定了只能发 140 个字，如果⼀串长链直接怼上去，其他可编辑的内容就所剩⽆⼏了，⽤短链的话，链接长度⼤⼤减少，⾃然可编辑的⽂字多了不少。
再⽐如⼀般短信发⽂有长度限度，如果⽤长链，⼀条短信很可能要拆分成两三条发，本来⼀条⼀⽑的短信费变成了两三⽑，何苦呢。另外⽤短链在内容排版上也更美观。
2、我们经常需要将链接转成⼆维码的形式分享给他⼈，如果是长链的话⼆维码密集难识别，短链就不存在这个问题了。
3、链接太长在有些平台上⽆法⾃动识别为超链接
如图⽰，在钉钉上，就⽆法识别如下长链接，只能识别部分，⽤短地址⽆此问题
短链跳转的基本原理
从上⽂可知，短链好处多多，那么它是如何⼯作的呢。我们在浏览器抓下包看看
可以看到请求后，返回了状态码 302(重定向)与 location 值为长链的响应，然后浏览器会再请求这个长链以得到最终的响应，整个交互流程图如下
主要步骤就是访问短⽹址后重定向访问 B，那么问题来了，301 和 302 都是重定向，到底该⽤哪个，这⾥需要注意⼀下 301 和 302 的区别
301，代表 永久重定向，也就是说第⼀次请求拿到长链接后，下次浏览器再去请求短链的话，不会向短⽹址服务器请求了，⽽是直接从浏览器的缓存⾥拿，这样在 server 层⾯就⽆法获取到短⽹址的点击数了，如果这个链接刚好是某个活动的链接，也就⽆法分析此活动的效果。所以我们⼀般不采⽤ 301。
302，代表 临时重定向，也就是说每次去请求短链都会去请求短⽹址服务器(除⾮响应中⽤ Cache-Control 或 Expired 暗⽰浏览器缓存)，这样就便于 server 统计点击数，所以虽然⽤ 302 会给 server 增加⼀点压⼒，但在数据异常重要的今天，这点代码是值得的，所以推荐使⽤ 302！
短链⽣成的⼏种⽅法
1、哈希算法
怎样才能⽣成短链，仔细观察上例中的短链，显然它是由固定短链域名 + 长链映射成的⼀串字母组成，那么长链怎么才能映射成⼀串字母呢，哈希函数不就⽤来⼲这事的吗，于是我们有了以下设计思路
那么这个哈希函数该怎么取呢，相信肯定有很多⼈说⽤ MD5，SHA 等算法，其实这样做有点杀鸡⽤⽜⼑了，⽽且既然是加密就意味着性能上会有损失，我们其实不关⼼反向解密的难度，反⽽更关⼼的是哈希的运算速度和冲突概率。
能够满⾜这样的哈希算法有很多，这⾥推荐 Google 出品的 MurmurHash 算法，MurmurHash 是⼀种⾮加密型哈希函数，适⽤于⼀般的哈希检索操作。与其它流⾏的哈希函数相⽐，对于规律性较强的 key，MurmurHash 的随机分布特征表现更良好。⾮加密意味着着相⽐MD5，SHA 这些函数它的性能肯定更⾼(实际上性能是 MD5 等加密算法的⼗倍以上)，也正是由于它的这些优点，所以虽然它出现于2008，但⽬前已经⼴泛应⽤到 Redis、MemCache、Cassandra、HBase、Lucene 等众多著名的软件中。
画外⾳：这⾥有个⼩插曲，MurmurHash 成名后，作者拿到了 Google 的 offer，所以多做些开源的项⽬，说不定成名后你也能不经意间收到 Google 的 offer ^_^。
如何缩短域名？
有⼈说⼈这个域名还是有点长，还有⼀招，3002604296 得到的这个哈希值是⼗进制的，那我们把它转为 62 进制可缩短它的长度，10进制转 62 进制如下：
画外⾳：6 位 62 进制数可表⽰ 568 亿的数，应付长链转换绰绰有余
如何解决哈希冲突的问题？
既然是哈希函数，不可避免地会产⽣哈希冲突(尽管概率很低)，该怎么解决呢。
我们知道既然访问访问短链能跳转到长链，那么两者之前这种映射关系⼀定是要保存起来的，可以⽤ Redis 或 Mysql 等，这⾥我们选择⽤
Mysql 来存储。表结构应该如下所⽰
CREATE TABLE `short_url_map` (  `id` int(11) unsigned NOT NULL AUTO_INCREMENT,  `lurl` varchar(160) DEFAULT NULL COMMENT '长地址',  `surl` varcha 于是我们有了以下设计思路。
1. 将长链(lurl)经过 MurmurHash 后得到短链。
2. 再根据短链去 short_url_map 表中查看是否存在相关记录，如果不存在，将长链与短链对应关系插⼊数据库中，存储。
3. 如果存在，说明已经有相关记录了，此时在长串上拼接⼀个⾃定义好的字段，⽐如「DUPLICATE」，然后再对接接的字段串「lurl +
DUPLICATE」做第⼀步操作，如果最后还是重复呢，再拼⼀个字段串啊，只要到时根据短链取出长链的时候把这些⾃定义好的字符
串移除即是原来的长链。
以上步骤显然是要优化的，插⼊⼀条记录居然要经过两次 sql 查询(根据短链查记录，将长短链对应关系插⼊数据库中)，如果在⾼并发下，
显然会成为瓶颈。
画外⾳：⼀般数据库和应⽤服务(只做计算不做存储)会部署在两台不同的 server 上，执⾏两条 sql 就需要两次⽹络通信，这两次⽹络通信
与两次 sql 执⾏是整个短链系统的性能瓶颈所在！
所以该怎么优化呢
1. ⾸先我们需要给短链字段 surl 加上唯⼀索引
2. 当长链经过 MurmurHash 得到短链后，直接将长短链对应关系插⼊ db 中，如果 db ⾥不含有此短链的记录，则插⼊，如果包含
了，说明违反了唯⼀性索引，此时只要给长链再加上我们上⽂说的⾃定义字段「DUPLICATE」，重新 hash 再插⼊即可，看起来在违
反唯⼀性索引的情况下是多执⾏了步骤，但我们要知道 MurmurHash 发⽣冲突的概率是⾮常低的，基本上不太可能发⽣，所以这种
⽅案是可以接受的。
当然如果在数据量很⼤的情况下，冲突的概率会增⼤，此时我们可以加布隆过滤器来进⾏优化。
⽤所有⽣成的短⽹址构建布隆过滤器，当⼀个新的长链⽣成短链后，先将此短链在布隆过滤器中进⾏查，如果不存在，说明 db ⾥不存在
此短⽹址，可以插⼊！
画外⾳：布隆过滤器是⼀种⾮常省内存的数据结构，长度为 10 亿的布隆过滤器，只需要 125 M 的内存空间。
种子哈希转换链接综上，如果⽤哈希函数来设计，总体的设计思路如下
⽤哈希算法⽣成的短链其实已经能满⾜我们的业务需求，接下来我们再来看看如何⽤⾃增序列的⽅式来⽣成短链
2、⾃增序列算法
我们可以维护⼀个 ID ⾃增⽣成器，⽐如 1，2，3 这样的整数递增 ID，当收到⼀个长链转短链的请求时，ID ⽣成器为其分配⼀个 ID，再将其转化为 62 进制，拼接到短链域名后⾯就得到了最终的短⽹址，那么这样的 ID ⾃增⽣成器该如何设计呢。如果在低峰期发号还好，⾼并发下，ID ⾃增⽣成器的的 ID ⽣成可能会系统瓶颈，所以它的设计就显得尤为重要。
主要有以下四种获取 id 的⽅法
1、类 uuid
简单地说就是⽤ UUID uuid = UUID.randomUUID(); 这种⽅式⽣成的 UUID，UUID(Universally Unique Identifier)全局唯⼀标识符，是指在⼀台机器上⽣成的数字，它保证对在同⼀时空中的所有机器都是唯⼀的，但这种⽅式⽣成的 id ⽐较长，且⽆序，在插⼊ db 时可能会频繁导致页分裂，影响插⼊性能。
2、Redis
⽤ Redis 是个不错的选择，性能好，单机可⽀撑 10 w+ 请求，⾜以应付⼤部分的业务场景，但有⼈说如果⼀台机器扛不住呢，可以设置多台嘛，⽐如我布置 10 台机器，每台机器分别只⽣成尾号0，1，2，... 9 的 ID, 每次加 10 即可，只要设置⼀个 ID ⽣成器代理随机分配给发号器⽣成 ID 就⾏了。
不过⽤ Redis 这种⽅案，需要考虑持久化(短链 ID 总不能⼀样吧)，灾备，成本有点⾼。
3、Snowflake
⽤ Snowflake 也是个不错的选择，不过 Snowflake 依赖于系统时钟的⼀致性。如果某台机器的系统时钟回拨，有可能造成 ID 冲突，或者ID 乱序。
4、Mysql ⾃增主键
这种⽅式使⽤简单，扩展⽅便，所以我们使⽤ Mysql 的⾃增主键来作为短链的 id。简单总结如下：
那么问题来了，如果⽤ Mysql ⾃增 id 作为短链 ID，在⾼并发下，db 的写压⼒会很⼤，这种情况该怎么办呢。
考虑⼀下，⼀定要在⽤到的时候去⽣成 id 吗，是否可以提前⽣成这些⾃增 id ?
⽅案如下：
设计⼀个专门的发号表，每插⼊⼀条记录，为短链 id 预留 (主键 id * 1000 - 999) 到 (主键 id * 1000) 的号段，如下
发号表：url_sender_num
如图⽰：tmp_start_num 代表短链的起始 id，tmp_end_num 代表短链的终⽌ id。
当长链转短链的请求打到某台机器时，先看这台机器是否分配了短链号段，未分配就往发号表插⼊⼀条记录，则这台机器将为短链分配范围在 tmp_start_num 到 tmp_end_num 之间的 id。从 tmp_start_num 开始分配，⼀直分配到 tmp_end_num，如果发号 id 达到了
tmp_end_num，说明这个区间段的 id 已经分配完了，则再往发号表插⼊⼀条记录就⼜获取了⼀个发号 id 区间。
画外⾳：思考⼀下这个⾃增短链 id 在机器上该怎么实现呢， 可以⽤ redis, 不过更简单的⽅案是⽤ AtomicLong，单机上性能不错，也保证了并发的安全性，当然如果并发量很⼤，AtomicLong 的表现就不太⾏了，可以考虑⽤ LongAdder，在⾼并发下表现更加优秀。
整体设计图如下