Golang 短网址服务核心代码

在一些应用的分享文案中，经常需要包含一个打开实际页面的链接，而这个链接可能会非常的长（因为可能会有很多很多参数。。）这样的分享文案不仅不够美观，而且在一些平台会受到限制，比如weibo的140字。这时候我们就需要采用一个短链接服务了。
短链服务实际上是对长链接的一个1对N映射。在访问短链的时候，通过应用或web服务器进行跳转，就能访问到实际的页面。我们只需将长链完成映射，存储这样的对应关系，就实现了短链生成服务。

算法

将任意一条长链接映射为6位字符长度的字符串，而不会造成短链接的重复。（不是绝对的，在一个很大数量级的数值之内）

1. 将原长链接进行md5校验和计算，生成32位字符串。
2. 将32位字符串每8位划分一段，得到4段子串。将每个字串（16进制形式）转化为整型数值，与0x3FFFFFFF（30位1）按位与运算，生成一个30位的数值。
3. 将上述生成的30位数值按5位为单位依次提取，得到的数值与0x0000003D按位与，获取一个0-61的整型数值，作为从字符数组中提取字符的索引。得到6个字符就生成了一个短链。
4. 4段字串共可以生成4个短链。

func Transform(longURL string) ([4]string, error) {
    md5Str := getMd5Str(longURL)
    //var hexVal int64
    var tempVal int64
    var result [4]string
    var tempUri []byte
    for i := 0; i < 4; i++ {
        tempSubStr := md5Str[i*8 : (i+1)*8]
        hexVal, err := strconv.ParseInt(tempSubStr, 16, 64)
        if err != nil {
            return result, nil
        }
        tempVal = int64(VAL) &amp; hexVal
        var index int64
        tempUri = []byte{}
        for i := 0; i < 6; i++ {
            index = INDEX &amp; tempVal
            tempUri = append(tempUri, alphabet[index])
            tempVal = tempVal >> 5
        }
        result[i] = string(tempUri)
    }
    return result, nil
}

/** generate md5 checksum of URL in hex format **/
func getMd5Str(str string) string {
    m := md5.New()
    m.Write([]byte(str))
    c := m.Sum(nil)
    return hex.EncodeToString(c)
}

短链接原理

原理其实很简单，前端给后端传一个字符串，然后根据这个字符串找到原网址，最后返回一个301即可。所以短网址算法主要就是研究如何根据原网址算出这个字符串以及如何根据字符串找到这个网址。

短链接算法

常用的短链接算法主要有两种：自增ID和哈希

哈希

顾名思义，哈希就是将原网址计算出一个哈希字符串，但是这种算法碰到哈希碰撞时，会存在重复的情况，这个时候就有可能需要再哈希或者进行其他的处理。

自增ID

所以这里我们选择使用自增ID的方法，我们先将原网址存入数据，然后使用数据库返回的id，将id换算成六十二进制的字符串（随机的大小写字母+数字），数据库也不需要存储这个字符串，直接返回给前端即可。当前端请求这个字符串时，再转成十进制的id即可找到原网址。go进制转换与随机62进制字符串代码：

import (
    "io"
    "log"
    "math"
    "math/rand"
    "os"
    "path/filepath"
    "regexp"
    "strings"
)

var CHARS = "InsV3Sf0obzp2i4gj1yYGqQv6wUtmBxlMAP7KHd8uTXFk9aRJWNC5EOhZDcLer"

const (
    // 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ
    SCALE = 62
    REGEX = "^[0-9a-zA-Z]+$"
    NUM = 6
)

func RandomStr(str string) string {
    chars := []rune(str)
    for i := len(chars) - 1; i > 0; i-- {
        num := rand.Intn(i + 1)
        chars[i], chars[num] = chars[num], chars[i]
    }
    return string(chars)
}

func Encode10To62(val uint) string {
    if val < 0 {
        panic("val cannot be negative.")
    }
    str := ""
    var remainder int
    for math.Abs(float64(val)) > SCALE-1 {
        remainder = int(val % SCALE)
        str = string(CHARS[remainder]) + str
        val = val / SCALE
    }
    str = string(CHARS[val]) + str
    //for i := len(str); i < NUM; i++ {
    //    str = string(CHARS[0]) + str
    //}
    return str
}

func Decode62To10(val string) uint {
    if match, _ := regexp.MatchString(REGEX, val); !match {
        panic("input illegal.")
    }
    var result uint = 0
    index, length := 0, len(val)
    for i := 0; i < length; i++ {
        index = strings.Index(CHARS, string(val[i]))
        result += uint(index * int(math.Pow(float64(SCALE), float64(length-i-1))))
    }
    return result
}

今天看到了一个比较有想法的缩短算法

主要是使用了 MurmurHash 哈希算法

package main

/**
CREATE TABLE `short_url_map` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT,
  `lurl` varchar(160) DEFAULT NULL COMMENT '长地址',
  `surl` varchar(10) DEFAULT NULL COMMENT '短地址',
  `gmt_create` int(11) DEFAULT NULL COMMENT '创建时间',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
*/

import (
    "github.com/spaolacci/murmur3"
    "fmt"
    "math"
    "bytes"
)

// characters used for conversion
const alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

// converts number to base62
func Encode(number int) string {
  if number == 0 {
    return string(alphabet[0])
  }

  chars := make([]byte, 0)

  length := len(alphabet)

  for number > 0 {
    result    := number / length
    remainder := number % length
    chars   = append(chars, alphabet[remainder])
    number  = result
  }

  for i, j := 0, len(chars) - 1; i < j; i, j = i + 1, j - 1 {
    chars[i], chars[j] = chars[j], chars[i]
  }

  return string(chars)
}

// converts base62 token to int
func Decode(token string) int {
  number := 0
  idx    := 0.0
  chars  := []byte(alphabet)

  charsLength := float64(len(chars))
  tokenLength := float64(len(token))

  for _, c := range []byte(token) {
    power := tokenLength - (idx + 1)
    index := bytes.IndexByte(chars, c)
    number += index * int(math.Pow(charsLength, power))
    idx++
  }

  return number
}

func main() {
    incr := murmur3.Sum32([]byte("https://u.geekbang.org/subject/python/100038901?utm_source=wechat&amp;utm_medium=pyq02282300&amp;utm_term=wechatpyq02282300"))
    fmt.Println(incr)
    fmt.Println(Encode(int(incr)))
}

还可以使用 https://github.com/speps/go-hashids.git 做转换。