マイクロ博短リンク生成アルゴリズムと簡単な実現
2775 ワード
Twitterがショートサイト(shorturl)を発売してから、国内でも多くのインターネット会社がショートサイトリンクを発売しています.例えば、微博などです.
次は、ネット上でいくつかのアルゴリズムのまとめです.
アルゴリズム1:
最も考えやすいアルゴリズムはmd 5クラスの暗号化アルゴリズムを用い,暗号化後の文字列に対して処理する可能性がある.1)長いウェブサイトmd 5を32ビットの署名列を生成し、4セグメントに分け、各セグメント8バイト;
2)この4つのループ処理に対して、8バイトを取って、彼を16進列と0 x 3 fffffffff(30ビット1)と操作、すなわち30ビットを超える無視処理と見なす.
3)この30ビットは6セグメントに分けられ、5ビットの数字ごとにアルファベットのインデックスとして特定文字を取得し、順次6ビット文字列を取得する.
4)全md 5列は4個の6ビット列を得ることができる.中のいずれかを取ると、この長いurlの短いurlアドレスになります.
アルゴリズム2:
a-zA-Z 0-9この64ビットは6ビットの組み合わせをとり、500億個以上の組み合わせを生成することができる.数字と文字の組み合わせを一定のマッピングをすると、62番目の組み合わせがaaaaa 9、63番目の組み合わせがaaaaabaのように、トランプアルゴリズムを再利用して元の文字列を乱して保存すると、対応する位置の組み合わせ文字列は無秩序な組み合わせになります.
長いURLをデータベースに格納、返されたidを取り、対応する文字列を探し出し、例えば返されたIDが1であれば、対応する上の文字列の組み合わせがbbbであり、同理IDが2である場合、文字列の組み合わせがbbaとなり、64種類の組み合わせに達するまで順番に類推されるので、上の62文字で任意に6文字を文字列に組み合わせると、あなたのデータストレージは500億以上に達してから重複する可能性があります.
次に、8ビットのインスタントコードを返す短いウェブサイトアルゴリズムを簡単にシミュレートし、アルゴリズムに基づいて1つを実現します.
短いURLリンクを生成する場合は、元のリンクと短いリンクのマッピング関係をテーブル(データベースまたはクラスNoSqlのK-Vストレージ)に格納するだけでよい.
次は、ネット上でいくつかのアルゴリズムのまとめです.
アルゴリズム1:
最も考えやすいアルゴリズムはmd 5クラスの暗号化アルゴリズムを用い,暗号化後の文字列に対して処理する可能性がある.1)長いウェブサイトmd 5を32ビットの署名列を生成し、4セグメントに分け、各セグメント8バイト;
2)この4つのループ処理に対して、8バイトを取って、彼を16進列と0 x 3 fffffffff(30ビット1)と操作、すなわち30ビットを超える無視処理と見なす.
3)この30ビットは6セグメントに分けられ、5ビットの数字ごとにアルファベットのインデックスとして特定文字を取得し、順次6ビット文字列を取得する.
4)全md 5列は4個の6ビット列を得ることができる.中のいずれかを取ると、この長いurlの短いurlアドレスになります.
アルゴリズム2:
a-zA-Z 0-9この64ビットは6ビットの組み合わせをとり、500億個以上の組み合わせを生成することができる.数字と文字の組み合わせを一定のマッピングをすると、62番目の組み合わせがaaaaa 9、63番目の組み合わせがaaaaabaのように、トランプアルゴリズムを再利用して元の文字列を乱して保存すると、対応する位置の組み合わせ文字列は無秩序な組み合わせになります.
長いURLをデータベースに格納、返されたidを取り、対応する文字列を探し出し、例えば返されたIDが1であれば、対応する上の文字列の組み合わせがbbbであり、同理IDが2である場合、文字列の組み合わせがbbaとなり、64種類の組み合わせに達するまで順番に類推されるので、上の62文字で任意に6文字を文字列に組み合わせると、あなたのデータストレージは500億以上に達してから重複する可能性があります.
次に、8ビットのインスタントコードを返す短いウェブサイトアルゴリズムを簡単にシミュレートし、アルゴリズムに基づいて1つを実現します.
public class ShortUrlUtil {
static char hexDigits[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8',
'9', 'a', 'b', 'c', 'd', 'e', 'f' };
public static String shortUrl(String url) throws Exception {
MessageDigest messagedigest = MessageDigest.getInstance("MD5");
messagedigest.update(url.getBytes());
String result = bufferToHex(messagedigest.digest());
String resUrl = new String("");
for (int i = 0; i < 8; i++) {
String tmpString = result.substring(i * 4, i * 4 + 4);
long hexLong = 0x3FFFFFFF & Long.parseLong(tmpString, 16);
resUrl += hexDigits[Integer.valueOf((hexLong % 16) + "")] + "";
}
return resUrl;
}
private static String bufferToHex(byte bytes[]) {
return bufferToHex(bytes, 0, bytes.length);
}
private static String bufferToHex(byte bytes[], int m, int n) {
StringBuffer stringbuffer = new StringBuffer(2 * n);
int k = m + n;
for (int l = m; l < k; l++) {
appendHexPair(bytes[l], stringbuffer);
}
return stringbuffer.toString();
}
private static void appendHexPair(byte bt, StringBuffer stringbuffer) {
char c0 = hexDigits[(bt & 0xf0) >> 4];
char c1 = hexDigits[bt & 0xf];
stringbuffer.append(c0);
stringbuffer.append(c1);
}
public static void main(String[] args) {
String sLongUrl = "http://weibo.com/taobaotianshui?wvr=5&wvr=5&lf=reg";
String shortUrl;
try {
shortUrl = shortUrl(sLongUrl);
System.out.println(sLongUrl + " ===> " + shortUrl);
} catch (Exception e) {
e.printStackTrace();
}
}
}
短いURLリンクを生成する場合は、元のリンクと短いリンクのマッピング関係をテーブル(データベースまたはクラスNoSqlのK-Vストレージ)に格納するだけでよい.