短链接生成算法

最早 twitter 推出短链接服务之后,各大互联网企业也都跟进推出了自己的短链接服务,就连我们公司最近也有了这个需求。短链接形如 http://t.cn/R7gyvR4 ,不仅好看而且能宏观上减少互联网的通讯量。这里记录下我做短链接的过程。

需求

首先短链接算法有两个基本需求:

  • 碰撞少

所以那种生产随机数,然后碰撞的算法肯定排除在外了,太过暴力,到后期碰撞绝对会相当严重。而 hash 算法可以算是正好能同时满足这两点需求,所以路线大概是怎么能改造一下现有的 hash 算法。

思路

常见 hash 算法有 md5 和 sha1 两种, md5 已经被证明不安全,很容易由 hash 值推出原始数据。但是我们这里只对 hash 算法的碰撞率感兴趣,和安全性关系不大,所以还是选用 md5 算法。

md5 算法的输出是固定的 16 个字节(byte),也就是 128 位(bit),大概有 $2^{128}$ 种情况。我们的需求是使用 6 位 大小写字母加数字 做短链接,大概可以表示 $62^6$ 种情况。是少于 md5 算法的,所以思路可以是取 md5 值的一部分,然后生成短链接。

好的,首先可以把62个字符列一张表。比如这样:

1
2
3
4
5
6
7
8
9
// 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 的版本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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
}

注释比较完善,可以和文章对应着看。

Proudly powered by Hexo and Theme by Hacker
© 2020 wastecat