Nodejs ·

短链接原理及其算法实现

短网址在目前来说是一个非常流行的东西,提供短网址服务的网站也是相当多的,短网址在微博上应用的比较广泛 ,因为微博对于url的长度有一个限制,所以将一个很长的网址转换成一个很短的网址,是一个非常棒的想法,其好处有很多,比如字符少,美观,便于发布和传播等。

短网址原理说明

在这里我们以百度短网址服务为例来说明一下。https://dwz.cn/XrxeqVqy 这个url是我网站首页经过缩短以后的效果。其具体步骤如下所示:

  • 在浏览器地址栏输入短网址,或在浏览器中点击短网址
  • 进行DNS解析,获取dwz.cn的ip,然后向该地址发送get请求,这里说白了一点其实就是请求了一个url
  • 服务器获取到XrxeqVqy,根据这个短码获取到其对应的长URL
  • 重定向到该长URL中。

重定向可以采用301重定向也可以采用302重定向,其区别在于前者是永久重定向,后者是临时重定向,一般情况下,短网址一经生成,就不会在变化,所以采用301重定向会更好一些,可以减轻服务器的压力。当前前提是你不需要统计该链接的访问次数,或其他信息,如果需要统计,那么使用可以使用302重定向的方式。

如何缩短网址

缩短网址其实就是采用一定的算法将长URL进行处理,然后得出唯一的短码,这个短码和长url是一一对应的,不能重复,然后将短码存储起来,当使用短码访问的时候,查询出其对应的长URL,进行重定向即可。

一般采用的算法有两种:自增ID法摘要算法

自增ID法

自增ID的方法也叫做永不重复法,即采用发号器原理来实现,每一个url对应一个数字,然后自增,可以理解为ID,然后将ID进行相应的转换(比如进制转换),由于ID是唯一的,所以转换出来的结果也是唯一的。短网址的长度一般设为 6 位,而每一位是由 [a - z, A - Z, 0 - 9] 总共 62 个字母组成的,所以 6 位的话,总共会有 62^6 ~= 568亿种组合,基本上够用了。

理论说完了,我们来看一下具体的实现算法步骤:

首先,获取长URL,将长url计算成md5值,判断库(这个库可以是redis或mysql获取noSql等数据库)中是否存在该md5值对应的短码,如果有,直接返回;如果没有,将url,md5存入数据库中,并返回该条记录的id值,此ID值作为生成短链的一个依据。这里为什么将url转换成md5,原因在于长url可能是一个很长的串,在数据库中查询是很费时的,尤其是作为redis的key值,更是不可取的。

然后将返回的ID转换为61进制,将字母或数字中的其中一个取出作为连接符使用,这里我们使用小写字母a,然后拼接到转换完进制的字符串后,不足六位的用随机字符补足,随机字符中也要相应的踢除掉该连接符字符,用以保证六位短码唯一。

短码已经生成,直接返回就好。在之后就是输入短码来重定向了,我们可以在库中查询该短码对应的长url,然后重定向到长url地址即可。

流程图如下
短链接原理及其算法实现

这里我将生成短码的算法贴出来,示例代码采用nodejs,其他的业务逻辑很容易实现,就不在贴了:

function EncodeStr(number) {

    if(!parseInt(number)){
        let codemsg = "请传入数字类型";
        return {
            success:false,
            msg:codemsg
        }
    }
    let randomInsertStr = 'a';
    var chars = '0123456789bcdefghigklmnopqrstuvwxyzABCDEFGHIGKLMNOPQRSTUVWXYZ'.split(''),
        radix = chars.length,
        qutient = +number,
        arr = [];
    do {
        mod = qutient % radix;
        qutient = (qutient - mod) / radix;
        arr.unshift(chars[mod]);
    } while (qutient);
    let  codeStr = arr.join('');
    codeStr = codeStr.length < 6 ?  (codeStr+randomInsertStr + randomWord(false,5-codeStr.length,0,[randomInsertStr])):codeStr;
    return codeStr;
}
let randomWord = (randomFlag, min, max,ruledOutStr)=>{
    var str = "",
        range = min,
        pos='',
        arr = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];
    if(ruledOutStr){
        ruledOutStr.map(item=>{
            arr = arr.join("").split(item).join('').split('')
        })
    }

    // 随机产生
    if(randomFlag){
        range = Math.round(Math.random() * (max-min)) + min;
    }
    for(var i=0; i<range; i++){
        pos = Math.round(Math.random() * (arr.length-1));
        str += arr[pos];
    }
    return str;
};

摘要算法

摘要算法是会存在重复的几率,而且越往后重复几率越大。先来说一下具体思路:
首先,将长网址 md5 生成 32 位签名串,分为 4 段, 每段 8 个字节,对这四段循环处理, 取 8 个字节, 将他看成 16 进制串与 0x3fffffff(30位1) 与操作, 即超过 30 位的忽略处理,这 30 位分成 6 段, 每 5 位的数字作为字母表的索引取得特定字符, 依次进行获得 6 位字符串。总的 md5 串可以获得 4 个 6 位串,取里面的任意一个就可作为这个长 url 的短 url 地址。查询库中短url是否存在,如果存在则重新来过,不存在直接存入即可。

如有不对之处欢迎指正

参与评论