你用过短链接网址系统的服务吗？如果我们在微博上发布一条带有网站的信息，微博会里面的网站变成更短的网站。只要我们访问这个短网站，就相当于访问原始网站。

从功能上讲，短网站服务其实很简单，就是把长网站变成短网站。作为一名软件工程师，你有没有想过如何实现这样一个简单的功能？底层依赖哪些数据结构和算法？

一.短网站服务整体介绍

正如我们刚才所说，短网站服务的核心功能之一是将原始的长网站转换为短网站。除此之外，短网站服务还有另一个重要的功能。也就是说，当用户点击短网站时，短网站服务将浏览器重新定位为原始网站。这个过程是如何实现的？

为了方便你理解，我画了一张对比图，你可以看看。

从图中可以看出，浏览器将首先访问短网站服务，通过短网站获取原始网站，然后通过原始网站访问页面。但这部分功能并不是我们今天要讨论的焦点。让我们关注一下如何将长网站转换为短网站？

二.如何通过哈希算法生成短网址？

哈希算法可以将一个字符串转换成一个长度固定的哈希值。我们可以使用哈希算法生成短网站。

我们之前提到过一些哈希算法，比如哈希算法MD5.SHA等待。但事实上，我们并不需要这些复杂的哈希算法。毕竟，我们不需要考虑反向解密的难度，所以我们只需要关注哈希算法的计算速度和冲突概率。

有许多哈希算法可以满足这些要求，其中一种更著名和广泛使用的哈希算法，即MurmurHash算法。尽管这种哈希算法在2008年才被发明，但现在它已广泛应用于Redis.MemCache.Cassandra.HBase.Lucene在许多著名的软件中。

MurmurHash算法提供了两种长度的哈希值，一种是32bits，一种是128bits。为了使最终生成的短网站尽可能短，我们可以选择32bits哈希值。对于开头那个。GitHub网址，经过MurmurHash经过计算，哈希值为18138494。如果我们拼上短网站服务的域名，就会成为最终的短网站http://t.cn/181338494（其中，http://t.cn是短网站服务的域名)。

1.如何使短网站更短？

不过，你可能已经看到了，通过MurmurHash算法得到的短网站还是很长的，似乎和我们开头网站的格式不一样。别担心，我们只需要稍微改变一下哈希值的表达方式，就可以轻松缩短短网站。

我们可以将10进制的哈希值转化为更高的哈希值，从而缩短哈希值。我们知道，在16进制中，我们使用它A～E，表示10~15。URL常用的合法字符有0~9.a～z.A～Z这是62个字符。为了尽可能短地表示哈希值，我们可以将10进制的哈希值转换为62进制。我在这里写了具体的计算过程。最后，62进制的短网站是http://t.cn/cgSqq。

2.如何解决哈希冲突？

然而，正如我们之前所说，哈希算法不可避免的一个问题是哈希冲突。尽管如此。MurmurHash算法，冲突的概率很低。然而，一旦发生冲突，两个原始网站将被转换为同一个短网站。当用户访问短网站时，我们无法判断用户想要访问哪个原始网站。如何解决这个问题？

一般情况下，我们会保存短网站与原网站的对应关系，以便后续用户在访问短链接网址系统时根据相应关系找到原网站。存储这种对应关系的方法有很多，比如我们自己设计存储系统或者使用现成的数据库。我们上面提到的数据库有MySQL.Redis。我们就拿MySQL例如。假设短网址与原网址之间的对应关系，则存储在MySQL数据库中。

当新的原始网站需要生成短网站时，我们首先使用它MurmurHash算法，生成短网站。然后，我们拿这个新生成的短网站，在这个新生成的短网站中，在这个短网站中，MySQL在数据库中搜索。

如果没有找到同样的短网站，这意味着新生成的短网站没有冲突。所以我们将短网站返回给用户（请求生成短网站的用户），然后将短网站与原始网站的对应关系存储到MySQL数据库中。

如果我们在数据库中找到相同的短网站，这并不一定意味着冲突。我们还从数据库中删除了与短网站相对应的原始网站。如果数据库中的原始网站与我们现在正在处理的原始网站相同，则表明有人已经请求了原始网站的短网站。我们可以直接使用这个短网站。如果数据库中记录的原始网站与我们正在处理的原始网站不同，则表明哈希算法发生了冲突。不同的原始网站，经过计算，得到的短网站被重复。现在，我们该怎么办？

我们可以为原始网站拼接一串特殊的字符，比如“[DUPLICATED]”然后重新计算哈希值，两次哈希计算冲突的概率显然很低。假设有一个非常极端的情况，再次发生冲突，我们可以改变拼接字符串，例如“[OHMYGOD]”，然后计算哈希值。然后将计算出来的哈希值与原始网站拼接成特殊字符串后的文本存储在一起。MySQL数据库中。

当用户访问短网站时，短网站服务首先通过短网站在数据库中找到相应的原始网站。如果原始网站拼接了特殊字符（通过字符串匹配算法很容易找到），我们将首先删除特殊字符，然后将不包含特殊字符的原始网站返回浏览器。

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

为了判断生成的短网站是否存在冲突，我们需要在数据库中找到生成的短网站。如果数据库中存储了大量数据，则搜索速度非常慢，这必然会影响短网站服务的性能。有什么优化的方法吗？

还记得我们之前说的话MySQL数据库索引？B+树索引。这样，通过短网站查询原网站的速度就提高了很多。事实上，在真正的软件开发中，我们可以通过一个小技巧进一步提高速度。

在生成短网站的过程中，我们会两次与数据库打交道，即执行两个SQL句子。第一个SQL语句是通过短网址查询短网址与原网址的对应关系，第二个是SQL句子是将新生成的短网址与原网址之间的对应关系存储在数据库中。

我们知道，短链接网址系统一般来说，数据库和应用服务（只计算不存储数据的业务逻辑部分）将部署在两个独立的服务器或虚拟服务器上。

SQL句子的执行需要两次网络通信。这种语句的执行需要两次网络通信。IO通讯耗时SQL句子的执行是整个短网站服务的性能瓶颈。因此，为了提高性能，我们需要尽量减少SQL句子。那怎么减少呢？SQL语句呢？

我们可以在数据库中的短网站字段中添加一个唯一的索引（不仅是索引，而且要求表中没有重复的数据）。当新的原始网站需要生成短网站时，我们不会首先使用生成的短网站，在数据库中找到重量，而是直接将生成的短网站和相应的原始网站存储到数据库中。如果数据库能正常写入数据，则不违反唯一的索引，即新生成的短网站没有冲突。

当然，如果数据库反馈违反了唯一性索引异常，我们必须重新执行刚才提到的索引“查询.写入”过程，SQL句子执行的次数不减反增。然而，在大多数情况下，情绪是如此。

以上就是关于《用数据结构和算法实现短链接网址系统》的全部内容了，感兴趣的话可以点击右侧直接使用哦！》》在线短链接生成器