短网址(Short URL) ,顾名思义就是看起来很短的网址。自从twitter推出短网址服务以后,各大互联网公司都推出了自己的短网址服务。短网址最大的优点就是短,字符少,便于发布、传播、复制和存储。
通过网上的搜索,感觉流传了2种短网址算法,一种是基于MD5码的,一种是基于自增序列的。
1、基于MD5码 : 这种算法计算的短网址长度一般是5位或者6位,计算过程中可能出现碰撞(概率很小),可表达的url数量为62
的5次方或6次方。感觉google(http://goo.gl),微博用的是类似这种的算法(猜的),可能看起来比较美观。
2、基于自增序列 : 这种算法实现比较简单,碰撞的可能性为0,可表达的URL可达无穷大,长度从1开始。貌似百度的短网址服务( http://dwz.cn/ )是这种算法.
具体算法
1、MD5码:假设url的长度为N
a.计算长地址的MD5码,将32位的MD码分成4段,每段8个字符
b.将a得到的8个字符串看成一个16进制的数,与N * 6个1表示的二进制数进行&操作
得到一个N * 6长的二进制数
c.将b得到的数分成N段,每段6位,然后将这N个6位数分别与61进行&操作,将得到的
数作为INDEX去字母表取相应的字母或数字,拼接就是一个长度为N的短网址。
1
2
3
4
5
|
static final char [] DIGITS =
{ '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' , '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
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
public String shorten(String longUrl, int urlLength) {
if (urlLength < 0 || urlLength > 6 ) {
throw new IllegalArgumentException( "the length of url must be between 0 and 6" );
}
String md5Hex = DigestUtils.md5Hex(longUrl);
// 6 digit binary can indicate 62 letter & number from 0-9a-zA-Z
int binaryLength = urlLength * 6 ;
long binaryLengthFixer = Long.valueOf(StringUtils.repeat( "1" , binaryLength), BINARY);
for ( int i = 0 ; i < 4 ; i++) {
String subString = StringUtils.substring(md5Hex, i * 8 , (i + 1 ) * 8 );
subString = Long.toBinaryString(Long.valueOf(subString, 16 ) & binaryLengthFixer);
subString = StringUtils.leftPad(subString, binaryLength, "0" );
StringBuilder sbBuilder = new StringBuilder();
for ( int j = 0 ; j < urlLength; j++) {
String subString2 = StringUtils.substring(subString, j * 6 , (j + 1 ) * 6 );
int charIndex = Integer.valueOf(subString2, BINARY) & NUMBER_61;
sbBuilder.append(DIGITS[charIndex]);
}
String shortUrl = sbBuilder.toString();
if (lookupLong(shortUrl) != null ) {
continue ;
} else {
return shortUrl;
}
}
// if all 4 possibilities are already exists
return null ;
}
|
2、自增序列:
a. 或者序列的自增值,将值用62进制表示。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
private AtomicLong sequence = new AtomicLong( 0 );
@Override
protected String shorten(String longUrl) {
long myseq = sequence.incrementAndGet();
String shortUrl = to62RadixString(myseq);
return shortUrl;
}
private String to62RadixString( long seq) {
StringBuilder sBuilder = new StringBuilder();
while ( true ) {
int remainder = ( int ) (seq % 62 );
sBuilder.append(DIGITS[remainder]);
seq = seq / 62 ;
if (seq == 0 ) {
break ;
}
}
return sBuilder.toString();
}
|
MAVEN工程中的代码用2个MAP来模拟存放长-短网址的互相映射,实际使用中可能是基于数据库表配合索引或者一些分布式KV系统来实现。
希望本文所述对大家学习短网址服务有所帮助。