1.背景
本文对于过期删除，统计数据等拓展功能也不具体介绍，也不对网络重定向等进行介绍
作用，意义
节省网址长度，便于社交化传播
方便后台跟踪点击量、地域分布等用户统计
域名屏蔽，减少域名的暴露
隐藏真实url地址，审核做付费推广
结合生成二维码
功能设计
func genShort(longUrl) : 根据长连接生成短链接
func getLong(shortUrl): 根据短链接还原成长连接
算法思考：
1.是否可以不利用存储（db，redis等），存在一一映射，保证短链，长链之间的正向逆向映射
不存在，这样的话都不用压缩算法了
2.短链一般有几位
比如base62算法的话，62^6=500亿了
3.同一长网址生成短码是否应该相同
视情况而定
2.长链到短链
Hash算法
以MD5算法为例，把长链直接MD5得到32位字符串，再通过移位等操作能拿到短链
算法不详细介绍，可参照refer代码
但是这里类似hash会有一个问题是，即不同的长链，有能拿到同样的短链，这个时候需要解决冲突
解决冲突
比如原长连接加上随机字符串再重试，反复重试直到短链没有用过，即没有产生冲突
业界有更合适的发号器算法,避免了冲突
发号器算法
发号器里面的号即为一个数字ID
这里其实换一种思路，不要用长链作为入参，可以把一个唯一ID作为入参
如何选择唯一ID:
1.比如mysql自增主键
2.前面自己写的文章ID分布式生成器
映射算法：
1.可参考base62编码,即 [0-9a-zA-Z]字符集，能把唯一的ID换成62进制的编码，也会是唯一的
这样的映射关系保证了输入ID和输出62进制串的一一映射关系，就不会有hash算法中的解决冲突，重试的问题
3.短链还原长链
即根据db里面里面找到信息找，找到short_url -> long_url等
4.思考
发号器算法如何避免重复的
之前看过用hash的，毕竟解决冲突这种事情，要实现，重试成本，比如再加上当前时间戳重试MD5重试几次等等
这里发号器的思路主要是通过唯一ID进行1:1的映射算法（base62），保证短链也是唯一
同一网址生成短码是否应该相同
这里可以相同可以不同
相同，根据严格程度分为两种：
1.严格：需要额外的存储成本保证long_url到短链接的映射关系，如建立long_uri为db索引，保证相同长链生成的短链都相同
2.宽松：提供最近一小时LFU的长链到短链的映射，保证最近一段时间相同的长链生成同样的短链
不同：
看似不够完美，同样的长链每次生成短链不同，和我们通常期望的“幂等性”不一样，但是实现以及速度上都是最方便的
5.refer
https://pathbox.github.io/2018/02/22/short-url-build-system/
网友评论