如何实现一个短地址服务

短网址服务经常会用到，这是一个看似简单，但内含不少小技巧的服务，想要做好可不太容易。

哈希算法：短网址服务需要重点考虑的问题是哈希算法的计算速度和冲突概率，MurmurHash 算法是一个应用比较广泛的哈希算法，可以选择这个算法

如何更短：将哈希算法随机生成的数字转换为62进制的值，62进制可以用[0-9a-zA-Z]表示，最终生成的链接会更短

• 如何解决哈希冲突

  • 首先从数据库中查询原始网址和短网址的对应关系
  • 如果短网址冲突，那么再比较原始网址是否相同
  • 如果相同，说明已经生成过，可以直接返回这个短网址
  • 如果不同我们可以对原始网址拼接一个特定的字符串标识，进行再次的哈希计算，拿到一个新的短网址存储下来，这样计算哈希冲突的概率是非常低的，取用的时候将特殊字符去掉即可

• 如何优化哈希算法生成短网址的性能

  • 性能损耗的点：冲突查找，加索引加快查找速度即可
  • 在大多数时候，哈希计算并不会出现冲突，并且短网址是唯一的，这个时候就可以加唯一索引，不检查是否冲突，直接插入数据，报错捕获后再进行查找处理，这样可以减少大量的查询操作
  • 还可以使用布隆过滤器来实现短网址是否冲突的查找操作，十亿的布隆过滤器占用空间也就是125M左右内存空间

• 使用自增id生成短网址

  • 相同的原始网址可能会对应不同的短网址，不想出现这种状况就需要去库里面查询，短网址和原始网址都需要加索引，查到之后将已经生成的短网址返回
  • 使用高性能的id生成器
    • 给id生成器装多个前置发号器，不断批量的给发号器发送id号码，来应对并发的访问
    • 使用多个id生成器，为了保证id不重复，每个生成器的生成规则要略有不同