阅读 135

如何生成短链接

这也是一道leetcode的题目

leetcode.com/problems/en…

leetcode-cn.com/problems/en…

描述

生成短链接.

思路

如果仅仅是做题,那么其实有很多办法.

在实际中,应该使用分布式发号器(Distributed ID Generator)

64位的整数能表示的范围184467440737亿远远大于全球网页数量45亿。来一个长网址,就分配一个ID去生成短网址.

而且这样可以支持一个长网址对应多个短网址。一般而言,一个长网址,在不同的地点,不同的用户等情况下,生成的短网址应该不一样,这样,在后端数据库中,可以更好的进行数据分析。

为了方便转化为字符串,一般使用62进制,字符串的一位可以是大小写字母加数字共62个字母.

一般采用一个7位的字符串,62^7=3521614606208627=35216亿.

其他的办法大概还有取HASH值的前N位,碰撞,不重复就为短网址.这样性能不高。

代码

public class EncodeAndDecodeTinyURL {

    Map<String, String> map = new HashMap<>();

    long index = 10000; // 这里是模拟一个当前计数值.
    private static String chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    private static int scale = 62;

    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {

        String tinyUrl = indexToStr(index, 7);
        map.put(tinyUrl, longUrl);
        return tinyUrl;
    }

    public String indexToStr(long num, int length) {
        StringBuilder sb = new StringBuilder();
        int remainder = 0;

        while (num > scale - 1) {
            /**
             * 对 scale 进行求余,然后将余数追加至 sb 中,由于是从末位开始追加的,因此最后需要反转(reverse)字符串
             */
            remainder = Long.valueOf(num % scale).intValue();
            sb.append(chars.charAt(remainder));

            num = num / scale;
        }

        sb.append(chars.charAt(Long.valueOf(num).intValue()));
        String value = sb.reverse().toString();

        while (value.length() < length) {
            value = "0" + value;
        }
        return value;


    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        return map.get(shortUrl);
    }

    public static void main(String[] args) {
        EncodeAndDecodeTinyURL codec = new EncodeAndDecodeTinyURL();
        codec.decode(codec.encode("https://leetcode.com/problems/design-tinyurl"));
    }
复制代码

其他

以下内容出自武林的回答

如何存储

如果存储短网址和长网址的对应关系?以短网址为 primary key, 长网址为value, 可以用传统的关系数据库存起来,例如MySQL,PostgreSQL,也可以用任意一个分布式KV数据库,例如Redis, LevelDB。 如果你手痒想要手工设计这个存储,那就是另一个话题了,你需要完整地造一个KV存储引擎轮子。当前流行的KV存储引擎有LevelDB何RockDB,去读它们的源码。

301还是302重定向

这也是一个有意思的问题。这个问题主要是考察你对301和302的理解,以及浏览器缓存机制的理解。 301是永久重定向,302是临时重定向。短地址一经生成就不会变化,所以用301是符合http语义的。但是如果用了301, Google,百度等搜索引擎,搜索的时候会直接展示真实地址,那我们就无法统计到短地址被点击的次数了,也无法收集用户的Cookie, User Agent 等信息,这些信息可以用来做很多有意思的大数据分析,也是短网址服务商的主要盈利来源。所以,正确答案是302重定向。

预防攻击

如果一些别有用心的黑客,短时间内向TinyURL服务器发送大量的请求,会迅速耗光ID,怎么办呢?
首先,限制IP的单日请求总数,超过阈值则直接拒绝服务。光限制IP的请求数还不够,因为黑客一般手里有上百万台肉鸡的,IP地址大大的有,所以光限制IP作用不大。
可以用一台Redis作为缓存服务器,存储的不是 ID->长网址,而是 长网址->ID,仅存储一天以内的数据,用LRU机制进行淘汰。这样,如果黑客大量发同一个长网址过来,直接从缓存服务器里返回短网址即可,他就无法耗光我们的ID了。

参考

youzhixueyuan.com/how-to-gene…