Java基础、中级、高级、架构面试资料
    你的位置：业余草 > JAVA > 短网址的3种算法：进制算法、随机数算法和HASH算法

    短网址的3种算法：进制算法、随机数算法和HASH算法

    JAVA herman 4191浏览
    公告：“业余草”微信公众号提供免费CSDN下载服务(只下Java资源)，关注业余草微信公众号，添加作者微信：xttblog2，发送下载链接帮助你免费下载！
    本博客日IP超过2000，PV 3000 左右，急需赞助商。
    极客时间所有课程通过我的二维码购买后返现24元微信红包，请加博主新的微信号：xttblog2，之前的微信号好友位已满，备注：返现
    受密码保护的文章请关注“业余草”公众号，回复关键字“0”获得密码
    所有面试题(java、前端、数据库、springboot等)一网打尽，请关注文末小程序
    视频教程免费领
    腾讯云】1核2G5M轻量应用服务器50元首年，高性价比，助您轻松上云

    在Web 2.0的今天，不得不说，短网址已经是一个潮流。前段时间有人在公众号里问我 java 如何实现短网址功能，今天我就抽个时间，简单的说一下短网址的相关算法！

    短网址，或者说短域名。顾名思义，就是把长的 URL 转成短的 URL, 现在提供这种服务的有很多公司。比如百度的，新浪的，谷歌的等。

    短网址的解析过程

    当我们在浏览器里输入 https://dwz.cn/fJPYNNoX 回车后，DNS首先解析获得 https://dwz.cn/ 的 IP 地址。当DNS获得IP地址以后，会向这个地址发送HTTP GET请求，这个时候 https://dwz.cn/服务器会把请求通过 HTTP 302 重定向到对应的长URL https://www.xttblog.com 。浏览器会再次发起请求，请 https://www.xttblog.com 网址。

    文字已经解释的很明白了！看不明白的看下图：

    短网址解析过程

    明白了短网址的解析过程后，我们来说短网址的实现算法。

    根据 GitHub 上 star 数量最多的十个短网址服务对应的算法，大致分为三类：进制算法、随机数算法和HASH算法。 下面我们分别说说它们的实现原理！

    短网址进制算法

    算法简述：一个以数字、大小写字母共62个字符的任意进制的算法。 

    数据库中ID递增，当ID为233，则对应短网址计算过程如下：

    1. 设置序列为“0123456789abcdefghijklmnopqrstuvwxyz” 
    2. 233/36=6 
    3. 233%36= 17 
    4. 依次取上述字符的6位，17位，则为6h 

    其生成之后的短网址为xx.xx/6h 。

    短网址随机数算法

    算法简述：每次对候选字符进行任意次随机位数选择，拼接之后检查是否重复 

    若要求位数为2，则其对应短地址为计算过程如下：

    1. 设置字符序列“0123456789abcdefghijklmnopqrstuvwxyz” 
    2. 根据字符个数设置最大值为35，最小值为0，取2次随机数假设为：6,17 
    3. 依次取上述字符的6位和17位，则为6h 

    其生成之后的短网址为xx.xx/6h 。

    短网址HASH算法

    算法简述：对id进行hash操作（ 可选：利用随机数进行加盐），并检查是否重复 

    设置ID自增，若ID=233，则其对应短地址为计算过程如下： 

    1. 取随机数为盐 
    2. 对233进行sha1加密为： aaccb8bb2b4c442a7c16a9b209c9ff448c6c5f35:2 
    3. 要求位数为7，直接取上述加密结果的前7位为：aaccb8 

    其生成之后的短网址为xx.xx/2e8c027 。

    短网址的本质

    短网址本质上是实现了一个映射函数 f: X -> Y 。而这个映射函数必须同时具有两个特点：

    1. 如果 x1 != x2, 则 f (x1) != f(x2);
    2. 对于每一个 y, 能够找到唯一的一个 x 使得 f(x) = y;

    对于任何的线性函数，比如 f(x) = 2x，都满足这样的条件。

    java 实现短网址

    根据上面的解释，下面我来实现一个简单的短网址算法！ 

    public class ShortUrlTest {
    private static final String ALPHABET =
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    private static final int    BASE     = ALPHABET.length();
    public static String encode(int num) {
        StringBuilder sb = new StringBuilder();
        while ( num > 0 ) {
            sb.append( ALPHABET.charAt( num % BASE ) );
            num /= BASE;
        }
        return sb.reverse().toString();
    }
    public static int decode(String str) {
        int num = 0;
        for ( int i = 0; i < str.length(); i++ )
            num = num * BASE + ALPHABET.indexOf(str.charAt(i));
        return num;
    }
    public static void main(String[] args) {
        // 假设 www.xttblog.com 对应的ID是1
        encode(1);
    }
}

    短网址重定向

    关于短网址的重定向，我建议使用302。不建议使用301。因为302方便统计和分析用户属性等数据。大家可以参考百度、新浪、谷歌等是否都使用的是302状态！

    最后提醒大家一下，实现短网址一定要注意安全问题。比如，短网址常见的SSRF安全问题、XSS、SQL注入等问题。

    业余草公众号

    最后，欢迎关注我的个人微信公众号：业余草（yyucao）！可加作者微信号：xttblog2。备注：“1”，添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注！后续有精彩内容会第一时间发给您！原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系！

    本文原文出处：业余草： » 短网址的3种算法：进制算法、随机数算法和HASH算法

    相关文章推荐