短链接
短链接是一种 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。
1234567891011121314151617 | 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，使用以下公式计算哈希值：
Hash(longUrl) = (\sum_{i=0}^{n-1} longUrl[i] \times k^i) \bmod m
URL的每一位乘以以质数k为底数的位数次幂，为避免整数过大造成溢出，再模质数m。最终目的就是为了让哈希值尽量离散分布，不要发生碰撞。但碰撞无法避免，当发生哈希碰撞的时候，将哈希值不断加1直到不再冲突。
12345678910111213141516171819202122 | 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进制表示的字符串也是左边低位，右边高位，当还原回整型时，以避免将字符串反转。完整代码如下：
12345678910111213141516171819202122232425262728293031323334353637383940 | 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即使只有一个大小写字符的差异，得到的短链接也会相差甚远。
12 | print(codec.encode("https://www.xdull.cn/tinyurl.html")) # http://tinyurl.com/opaqEprint(codec.encode("https://www.xdull.cn/Tinyurl.html")) # http://tinyurl.com/fxMk9 |
|---|
如果可以预测要加密的URL数量很多，可适当增大质数m，以使哈希值的范围变得更大。