两种JAVA实现短网址服务算法
程序员文章站
2024-03-06 09:48:31
短网址(short url) ,顾名思义就是看起来很短的网址。自从twitter推出短网址服务以后,各大互联网公司都推出了自己的短网址服务。短网址最大的优点就是短,字符少,...
短网址(short url) ,顾名思义就是看起来很短的网址。自从twitter推出短网址服务以后,各大互联网公司都推出了自己的短网址服务。短网址最大的优点就是短,字符少,便于发布、传播、复制和存储。
通过网上的搜索,感觉流传了2种短网址算法,一种是基于md5码的,一种是基于自增序列的。
1、基于md5码 : 这种算法计算的短网址长度一般是5位或者6位,计算过程中可能出现碰撞(概率很小),可表达的url数量为62
的5次方或6次方。感觉google(),微博用的是类似这种的算法(猜的),可能看起来比较美观。
2、基于自增序列 : 这种算法实现比较简单,碰撞的可能性为0,可表达的url可达无穷大,长度从1开始。貌似百度的短网址服务( )是这种算法.
具体算法
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的短网址。
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' };
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进制表示。
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系统来实现。
希望本文所述对大家学习短网址服务有所帮助。