短链接算法原理

2024-09-08 13:48
文章标签 算法 原理 链接

本文主要是介绍短链接算法原理,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

平时我们在上网的时候,印象最深刻的有一次是短链接的服务。例如:平时在微信上看一个网页的时候,如果我们选择在浏览器打开的时候,会看到很长的URL,我们分享的时候,会看到一个很短URL,这就是本次所说的短链接的应用之一。
长链接示例:https://mp.weixin.qq.com/s?__biz=MzAxNzMwOTQ0NA==&mid=2653355437&idx=1&sn=5901826ea638462ff71b7f2d06c6331d&chksm=8035d7c6b7425ed06661866af60657414bb71765d2ce915d14726736fa1e72ea8a529331c947&scene=0&key=34df968fd24033237ff036c7de8b6745e1968de9564cf2a8db689025dd0c3682848381771dab960824f506e6f9d484614746f9c0eecb48b884ce4320bb86470a77ce811cc5b401a8800b6fd6b36be097&ascene=0&uin=ODU5NDQ1NjI1&devicetype=iMac+MacBookAir6%2C2+OSX+OSX+10.12.6+build(16G29)&version=12020810&nettype=WIFI&fontScale=100&pass_ticket=IvPqxUmCJqZg9%2B3GfAIQSbQ4IGRIHx796D0UwlCyUCu4b5P4bSsjlN89A0eRzSfL
我用短链接系统生成的(长期会失效):https://0x9.me/FAKcm

怎么把长链接转换成短链接呢?

废话少说,短链接就是我们很短的链接。我们的目的是要把长链接转换成短链接。接下来我要提出一个问题:怎么把长链接转换成短链接呢?
1.压缩
实现一种算法,将长地址转换成短地址。然后再实现一种逆运算,将短地址转换成原来的地址。其实仔细的想一下,这是不可能的。
2.Hash算法
可能是大多数人都会想到的一种方法。有人会提出,将一个长URL进行Hash运算,然后将Hash值作为这个长链接的唯一标示。但是通常容易想到的不一定是最优的,我们知道Hash有可能产生碰撞,Hash碰撞的解决,会增强短链接系统的复杂度。

最优的算法

通过发号原理

顾名思义这个系统的第一个请求过来了,我们以微博为例,短链接系统的第一个请求我们可以给变为t.cn/0,第二个t.cn/1等等;
实现的方式也会很简单
1、小型的系统用MySQL的自增索引就可以满足。
2、大型系统可以考虑分布式key-value系统。

存储原理

发号策略是这样的,当一个新的链接过来时,发号器发一个号与之对应。往后只要有新链接过来,发号器不停发号就好。举个例子,第一个进来的链接发号器发0号,对应的短链接为 xx.xxx/0,第二个进来的链接发号器发1号,对应的短链接为 xx.xxx/1,以此类推。
发号器发出的10进制号需要转换成62进制,这样可以大大缩短号码转换成字符串后的长度。比如发号器发出 10,000,000,000 这个号码,如果不转换成62进制,直接拼接在域名后面,得到这样一个链接 xx.xxx/10000000000。将上面的号码转换成62进制,结果为AOYKUa,长度只有6位,拼接得到的链接为 xx.xxx/AOYKUa。可以看得出,进制转换后得到的短链接长度变短了一些。6位62进制数,对应的号码空间为626,约等于568亿,所以基本上不用担心发号器无号可发的情况。

高并发场景下

上面设计看起来有一个单点,那就是发号器。如果做成分布式的,那么多节点要保持同步加1,多点同时写入。这样难以避免产生单点性能瓶颈。因此我们可以考虑将单点变为多点。我们可以引入多个机器,我们可以设定机器A发号只发向100取余等于0的数字100n,同理机器B只发向100取余等于1数字 100n+1,以此类推,各个机器相互独立互不干扰,我们可以随时扩展我们的机器了。

同一长链接,每次转成的短链接是否一样

同一长链接,每次转成的短链接不一定一样,原因在于如果查询缓存时,如果未命中,发号器会发新号给这个链接。需要说明的是,缓存应该缓存经常转换的热门链接,假设设定缓存过期时间为一小时,如果某个链接很活跃的话,缓存查询命中后,缓存会刷新这个链接的存活时间,重新计时,这个链接就会长久存在缓存中。
我们也可以引入LRU算法。进行淘汰我们不经常使用到的链接。

重定向问题

选取301,还是302?
301是永久重定向,302是临时重定向。

如果选择301:短地址生成以后就不会变化,所以用301是符合http语义的。同时对服务器压力也会有一定减少。这样一来,我们就无法统计到短地址被点击的次数了。
如果选择302:选择302虽然会增加服务器压力,但是可以统计到短地址被点击的次数了,我可以针对点击的次数来进行后期的大数据处理,机器学习,以及推荐算法。
选择302还是301,想必读者心中有肯定有数了。

其他

下面是从网上找到了一些算法总结:
算法一:

最容易想到的算法可能是利用md5类的加密算法,然后针对加密后的字符串进行处理。

1)将长网址md5生成32位签名串,分为4段, 每段8个字节;
2)对这四段循环处理, 取8个字节, 将他看成16进制串与0x3fffffff(30位1)与操作, 即超过30位的忽略处理;
3)这30位分成6段, 每5位的数字作为字母表的索引取得特定字符, 依次进行获得6位字符串;
4)总的md5串可以获得4个6位串; 取里面的任意一个就可作为这个长url的短url地址。

算法二:
a-zA-Z0-9 这64位取6位组合,可产生500多亿个组合数量。把数字和字符组合做一定的映射,就可以产生唯一的字符串,如第62个组合就是aaaaa9,第63个组合就是aaaaba,再利用洗牌算法,把原字符串打乱后保存,那么对应位置的组合字符串就会是无序的组合。
把长网址存入数据库,取返回的id,找出对应的字符串,例如返回ID为1,那么对应上面的字符串组合就是bbb,同理 ID为2时,字符串组合为bba,依次类推,直至到达64种组合后才会出现重复的可

这篇关于短链接算法原理的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1148279

相关文章

Mysql的主从同步/复制的原理分析

《Mysql的主从同步/复制的原理分析》:本文主要介绍Mysql的主从同步/复制的原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录为什么要主从同步?mysql主从同步架构有哪些?Mysql主从复制的原理/整体流程级联复制架构为什么好?Mysql主从复制注意

Nacos注册中心和配置中心的底层原理全面解读

《Nacos注册中心和配置中心的底层原理全面解读》:本文主要介绍Nacos注册中心和配置中心的底层原理的全面解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录临时实例和永久实例为什么 Nacos 要将服务实例分为临时实例和永久实例?1.x 版本和2.x版本的区别

apache的commons-pool2原理与使用实践记录

《apache的commons-pool2原理与使用实践记录》ApacheCommonsPool2是一个高效的对象池化框架,通过复用昂贵资源(如数据库连接、线程、网络连接)优化系统性能,这篇文章主... 目录一、核心原理与组件二、使用步骤详解(以数据库连接池为例)三、高级配置与优化四、典型应用场景五、注意事

电脑系统Hosts文件原理和应用分享

《电脑系统Hosts文件原理和应用分享》Hosts是一个没有扩展名的系统文件,当用户在浏览器中输入一个需要登录的网址时,系统会首先自动从Hosts文件中寻找对应的IP地址,一旦找到,系统会立即打开对应... Hosts是一个没有扩展名的系统文件,可以用记事本等工具打开,其作用就是将一些常用的网址域名与其对应

Dubbo之SPI机制的实现原理和优势分析

《Dubbo之SPI机制的实现原理和优势分析》:本文主要介绍Dubbo之SPI机制的实现原理和优势,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Dubbo中SPI机制的实现原理和优势JDK 中的 SPI 机制解析Dubbo 中的 SPI 机制解析总结Dubbo中

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

Android与iOS设备MAC地址生成原理及Java实现详解

《Android与iOS设备MAC地址生成原理及Java实现详解》在无线网络通信中,MAC(MediaAccessControl)地址是设备的唯一网络标识符,本文主要介绍了Android与iOS设备M... 目录引言1. MAC地址基础1.1 MAC地址的组成1.2 MAC地址的分类2. android与I

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

Spring框架中@Lazy延迟加载原理和使用详解

《Spring框架中@Lazy延迟加载原理和使用详解》:本文主要介绍Spring框架中@Lazy延迟加载原理和使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录一、@Lazy延迟加载原理1.延迟加载原理1.1 @Lazy三种配置方法1.2 @Component

spring IOC的理解之原理和实现过程

《springIOC的理解之原理和实现过程》:本文主要介绍springIOC的理解之原理和实现过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、IoC 核心概念二、核心原理1. 容器架构2. 核心组件3. 工作流程三、关键实现机制1. Bean生命周期2.