shorturl实现常见的做法都是将原始Url存储到数据库，由数据库返回一个对应ID。
以下要实现的是不用数据库支持就对原始URL进行shorturl hash。说到这里我们很容易想到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
1#encoding:utf-8 2__author__ = 'James Lau' 3 4import hashlib 5import re 6 7def __original_shorturl(url): 8 ''' 9 算法： 10 ① 将长网址用md5算法生成32位签名串，分为4段,，每段8个字符； 11 ② 对这4段循环处理，取每段的8个字符, 将他看成16进制字符串与0x3fffffff(30位1)的位与操作，超过30位的忽略处理； 12 ③ 将每段得到的这30位又分成6段，每5位的数字作为字母表的索引取得特定字符，依次进行获得6位字符串； 13 ④ 这样一个md5字符串可以获得4个6位串，取里面的任意一个就可作为这个长url的短url地址。 14 （出现重复的几率大约是n/(32^6) 也就是n/1,073,741,824，其中n是数据库中记录的条数） 15 ''' 16 base32 = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 17 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 18 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 19 'y', 'z', 20 '0', '1', '2', '3', '4', '5' 21 ] 22 23 m = hashlib.md5() 24 m.update(url) 25 hexStr = m.hexdigest() 26 hexStrLen = len(hexStr) 27 subHexLen = hexStrLen / 8 28 29 output = [] 30 for i in range(0,subHexLen): 31 subHex = '0x'+hexStr[i*8:(i+1)*8] 32 res = 0x3FFFFFFF & int(subHex,16) 33 34 out = '' 35 for j in range(6): 36 val = 0x0000001F & res 37 out += (base32[val]) 38 res = res >> 5 39 output.append(out) 40 return output 41 42def shorturl(url): 43 ''' 44 算法： 45 ①从原始url中提取域名，提取数字（最多后6位）； 46 ②将所得的数字与4取模，根据所得的余数决定从第一步算法中得到的4个shorturl中选取哪一个； 47 ③从域名中提取特征串：一级域名中的第一个字符和后面二个辅音（如果辅音不足2个取任意前两个）； 48 ④域名特征串和选定的shorturl拼接成9位字符为最终的shorturl； 49 （后两个步骤是将冲突控制在一个domain内） 50 ''' 51 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]+)).*$') 52 match_full_domain = match_full_domain_regex.match(url) 53 54 if match_full_domain is not None: 55 full_domain = match_full_domain.group(1) 56 else: 57 return None 58 59 not_numeric_regex = re.compile(u'[^\d]+') 60 numeric_string = not_numeric_regex.sub(r'',url) 61 if numeric_string is None or numeric_string=='': 62 numeric_string = '0' 63 else: 64 numeric_string = numeric_string[-6:] 65 66 domainArr = full_domain.split('.') 67 domain = domainArr[1] if len(domainArr)==3 else domainArr[0] 68 69 vowels = 'aeiou0-9' 70 if len(domain)<=3: 71 prefix = domain 72 else: 73 prefix = re.compile(u'[%s]+'%vowels).sub(r'',domain[1:]) 74 prefix = '%s%s'%(domain[0],prefix[:2]) if len(prefix)>=2 else domain[0:3] 75 76 t_shorturl = __original_shorturl(url) 77 t_choose = int(numeric_string)%4 78 result = '%s%s'%(prefix,t_shorturl[t_choose]) 79 return result