我们都用过这样一个函数,一个很长的URL,可以压缩成一个很短的链接。这背后用的是什么样的技术?背后隐藏着怎样的算法和数据结构?怎么才能快速实施。
短URL技术其实很简单。我们可以把这项技术分为两部分。第一部分是长URL的压缩,即如何将长链接地址压缩成短链接地址。第二部分是如何把短链接地址重新变成长链接地址。
散列算法
最常见的短URL实现方案是使用哈希算法。相信学过算法和数据结构的同学对这个算法都很熟悉。哈希算法可以将很长的文本甚至文件映射成一个字符串或数字。这个算法并不陌生。我们常见的文件md5算法也是哈希算法之一。
但是md5比较长,所以我们通常使用murmurhash进行哈希,这是一种轻量级的哈希算法。我们把哈希值和长链接、过期时间一起保存在数据库里,然后就可以通过哈希值找到对应的原始长链接地址。
不过,这里还有两个细节。首先,如果散列地址冲突怎么办?常见的哈希冲突解决方法是从后面搜索,找到空的一个槽,放进去。如果你研究过算法和数据结构,你就会知道这个算法不稳定,很难实现。我们有一个更简单的方法,就是在原链接后面拼写一个自定义字符串进行哈希。
另一个问题是murmurhash的哈希结果是一个32位的数,只由0到9组成。如果看起来几千万这个数字比较长,那怎么办?我们可以把这个简单的十进制数转换成更高的十进制数,用字母A到Z,A到Z,把字符串变得很短。
再直接的
那么如何访问一个短网址,把它变成一个长地址呢?同理,很简单,就是利用网页重定向功能。
首先,用户使用短url在后台查询,然后检查数据的有效性,如数据过期,然后返回长地址和重定向错误代码。浏览器收到错误地址后,开始重定向到真实地址。
摘要
看,其实只要算法和存储非常简单,我们就做一个短url服务器。有兴趣的可以关注我。稍后,我们将用简单的代码实现它。欢迎大家关注我,一起学习,一起进步。大家的支持是我继续说下去的动力。同名微信官方账号(沙查敏的碎念)
vsus是什么牌子的电脑
