网址短链接在线生成地址：https://www.aifabu.com/  (稳定  快速  安全  免费)

短链接，顾名思义，就是将长URL缩减为很短的URL，用户通过访问这个短URL就可以重定向到原来的长URL（还原）。这样既能达到易记易转换的目的，又能隐藏链接参数，非常利于运营人员和推广者。

1.实现一个算法，可以直接将100个字符左右的长URL缩减到10位以内，并且可以恢复到原来的样子，可以逆向

不可能。不可能对所有可能的长链接实现一一对应。会有碰撞。多个长链接对应一个短链接，因此是不可逆的。

2.实现长地址转短地址的算法，无需逆运算，将粗细对应关系存入数据库

不可能。本质没有改变（长链接的数量远少于长链接的数量），只要有足够长的链接，就不可避免地会发生碰撞

3.使用哈希算法，生成的短链接碰撞后，添加1、2、3

在短链接之后

在数学和逻辑上可行，生产应用是不可行的。效率不可控地下降。算法估计短URL后，经过哈希冲突后，生成多个xx1、xx2、xx3....xx20...的短URL。长宽对应的数字不可控，会降低搜索效率。

4.随机生成一个短地址，到数据库中查找之前是否使用过，然后随机化，直到随机找到一个未使用的短地址并存入数据库

在数学和逻辑上可行，生产应用是不可行的。对每一代都进行必要的完整查询操作绝对不是一种选择。

5. 维护大量数据，预生成超出实际生产使用的短网址，直接发出API读取，同步更改短网址状态。

物理和逻辑上可行，生产应用程序的低可用性。具体来说，redis 或 db 中的批量生成虽然是两种完全不同的实现方式。

如果是redis，需要把短网址全部放出来吗？否则，你怎么知道短网址是否唯一？如果满了，那么应该严格保证redis的可用性。为了高可用性，需要多节点同步来维护完整的数据。这个过程不是那么容易做到的；如果是db，那么肯定有大量的并发锁，也就意味着大量的读写，这只是对数据库的一个测试。

创建发件人。每次新的长 URL 进入时，我们都会增加它并返回新值。第一个 URL 返回“”，第二个返回“/1”。

详细问题：短网址的恢复跳转使用301还是302？

301 是永久重定向，302 是临时重定向。

短地址即使生成也不会改变，所以使用301符合http语义。同时，浏览器会为301请求保存常年缓存，减轻服务器压力；而301请求会在一定程度上提升网站的SEO。但是在很多情况下，当我们需要对界面点击或者用户行为进行一些业务监控处理时，301似乎不合适（浏览器直接根据缓存数据跳转），所以在很多业务中使用302比较合适情景。 

即使达到10亿（Billion），转换后的62位字符也只是6位字符，所以宽度基本忽略不计，这个范围就够了。

对应的数据要放在硬盘上，不能每天系统重启后重新排列数字，所以可以存储在mysql等数据库中。如果数据量小，qps低，可以直接使用数据库自增外键实现。

根据上述发行方政策，不保证长链接与短链接之间存在一一对应关系。如果同一 URL 连续使用两次，结果值会不同。

为了实现长链接和短链接的一一对应，需要大量的空间成本，尤其是为了快速响应，可能需要在里面做一层缓存显存，太贵了。

但评测：回答面试官的问题：如何设计一个短网址服务，可以实现一些变种来实现部分的一一对应，比如将最新/最流行的对应存储在KV数据库中，这样可以节省空间并提高响应速度。

我们返回的短网址通常会将数字转换为十六进制，这样可以更有效地减少网址的宽度。那么这个 62 位的数字对计算机来说也是一个字符串。如何储存？直接存储字符串等值值的查找容易查找，对范围查找等过于不友好。

其实十进制数可以直接存储，不仅占用空间更小，还支持更好的搜索，也更方便将其转换成more/less bases，进一步减少URL。

按照算法，从0到61，是1个字符，那么2、3……这样就很容易被检测和防御了。当然，防御方法有很多，请求签名等安全验证方法不在本文讨论范围。

首先，计数器可以从一个比较大的随机返回值开始，比如10000，它的62位系统是一个2Bi的3位字符串；

然后使用一些校验位算法（如Luhn改进）将条带的1位校验位和4位短码一起计算，可以消除一定的安全隐患；

如果添加了一些安全材料，则可以在十六进制转换期间随机打乱已排序的 62 个字母数字。比如ABCD1234加扰成1BC43A2D，再转成16进制，破解难度较大；

最后短链接恢复，如果还怕的话，也可以在这些位置插入随机数（比如1、3、5），这样人就可以了'不看规律，就能达到很好的疗效。

在编号策略中，并不确定长地址是否已经被传输，所以结果是一长对多短。有人说这是浪费空间。创建一个从长到短的地图存储足以短链接恢复，但使用地图存储本质上是占用空间的。 ，甚至以大空间换小空间，需要考虑是否真的需要一一对应而不是一对多；

最简单的解决方案：构建厚度图，以空间换空间，更好的方案：使用map存储“最近”生成的长短关系，一小时过期方式实现LRU淘汰

检查这个“最近”表，看看长地址是否有对应的短地址

如果有，直接返回，并将该字段对的过期时间重置为一小时

如果没有，通过sender生成一个短地址，把这个“最近”的表，过期时间为1小时

当一个地址被频繁使用时，它仍然会在key-value表中，并且会一直返回原来生成的短地址而不重复。如果不经常使用，长短键会过期，手动淘汰LRU模式。

这样就达到了空间和发号数量的平衡。这里也要看具体的业务需求，会不会出现一对多的情况。比如订单没有支付短链接恢复，用户会通过发送短信被召回。短信中的短url包含用户名、订单号等个性化信息，即不需要添加这个逻辑链接。

高并发

如果直接存储在 MySQL 中，对数据库的压力太大，并发请求减少时可能会出现问题。这时候可以做一些优化。

缓存

上面长的短链接一一对应也提到了缓存，这里我们来提升一下程序的处理速度。

可以缓存热门长链接（需要统计的长链接数）、最近的长链接（redis可以用来保存最近一小时）等，并保存在显存或者redis之类的内存数据库，如果请求长URL命中缓存，则直接获取对应的短URL返回，无需一步步生成。

批号

每次发出一个数，都要访问MySQL一次，获取当前最大数，获取后更新最大数，压力很大。

我们每天可以从数据库中获取 10,000 个数字，并将它们发送到显存中。当剩余数字大于 1000 时，我们可以再次向 MySQL 请求 10000 个数字。最后批号发出后，分批写入。

这样可以将数据库的持续操作移到代码中，异步进行读写操作，保证服务的持续高并发。

去中心化

上面设计的系统是单点的，即发号器是单点的，很容易挂机。

可以使用分布式服务。如果是分布式的，如果每个发行者在发行完号码后需要同步到其他发行者，可能不会太麻烦。

换一种思考方式，可能有两个发射器，一个用于奇数，一个用于偶数。号码发出后，不加1，加2.

以此类推，我们可以用1000个服务发出以0-999结尾的数字，每个数字加100 0.这个很简单，基本上不需要服务相互通信，只是你自己的事情会变得更好。