短链接

短链接是一种 URL 简化服务， 比如：当你输入一个 URL https://www.xdull.com 时，它将返回一个简化的URL http://tinyurl.com/weuZn ，其中http://tinyurl.com/是提供服务的域名，后面的weuZn为简化后的URL的key值，通过这个key能还原成原来的真正的URL。

本文旨在介绍短链接的实现方式，并非在 http://tinyurl.com/ 中存在真实的短链接地址。

现在我们的目标是实现短链接生成功能，它应当包含2个方法encode和decode，encode将真实URL转换为短链接，decode将短链接还原成原来的URL。

自增id

一种最直接的方式是我们内部维持一个自增id，并用字典将每一个id和一个URL对应上，解密即使用id作为字典的键值找到原始URL。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Codec:
    def __init__(self):
        self.dic = {}
        self.id=0

    def encode(self, longUrl: str) -> str:
        """Encodes a URL to a shortened URL.
        """
        self.id+=1
        self.dic[self.id]=longUrl
        return str(self.id)

    def decode(self, shortUrl: str) -> str:
        """Decodes a shortened URL to its original URL.
        """
        return self.dic[int(shortUrl.split('/')[-1])]

此方法实现起来虽然简单，但是缺点也非常明显，第一，由于id在不断变大，越靠后面的URL生成的短链接长度越长，这就导致短链接分配不均（长度相差较大）；第二，相同的URL生成的短链接是不同的，这就导致某一个URL可能会占用过多资源（占据了字典的大部分空间）。

哈希

一种更好的方式是使用hash算法，这样能保证每次encode相同的URL得到的结果是一样的，而且哈希值是均匀分布的。这里采用的hash算法是设URL的长度为n，然后选择两个合适的质数k 和m，使用以下公式计算哈希值：

URL的每一位乘以以质数k为底数的位数次幂，为避免整数过大造成溢出，再模质数m。最终目的就是为了让哈希值尽量离散分布，不要发生碰撞。但碰撞无法避免，当发生哈希碰撞的时候，将哈希值不断加1直到不再冲突。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Codec:
    def __init__(self):
        self.dic={}

    def encode(self, longUrl: str) -> str:
        """Encodes a URL to a shortened URL.
        """
        k=1117
        m=10**9+7
        h,base=0,1
        for c in longUrl:
            h+=ord(c)*base%m
            base=base*k%m
        while h in self.dic and self.dic[h]!=longUrl:
            h+=1
        self.dic[h]=longUrl
        return f'http://tinyurl.com/{h}'

    def decode(self, shortUrl: str) -> str:
        """Decodes a shortened URL to its original URL.
        """
        return self.dic[int(shortUrl.split('/')[-1])]

优化

这里得到的哈希值是个长度为10的十进制表示的整型，我们可以将它转化为更大进制的表示形式，以再次缩短它的长度，比如使用52个英文字符（26个大写和26个小写）加上10个数字字符表示成62进制的字符串。

我们把十进制数值的左边当作低位，右边当作高位，这样得到的62进制表示的字符串也是左边低位，右边高位，当还原回整型时，以避免将字符串反转。完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Codec:
    def __init__(self):
        self.dic = {}
        self.code = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
        self.map = {}
        for i,c in enumerate(self.code):
            self.map[c] = i
        self.base = len(self.code) # 有多少字符就表示多少进制

    # 整型数值转换为62进制表示的字符串
    def toStr(self,num):
        return "0" if num == 0 else (self.code[num % self.base] + self.toStr(num // self.base).rstrip("0"))

    # 62进制表示的字符串转换为整型数值
    def toInt(self,num):
        r,base = 0,1
        for c in num:
            r+=self.map[c] * base
            base*=self.base
        return r

    def encode(self, longUrl: str) -> str:
        """Encodes a URL to a shortened URL.
        """
        k = 1117
        m = 10 ** 9 + 7
        h,base = 0,1
        for c in longUrl:
            h+=ord(c) * base % m
            base = base * k % m
        while h in self.dic and self.dic[h] != longUrl:
            h+=1
        self.dic[h] = longUrl
        return f'http://tinyurl.com/{self.toStr(h)}'


    def decode(self, shortUrl: str) -> str:
        """Decodes a shortened URL to its original URL.
        """
        return self.dic[self.toInt(shortUrl.split('/')[-1])]

通过测试用例可以看到，2个URL即使只有一个大小写字符的差异，得到的短链接也会相差甚远。

1
2
print(codec.encode("https://www.xdull.cn/tinyurl.html"))  # http://tinyurl.com/opaqE
print(codec.encode("https://www.xdull.cn/Tinyurl.html"))  # http://tinyurl.com/fxMk9

如果可以预测要加密的URL数量很多，可适当增大质数m，以使哈希值的范围变得更大。