短链接生成算法

短链接 算法 golang

2016-04-14 23:29 PM

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


需求

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

  • 碰撞少

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


思路

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

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

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

  1. // 62个字符, 需要6bit做索引(2 ^ 6 = 64)
  2. var charTable = [...]rune{
  3. 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k',
  4. 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v',
  5. 'w', 'x', 'y', 'z', '0', '1', '2', '3', '4', '5', '6',
  6. '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H',
  7. 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S',
  8. 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
  9. }

那么,如果一个网址的 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. package util
  2. import (
  3. "bytes"
  4. "crypto/md5"
  5. "encoding/binary"
  6. )
  7. // 62个字符, 需要6bit做索引(2 ^ 6 = 64)
  8. var charTable = [...]rune{
  9. 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k',
  10. 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v',
  11. 'w', 'x', 'y', 'z', '0', '1', '2', '3', '4', '5', '6',
  12. '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H',
  13. 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S',
  14. 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
  15. }
  16. func ShortenUrl(url string) []string {
  17. shortUrlList := make([]string, 0, 4)
  18. sumData := md5.Sum([]byte(url))
  19. // 把md5sum分成4份, 每份4个字节
  20. for i := 0; i < 4; i++ {
  21. part := sumData[i*4 : i*4+4]
  22. // 将4字节当作一个整数
  23. partUint := binary.BigEndian.Uint32(part)
  24. shortUrlBuffer := &bytes.Buffer{}
  25. // 将30bit分成6份, 每份5bit
  26. for j := 0; j < 6; j++ {
  27. index := partUint % 62
  28. shortUrlBuffer.WriteRune(charTable[index])
  29. partUint = partUint >> 5
  30. }
  31. shortUrlList = append(shortUrlList, shortUrlBuffer.String())
  32. }
  33. return shortUrlList
  34. }

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


发表于 2016-04-14 23:29 PM,最后更新于 2018-11-28 15:09:38 PM。

本文使用 署名 - 非商业性使用 - 相同方式共享 4.0 国际 协议


评论加载中...

首页