前言：

最近看了一些關(guān)于短址（short URL）方面的一些博客，有些博客說(shuō)到一些好的東西，但是，也不是很全，所以，這篇博客算是對(duì)其它博客的一個(gè)總結(jié)吧。

介紹：

短址，顧名思義，就是把長(zhǎng)的 URL 轉(zhuǎn)成短的 URL, 現(xiàn)在提供這種服務(wù)的有很多公司，我們以google家的 URL shortener 服務(wù)： http://goo.gl/ 為例。

首先我們到 http://goo.gl/，然后把本文博客的地址http://blog.csdn.net/beiyeqingteng 輸入進(jìn)去，最后它會(huì)返回一個(gè)更短的URL，http://goo.gl/Jfs6q 。如下圖所示：

URL 解析：

當(dāng)我們?cè)跒g覽器里輸入 http://goo.gl/Jfs6q 時(shí)，DNS首先解析獲得http://goo.gl/的IP地址。當(dāng)DNS獲得IP地址以后（比如：74.125.225.72），會(huì)向這個(gè)地址發(fā)送HTTP GET請(qǐng)求，查詢(xún) Jfs6q， 這個(gè)時(shí)候，http://goo.gl/服務(wù)器會(huì)把請(qǐng)求通過(guò)HTTP 301轉(zhuǎn)到對(duì)應(yīng)的長(zhǎng)URL http://blog.csdn.net/beiyeqingteng 。后面的解析過(guò)程就和平常網(wǎng)址解析是一樣的了。

短址本質(zhì)：

短址本質(zhì)上是實(shí)現(xiàn)了一個(gè)映射函數(shù) f: X -> Y 。而這個(gè)映射函數(shù)必須同時(shí)具有兩個(gè)特點(diǎn)：

1. 如果 x1 != x2, 則 f (x1) != f(x2);

2. 對(duì)于每一個(gè) y, 能夠找到唯一的一個(gè) x 使得 f(x) = y;

對(duì)于任何的線性函數(shù)，比如 f(x) = 2x，都滿(mǎn)足這樣的條件。

好了，如果了解了短址的本質(zhì)，我們?cè)賮?lái)看它是如何實(shí)現(xiàn)的。

注明：在google URL shortener 服務(wù)中，它允許一個(gè)長(zhǎng) url 對(duì)應(yīng)多個(gè)短的url。這可能是出于安全上的考慮。在本文中，我們不考慮這種情況。

實(shí)現(xiàn)：

短址的長(zhǎng)度一般設(shè)為 6 位，而每一位是由 [a - z, A - Z, 0 - 9] 總共 62 個(gè)字母組成的，所以6位的話，總共會(huì)有 62^6 ~= 568億種組合，基本上夠用了。在google URL shortener 服務(wù)中，短址長(zhǎng)度為 5，大概有9億多種組合.

假設(shè)我們用數(shù)據(jù)庫(kù)來(lái)保存長(zhǎng)地址和短地址的映射，那么，在表 LongtoShortURL 中，我們會(huì)有三列：

1. ID，int, ?自動(dòng)增長(zhǎng)；

2. LURL，varchar, ?// 長(zhǎng)URL；

3. SURL, varchar, ?// 短URL。

現(xiàn)在我們考慮通過(guò)如何長(zhǎng)URL得到唯一的短URL。

在講具體算法以前，先提一個(gè)問(wèn)題：10進(jìn)制數(shù)和16進(jìn)制數(shù)之間的轉(zhuǎn)換是否滿(mǎn)足剛剛提到的映射函數(shù) f: X -> Y中的兩個(gè)條件？

答案： 是。

本文的思路也是利用進(jìn)制之間的轉(zhuǎn)換。因?yàn)槲覀兛偣灿?62 個(gè)字母，我們可以自創(chuàng)一種進(jìn)制，叫做 62 進(jìn)制。其規(guī)則如下：

0 ?→ a
1 ?→ b
...
25 → z
...
52 → 0
61 → 9

所以，對(duì)于每一個(gè)長(zhǎng)地址，我們可以根據(jù)它的ID，得到一個(gè)6位的 62 進(jìn)制數(shù)，這個(gè)6位的 62 進(jìn)制數(shù)就是我們的短址。具體實(shí)現(xiàn)如下：

public ArrayList<Integer> base62(int id) {ArrayList<Integer> value = new ArrayList<Integer>();while (id > 0) {int remainder = id % 62;value.add(remainder);id = id / 62;}return value;
}

舉例：

對(duì)于 ID = 138，通過(guò) base62(138), 我們得到 value = [14, 2]。根據(jù)上面的對(duì)應(yīng)規(guī)則表，我們可以得到其對(duì)應(yīng)的短址為：aaaabn 。(由 value 得到具體的短址，可以通過(guò)switch 語(yǔ)句得到，因?yàn)榇a太長(zhǎng)，在此略過(guò)。)

當(dāng)我們想通過(guò)短址找到所對(duì)應(yīng)的長(zhǎng)地址，方法也很簡(jiǎn)單，就是把62進(jìn)制數(shù)轉(zhuǎn)成10進(jìn)制數(shù)即可，這樣我們就可以得到長(zhǎng)地址的ID了。代碼如下：

public static int base10(ArrayList<Integer> base62) {//make sure the size of base62 is 6for (int i = 1; i <= 6 - base62.size(); i++) {base62.add(0, 0);}int id = 0;int size = base62.size();for (int i = 0; i < size; i++) {int value = base62.get(i);id += (int) (value * Math.pow(62, size - i - 1));}return id;
}

比如，對(duì)于短址aaae9a，其62進(jìn)制為[0, 0, 0, 4,61,0] ，則其長(zhǎng)地址的ID 為[0, 0, 0, 4,61,0] = 0×62^5+ 0×62^4 + 0×62^3 + 4×62^2 + 61×62^1 + 0×62^0 = 1915810。有了ID，我們自然就可以得到長(zhǎng)地址了。

參考：http://stackoverflow.com/questions/742013/how-to-code-a-url-shortener (本文算法來(lái)源)

http://blog.sina.com.cn/s/blog_65db99840100lg4n.html
?

原文地址：https://blog.csdn.net/beiyeqingteng/article/details/7706010