算法实战5 - 用学过的数据结构和算法实现一个短网址系统

许多网站都提供短网址服务，简单来说，这个服务就是将一个较长的网址转化成一个更短的网址。我们只要访问这个短网址，就相当于访问原始的网址。比如下面的两个网址，尽管不同，但是都会跳转到同一个网址中，其中第二个网址就是通过新浪的短网址服务生成的：

原始网址：https://github.com/wangzheng0822/ratelimiter4j
短网址：http://t.cn/EtR9QEG

这个功能非常简单，我们来看一看在这个功能中，会使用哪些数据结构和算法。

短网址

短网址的服务过程如下： 短网址.jpg

实际上，浏览器会先访问短网址服务，通过服务获取原网址，然后通过原始网址进入访问页面。

当然，这些不是重点。重点是：如何将长网址转化成短网址？

1.通过哈希算法生成短网址

• 我们可以使用哈希算法将一个较长的网址转化成较短的内容。

• 这里使用 MurmerHash 算法，将网址转化成 32bit 的数据（也可以变成 128bit），由于它不考虑反解的难度，所以它的计算速度相对较快。

1.1让短网址更短

32bit 的信息如果转换成数字还是比较长的（例子中的网址可以转换为 181338494），我们可以进一步缩短它。

我们可以将那个数字转换成 62进制 （26个大写字母 + 26个小写字母 + 10个数字），进一步减小网址长度： 计算结果为cgSqq

1.2解决哈希冲突

既然是使用哈希函数，就一定会面临哈希冲突，下面，我们看一看该如何解决哈希冲突的问题。也就是如果两个网址得到的哈希值相同该怎么办：

• 向数据库（假设为MySQL数据库）中添加一条数据 ：哈希值 → 原网址
• 将哈希值字段设置为 “不重复” 字段
• 如果写入失败，则为原网址添加一段标识符，然后再进行哈希，得到一个新的哈希值
• 当请求这个短网址时，通过短网址找到相应的数据，将数据中的标识符去掉，然后返回原网址。

当然，你也可以使用布隆过滤器进行预先判重。

2.通过 ID 生成器生成短网址

我们可以维护一个 ID 自增生成器。它可以生成1、2、3...这样的整数 ID。

当服务器收到原网址的转化请求之后，向生成器中取一个号码，然后直接将这个 ID 转化成相应的 62 进制表示法的字符串。将这个字符串拼接得到服务器域名之后，就形成了最终的短网址。

由于生成器是自增、不重复的，所以不存在短网址转为多个原网址的情况。但是这带来了新的问题：

2.1相同的原始网址可能会对应不同的短网址

解决这个问题，有两种思路：

• 对重复问题不做处理。没错，我们只要使用短网址能够正确找到原网址即可，至于 一个原网址 被分配 多个短网址，这种情况并不影响用户使用。
  当然，这会造成一丢丢空间浪费。

• 第二种思路，和使用哈希处理冲突的思想一样。在生成短网址之前，先在数据库中查找原网址，如果原网址存在，那么就直接使用已经映射好的短网址即可。
  当然，这需要在数据库中维护 原网址 的索引。这会占用更多存储空间，还会影响插入、删除的性能。

2.2如何实现高性能 ID 生成器

实现一个单纯的 ID生成器 非常简单，但是面对大量频繁的 ID 申请，还是有些力不从心的。（由于计数器必须保证 ID 不重复，所以在多线程的情况下，需要加锁操作。）

对这个问题，我们有两种思路：

• 使用之前讲到的 Disruptor 的方法，给 ID生成器 装多个前置发号器。批量的为前置发号器发送 ID号码。当我们接收到短网址生成请求的时候，从某个前置发号器中取号码。
  

  这样，可以明显提高并发发号的能力。 ID生成-前置发号器.jpg

• 第二种解决思路是，使用多个 ID生成器，每个生成器按照规则生成指定的不重复的号码。比如，设置是个生成器，分别生成尾号为 0、1、2...
  

  这样也可以提高生成效率： ID生成-多个生成器.jpg

总结

今天我们介绍了两种短网址服务的实现方法：

第一种实现思路是通过哈希算法生成短网址。我们采用计算速度快、冲突概率小的 MurmurHash 算法，并将计算得到的 10 进制数，转化成 62 进制表示法，进一步缩短短网址的长度。对于哈希算法的哈希冲突问题，我们通过给原始网址添加特殊前缀字符，重新计算哈希值的方法来解决。

第二种实现思路是通过 ID 生成器来生成短网址。我们维护一个 ID 自增的 ID 生成器，给每个原始网址分配一个 ID 号码，并且同样转成 62 进制表示法，拼接到短网址服务的域名之后，形成最终的短网址。

---

以上就是本节的全部内容

注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我使用了大量的原文、代码和截图，如果想要了解具体内容，可以前往极客时间