两种JAVA实现短网址服务算法
短网址（ShortURL），顾名思义就是看起来很短的网址。自从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的短网址。
staticfinalchar[]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'};
publicStringshorten(StringlongUrl,inturlLength){
if(urlLength<0||urlLength>6){
thrownewIllegalArgumentException("thelengthofurlmustbebetween0and6");
}
Stringmd5Hex=DigestUtils.md5Hex(longUrl);
//6digitbinarycanindicate62letter&numberfrom0-9a-zA-Z
intbinaryLength=urlLength*6;
longbinaryLengthFixer=Long.valueOf(StringUtils.repeat("1",binaryLength),BINARY);
for(inti=0;i<4;i++){
StringsubString=StringUtils.substring(md5Hex,i*8,(i+1)*8);
subString=Long.toBinaryString(Long.valueOf(subString,16)&binaryLengthFixer);
subString=StringUtils.leftPad(subString,binaryLength,"0");
StringBuildersbBuilder=newStringBuilder();
for(intj=0;j<urlLength;j++){
StringsubString2=StringUtils.substring(subString,j*6,(j+1)*6);
intcharIndex=Integer.valueOf(subString2,BINARY)&NUMBER_61;
sbBuilder.append(DIGITS[charIndex]);
}
StringshortUrl=sbBuilder.toString();
if(lookupLong(shortUrl)!=null){
continue;
}else{
returnshortUrl;
}
}
//ifall4possibilitiesarealreadyexists
returnnull;
}
2、自增序列：
a.或者序列的自增值，将值用62进制表示。
privateAtomicLongsequence=newAtomicLong(0);
@Override
protectedStringshorten(StringlongUrl){
longmyseq=sequence.incrementAndGet();
StringshortUrl=to62RadixString(myseq);
returnshortUrl;
}
privateStringto62RadixString(longseq){
StringBuildersBuilder=newStringBuilder();
while(true){
intremainder=(int)(seq%62);
sBuilder.append(DIGITS[remainder]);
seq=seq/62;
if(seq==0){
break;
}
}
returnsBuilder.toString();
}
MAVEN工程中的代码用2个MAP来模拟存放长-短网址的互相映射，实际使用中可能是基于数据库表配合索引或者一些分布式KV系统来实现。
希望本文所述对大家学习短网址服务有所帮助。