Python实现短网址ShortUrl的Hash运算实例讲解
本文实例讲述了Python实现短网址ShortUrl的Hash运算方法。分享给大家供大家参考。具体如下:
shorturl实现常见的做法都是将原始Url存储到数据库,由数据库返回一个对应ID。
以下要实现的是不用数据库支持就对原始URL进行shorturlhash。说到这里我们很容易想到MD5,固定长度,冲突概率小,但是32个字符,太长?我们以MD5为基础,将其字符缩短,同时要保证一定数量范围内hash不会冲突。
我们分成两个步骤来实现。
第一步算法:
①将长网址用md5算法生成32位签名串,分为4段,,每段8个字符;
②对这4段循环处理,取每段的8个字符,将他看成16进制字符串与0x3fffffff(30位1)的位与操作,超过30位的忽略处理;
③将每段得到的这30位又分成6段,每5位的数字作为字母表的索引取得特定字符,依次进行获得6位字符串;
④这样一个md5字符串可以获得4个6位串,取里面的任意一个就可作为这个长url的短url地址。
(出现重复的几率大约是n/(32^6)也就是n/1,073,741,824,其中n是数据库中记录的条数)
我们就得到了4个6位串,可是选哪个作为最终的hash结果呢,随机选肯定是不行的,同样的url两次hash就会得出不同的结果。接下来根据原始url的特征进行选择,并且将hash冲突的可能性控制在同一个domain内:
第二步算法:
①从原始url中提取域名,提取数字(最多后6位);
②将所得的数字与4取模,根据所得的余数决定从第一步算法中得到的4个shorturl中选取哪一个;
③从域名中提取特征串:一级域名中的第一个字符和后面二个辅音(如果辅音不足2个取任意前两个);
④域名特征串和选定的shorturl拼接成9位字符为最终的shorturl;
(后两个步骤是将冲突控制在一个domain内)
ShortUrl.py
#encoding:utf-8 __author__='JamesLau' importhashlib importre def__original_shorturl(url): ''' 算法: ①将长网址用md5算法生成32位签名串,分为4段,,每段8个字符; ②对这4段循环处理,取每段的8个字符,将他看成16进制字符串与0x3fffffff(30位1)的位与操作,超过30位的忽略处理; ③将每段得到的这30位又分成6段,每5位的数字作为字母表的索引取得特定字符,依次进行获得6位字符串; ④这样一个md5字符串可以获得4个6位串,取里面的任意一个就可作为这个长url的短url地址。 (出现重复的几率大约是n/(32^6)也就是n/1,073,741,824,其中n是数据库中记录的条数) ''' base32=['a','b','c','d','e','f','g','h', 'i','j','k','l','m','n','o','p', 'q','r','s','t','u','v','w','x', 'y','z', '0','1','2','3','4','5' ] m=hashlib.md5() m.update(url) hexStr=m.hexdigest() hexStrLen=len(hexStr) subHexLen=hexStrLen/8 output=[] foriinrange(0,subHexLen): subHex='0x'+hexStr[i*8:(i+1)*8] res=0x3FFFFFFF&int(subHex,16) out='' forjinrange(6): val=0x0000001F&res out+=(base32[val]) res=res>>5 output.append(out) returnoutput defshorturl(url): ''' 算法: ①从原始url中提取域名,提取数字(最多后6位); ②将所得的数字与4取模,根据所得的余数决定从第一步算法中得到的4个shorturl中选取哪一个; ③从域名中提取特征串:一级域名中的第一个字符和后面二个辅音(如果辅音不足2个取任意前两个); ④域名特征串和选定的shorturl拼接成9位字符为最终的shorturl; (后两个步骤是将冲突控制在一个domain内) ''' match_full_domain_regex=re.compile(u'^https?:\/\/(([a-zA-Z0-9_\-\.]+[a-zA-Z0-9_\-]+\.[a-zA-Z]+)|([a-zA-Z0-9_\-]+\.[a-zA-Z]+)).*$') match_full_domain=match_full_domain_regex.match(url) ifmatch_full_domainisnotNone: full_domain=match_full_domain.group(1) else: returnNone not_numeric_regex=re.compile(u'[^\d]+') numeric_string=not_numeric_regex.sub(r'',url) ifnumeric_stringisNoneornumeric_string=='': numeric_string='0' else: numeric_string=numeric_string[-6:] domainArr=full_domain.split('.') domain=domainArr[1]iflen(domainArr)==3elsedomainArr[0] vowels='aeiou0-9' iflen(domain)<=3: prefix=domain else: prefix=re.compile(u'[%s]+'%vowels).sub(r'',domain[1:]) prefix='%s%s'%(domain[0],prefix[:2])iflen(prefix)>=2elsedomain[0:3] t_shorturl=__original_shorturl(url) t_choose=int(numeric_string)%4 result='%s%s'%(prefix,t_shorturl[t_choose]) returnresult
希望本文所述对大家的Python程序设计有所帮助。