观察到短链接这个东西，主要是在微博和微信上，例如微信我订阅了一个每日推送，短小的篇幅里，夹杂的就是短链接，若是原链接，则篇幅很大，一点也不简洁。

短链接网上的各类博客讨论的不止一点半点了，我这里并不是太想重复前辈们写的东西，我这里想的是直接上算法展示，具体的短链接服务，留待我以后完成后，写一篇总结，挂上GitHub地址就好了，这样感（tou）觉（lan）不（hen）错（bang）。

我参考的博客：

短链接 设计

短网址、发号器 系统构建分析

短网址(short URL)系统的原理及其实现

原理

获得短链接：

1
long url => server => short url

访问短链接：

1
short url => short server (重定向)=> long url

short server 服务提供重定向到 长网址的功能，还可以在short server 服务上进行点击访问统计，用户地域分析等等统计功能。 像Google、新浪等短网址服务提供商大都集成了类似的统计后台功能（有的可能需要付费） 。

百度短网址生成网站。

谷歌原本也有，不过已经关停了。

算法

大体上来说，短网址上熟知的算法有两种，Hash算法和自增序列ID算法。

Hash算法

将长网址md5生成32位签名串（原始数据加上盐，这样不容易暴露算法），分为4段，每段8个字节；

对这四段循环处理，取8个字节，将他看成16进制串与0x3fffffff(30位1)与操作，即超过30位的忽略处
理；

这30位分成6段，每5位的数字作为字母表的索引取得特定字符，依次进行获得6位字符串；

总的md5串可以获得4个6位串；取里面的任意一个就可作为这个长url的短url地址；

字母表既由数字和大小写字母组成（一般顺序会被打乱）：

1
2
3
4
5
6
7
// 短链字符: a-z 0-9 A-Z
var Codes = []byte{'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'}

生成短链的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 首先every8Chars是md5中的一组子串, 8个字符
// 所有的数据支取后面30bits
base := every8Chars & 0x3FFFFFFF
// 数组保存6个字符
result := make([]byte, 6)
// 下面生成6个字符
for j := 0; j < 6; j++ {
    // 0x0000003D = 61, 所以0x0000003D & out保证生成的数载0~61, 所以其实就是Codes的所有下标
	idx := 0x0000003D & base
	// 获取这个idx下标的字符
	result[j] = ALPHABET[int(idx)]
	// 继续处理后面的bits
	base = base >> 5
}

完整代码：

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// 短链字符: a-z 0-9 A-Z
var Codes = []byte{'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 GenerateShortLink(longURL string) string {
	// 生成4个短链串
	loopNum := 4
	var urls []string
	var i int

	// long url转md5
	md5URL := md5.New()
	// 此处的"salt": 自定义字符串,防止算法泄漏
	_, err := io.WriteString(md5URL, "salt"+longURL)
	if err != nil {
		fmt.Println(err)
		return ""
	}
	md5Byte := md5URL.Sum(nil)
	md5Str := fmt.Sprintf("%x", md5Byte)

	for i = 0; i < loopNum; i++ {
		// 每8个字符是一个组
		each8BitsStr := md5Str[i*8 : i*8+8]
		// 将一组串转成16进制数字
		val, err := strconv.ParseInt(fmt.Sprintf("%s", each8BitsStr), 16, 64)
		if err != nil {
			fmt.Println(err)
			continue
		}
		// 获得一个新的短链
		urls = append(urls, genShortURL(val, i))
	}

	// 下面从上面的4个短链中随机一个作为当前的短链
	if len(urls) == 0 {
		return ""
	}

	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	idx := r.Intn(len(urls))
	return urls[idx]
}

// 32位的md5串中, 每8个字符作为一组, 计算得到一个6个字符的短链
func genShortURL(every8Chars int64, idx int) string {
	// 首先every8Chars是md5中的一组子串, 8个字符
	// 所有的数据支取后面30bits
	base := every8Chars & 0x3FFFFFFF
	// 数组保存6个字符
	result := make([]byte, 6)
	// 下面生成6个字符
	for j := 0; j < 6; j++ {
		// 0x0000003D = 61, 所以0x0000003D & out保证生成的数载0~61, 所以其实就是Codes的所有下标
		idx := 0x0000003D & base
		// 获取这个idx下标的字符
		result[j] = Codes[int(idx)]
		// 继续处理后面的bits
		base = base >> 5
	}
	return fmt.Sprintf("%s", result)
}

自增序列ID算法

短址的长度一般设为 6 位，而每一位是由 [a - z, A - Z, 0 - 9] 总共 62 个字母组成的，所以 6 位的话，总共会有 62^6 ~= 568亿种组合。

ID作为重要组成单元，其不可重复性非常重要，在单机系统中，我们可以借助MySQL自增索引来获取ID，分布式环境中则可以借助Redis这类分布式K/V系统做发号器，来获取这个ID。

简单的生成短链接代码：

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
package main

import (
	"fmt"
	"math"
	"math/rand"
	"strconv"
	"strings"
	"time"
)

func random(min, max int) int {
	rand.Seed(time.Now().Unix())
	return rand.Intn(max-min) + min
}

var ALPHABET = strings.Split("adefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789", "")

func main() {
    // 填充短链接的长度
    // int64(random(1, 99))*int64(math.Pow(10, 9)) + ID 
	randNo := int64(random(1, 99))*int64(math.Pow(10, 9)) + 1000

	s := strconv.Itoa(int(randNo))
	fmt.Println(s)
	fmt.Println(GetShortUrl(randNo))
}

func GetShortUrl(id int64) string {
	indexAry := Encode62(id)
	return GetString62(indexAry)
}

// 转换成62进制
func Encode62(id int64) []int64 {
	indexAry := []int64{}
	base := int64(len(ALPHABET))

	for id > 0 { // i < 0 时,说明已经除尽了,已经到最高位,数字位已经没有了
		remainder := id % base
		indexAry = append(indexAry, remainder)
		id = id / base
	}

	return indexAry
}

//  输出字符串, 长度不一定为6
func GetString62(indexAry []int64) string {
	result := ""

	for val := range indexAry {
		result = result + ALPHABET[val]
	}

	return reverseString(result)
}

// 反转字符串
func reverseString(s string) string {
	runes := []rune(s)
	for from, to := 0, len(runes)-1; from < to; from, to = from+1, to-1 {
		runes[from], runes[to] = runes[to], runes[from]
	}
	return string(runes)
}