ShortUrl Hash的实现

Stella981
• 阅读 719

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
点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Easter79 Easter79
3年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Stella981 Stella981
3年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
10个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这