数据结构与算法-短连接生成器

Posted on | Edited on | In ,

通过hash算法产生短网址

要点：

  1. 选择冲撞小、高效的的hash函数，MurmueHash算法。有32bit和128bit，短连接我们可以选择32bits,求原始地址的hashCode
  2. 进一步缩短网址：网址我们一般会采用a-zA-Z0-9等62个字符，我们可以通过除法、并且取模来生成网址，见代码
  3. 解决Hash冲突，将原始地址和短连接地址保存起来（redis or mysql）等，当我们发现短连接已经存在并且和原始地址一致可直接返回，如果存在，且和原始地址不一致我们可以加一些额外字段,比如当前的纳秒数等等作为计算hash的种子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class ShortUrlGenerator {

    private static char[] charArray = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789".toCharArray();

    public static String genaratorCode(String input) {

        int code = Math.abs(MurmurHash.murmurhash3_x86_32(input, 0, input.length(), 0));

        List<Integer> list = new ArrayList<>();

        StringBuilder sb = new StringBuilder();
        while (code > 0) {
            //取模
            sb.append(charArray[code % charArray.length]);
            //整除
            code = code / charArray.length;
        }

        return sb.toString();
    }
}

通过自增ID

  • 对比上面的方式，对于相同的网址，我们会产生不同的短连接，但是会减少判重的次数（数据库的交互）
  • 自增ID是全局的，肯定要加锁，为了增加并发我们可以同时用多个发号器来解决，类似分库分表的思想。