短链接是一种 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和一个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
,以使哈希值的范围变得更大。