短链接生成算法

blog 短链接 算法 golang

最早 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个字符列一张表。比如这样：

// 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
}

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