@zwh8800
2016-06-02T00:02:28.000000Z
字数 1980
阅读 324804
blog
短链接
算法
golang
最早 twitter 推出短链接服务之后,各大互联网企业也都跟进推出了自己的短链接服务,就连我们公司最近也有了这个需求。短链接形如 http://t.cn/R7gyvR4
,不仅好看而且能宏观上减少互联网的通讯量。这里记录下我做短链接的过程。
首先短链接算法有两个基本需求:
所以那种生产随机数,然后碰撞的算法肯定排除在外了,太过暴力,到后期碰撞绝对会相当严重。而 hash 算法可以算是正好能同时满足这两点需求,所以路线大概是怎么能改造一下现有的 hash 算法。
常见 hash 算法有 md5 和 sha1 两种, md5 已经被证明不安全,很容易由 hash 值推出原始数据。但是我们这里只对 hash 算法的碰撞率感兴趣,和安全性关系不大,所以还是选用 md5 算法。
md5 算法的输出是固定的 16 个字节(byte),也就是 128 位(bit),大概有 种情况。我们的需求是使用 6 位 大小写字母加数字
做短链接,大概可以表示 种情况。是少于 md5 算法的,所以思路可以是取 md5 值的一部分,然后生成短链接。
好的,首先可以把62个字符列一张表。比如这样:
// 62个字符, 需要6bit做索引(2 ^ 6 = 64)
var charTable = [...]rune{
'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', '6',
'7', '8', '9', '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',
}
那么,如果一个网址的 md5 值是 0 可以在短链接中用 a
表示 ,同理用 b
代表 1 。
按照这个思路,我来举个例子。
比如 https://lengzzz.com 的 md5 值是 3CD4B16B4855CF2DBEB9051867665045
,第一个字节是 0x3c
,十进制值为 60
那么在表中第 60 个是 Y ,那么用 Y 来表示 0x3c 。
但是这个思路还略有不妥,万一字节超了61就不行了。所以我们对字节使用 % 0x3d
取余运算,因为 0x3d 即为62,所以得到的数不会超出。
例如 0xd4
,十进制为 212
显然超出了,但是 0xd4 % 0x3d
等于 26
,第 26 个字符是 '0' ,所以可以用 '0' 来表示。
因此,我们可以把 md5 的输出分为 4 份,每份 4 个字节(byte)。4 个字节又可以分成 6 份,每份 5 位(bit)共 30 位(bit),这样正好是在使用一个 uint32
计算,效率较高。
公司里是用 java 实现的,我再写一个 golang 的版本:
package util
import (
"bytes"
"crypto/md5"
"encoding/binary"
)
// 62个字符, 需要6bit做索引(2 ^ 6 = 64)
var charTable = [...]rune{
'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', '6',
'7', '8', '9', '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',
}
func ShortenUrl(url string) []string {
shortUrlList := make([]string, 0, 4)
sumData := md5.Sum([]byte(url))
// 把md5sum分成4份, 每份4个字节
for i := 0; i < 4; i++ {
part := sumData[i*4 : i*4+4]
// 将4字节当作一个整数
partUint := binary.BigEndian.Uint32(part)
shortUrlBuffer := &bytes.Buffer{}
// 将30bit分成6份, 每份5bit
for j := 0; j < 6; j++ {
index := partUint % 62
shortUrlBuffer.WriteRune(charTable[index])
partUint = partUint >> 5
}
shortUrlList = append(shortUrlList, shortUrlBuffer.String())
}
return shortUrlList
}
注释比较完善,可以和文章对应着看。