本文共 2476 字，大约阅读时间需要 8 分钟。

http://blog.csdn.net/beiyeqingteng/article/details/7706010

URL 解析：

当我们在浏览器里输入  时，DNS首先解析获得的IP地址。当DNS获得IP地址以后（比如：74.125.225.72），会向这个地址发送HTTP GET请求，查询 Jfs6q， 这个时候，服务器会把请求通过HTTP 301转到对应的长URL  。后面的解析过程就和平常网址解析是一样的了。

短址本质：

短址本质上是实现了一个映射函数 f: X -> Y 。而这个映射函数必须同时具有两个特点：

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

2. 对于每一个 y, 能够找到唯一的一个 x 使得 f(x) = y;

对于任何的线性函数，比如 f(x) = 2x，都满足这样的条件。

好了，如果了解了短址的本质，我们再来看它是如何实现的。

注明：在google URL shortener 服务中，它允许一个长 url 对应多个短的url。这可能是出于安全上的考虑。在本文中，我们不考虑这种情况。

实现：

短址的长度一般设为 6 位，而每一位是由 [a - z, A - Z, 0 - 9] 总共 62 个字母组成的，所以6位的话，总共会有 62^6 ~= 568亿种组合，基本上够用了。在google URL shortener 服务中，短址长度为 5，大概有9亿多种组合.

假设我们用数据库来保存长地址和短地址的映射，那么，在表 LongtoShortURL 中，我们会有三列：

1. ID，int,  自动增长；

2. LURL，varchar,  // 长URL；

3. SURL, varchar,  // 短URL。

现在我们考虑通过如何长URL得到唯一的短URL。

在讲具体算法以前，先提一个问题：10进制数和16进制数之间的转换是否满足刚刚提到的映射函数 f: X -> Y中的两个条件？

答案： 是。

本文的思路也是利用进制之间的转换。因为我们总共有 62 个字母，我们可以自创一种进制，叫做 62 进制。其规则如下：

0  → a1  → b...25 → z...52 → 061 → 9

所以，对于每一个长地址，我们可以根据它的ID，得到一个6位的 62 进制数，这个6位的 62 进制数就是我们的短址。具体实现如下：

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

举例：

对于 ID = 138，通过 base62(138), 我们得到 value = [14, 2]。根据上面的对应规则表，我们可以得到其对应的短址为：aaaabn 。(由 value 得到具体的短址，可以通过switch 语句得到，因为代码太长，在此略过。)

当我们想通过短址找到所对应的长地址，方法也很简单，就是把62进制数转成10进制数即可，这样我们就可以得到长地址的ID了。代码如下：

public static int base10(ArrayList
   
     base62) {	//make sure the size of base62 is 6	for (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;}
   

比如，对于短址aaae9a，其62进制为[0, 0, 0, 4,61,0] ，则其长地址的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，我们自然就可以得到长地址了。

参考： (本文算法来源)

转载请注明出处：