文档章节

ShortUrl Hash的实现

小水熊
 小水熊
发布于 2013/08/12 12:07
字数 1072
阅读 185
收藏 0

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

#encoding:utf-8
__author__ = 'James Lau'

import hashlib
import re

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 = []
    for i in range(0,subHexLen):
        subHex = '0x'+hexStr[i*8:(i+1)*8]
        res = 0x3FFFFFFF & int(subHex,16)

        out = ''
        for j in range(6):
            val = 0x0000001F & res
            out += (base32[val])
            res = res >> 5
        output.append(out)
    return output

def shorturl(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)

    if match_full_domain is not None:
        full_domain = match_full_domain.group(1)
    else:
        return None

    not_numeric_regex = re.compile(u'[^\d]+')
    numeric_string = not_numeric_regex.sub(r'',url)
    if numeric_string is None or numeric_string=='':
        numeric_string = '0'
    else:
        numeric_string = numeric_string[-6:]

    domainArr = full_domain.split('.')
    domain = domainArr[1] if len(domainArr)==3 else domainArr[0]

    vowels = 'aeiou0-9'
    if len(domain)<=3:
        prefix = domain
    else:
        prefix = re.compile(u'[%s]+'%vowels).sub(r'',domain[1:])
        prefix = '%s%s'%(domain[0],prefix[:2]) if len(prefix)>=2 else domain[0:3]

    t_shorturl = __original_shorturl(url)
    t_choose = int(numeric_string)%4
    result = '%s%s'%(prefix,t_shorturl[t_choose])
    return result



© 著作权归作者所有

小水熊

小水熊

粉丝 68
博文 61
码字总数 41633
作品 1
静安
架构师
私信 提问
关于apache服务器mod_rewrite配置

我的目的是在地址栏输入的url: http://localhost/project/ShortURL/index.php/149Ui3 自动重写为 http://localhost/project/ShortURL/index.php?controller=jump&method=jemp&code=149Ui3 ap......

Dreamshield
2015/03/06
831
10
535. Encode and Decode TinyURL - LeetCode

Question 535. Encode and Decode TinyURL Solution 题目大意:实现长链接加密成短链接,短链接解密成长链接 思路:加密成短链接+key,将长链接按key保存到map,解密时根据短链接提取key,再从map...

yysue
2018/07/28
120
0
URL短地址压缩算法 微博短地址原理解析 (Java实现)

最近,项目中需要用到短网址(ShortUrl)的算法,于是在网上搜索一番,发现有C#的算法,有.Net的算法,有PHP的算法,就是没有找到Java版的短网址(ShortUrl)的算法,很是郁闷。同时还发现有...

神勇小白鼠
2014/07/29
815
0
osc的短url用的是什么方法 ?在java里有没有比较好的处理shorturl的框架

osc的短url用的是什么方法啊在java里有没有比较好的处理shorturl的框架之类的?好像osc用的是shorturl和普通url的混合型 的?

黑神领主
2012/02/21
383
2
长url与短url之间建立映射关系 Encode and Decode TinyURL

问题: Note: This is a companion problem to the System Design problem: Design TinyURL. TinyURL is a URL shortening service where you enter a URL such as and it returns a short U......

叶枫啦啦
2018/01/10
37
0

没有更多内容

加载失败,请刷新页面

加载更多

XXL-JOB使用命令行的方式启动python时,日志过多导致阻塞的解决方式

一、Runtime.getRuntime().exec()的阻塞问题 这个问题也不能算是XXL-JOB的问题,而是Java的Runtime.getRuntime().exec()造成的,BufferedReader的缓冲区大小有限,当不能及时从缓冲区中把输出...

codeobj
25分钟前
4
0
java后端获取字符串标签里面的具体值

1、如下:怎么获取value值,使用Jsoup解决 <select id='department' name='department' class='select' tabindex='6' onchange='changeDept()'><option value=''>院系</optio......

木九天
32分钟前
4
0
Xamarin图表开发基础教程(10)OxyPlot框架支持的图表类型

Xamarin图表开发基础教程(10)OxyPlot框架支持的图表类型 OxyPlot组件支持26种图表,这些图表按照功能和样式可以分为4大类,分别为线型图表、条型图表、金融图表和其它图表。 线型图表 OxyP...

大学霸
35分钟前
4
0
移动端input“输入框”常见问题及解决方法

移动端input“输入框”常见问题及解决方法 1. ios中,输入框获得焦点时,页面输入框被遮盖,定位的元素位置错乱: 当页input存在于吸顶或者吸底元素中时,用户点击输入框,输入法弹出后,fie...

tyou
37分钟前
4
0
初探Android线程池

前言 最近在看OkHttp的源码,看的时候发现有关线程池的运用,自己就仔细想了一下,这个块知识好像不是很牢固。没办法,再研究一下有关线程池的相关知识吧。学习就是一个查漏补缺的过程,最终...

二营长的意大利炮手
44分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部