URL 短地址壓縮算法微博短地址原理短網(wǎng)址應(yīng)用已經(jīng)在全國各大微博上開始流行了起來。例如QQ 微博的url.cn ，新郎的sinaurl.cn 等。我們在QQ 微博上發(fā)布網(wǎng)址的時候，微博會自動判別網(wǎng)址，

URL 短地址壓縮算法微博短地址原理

短網(wǎng)址應(yīng)用已經(jīng)在全國各大微博上開始流行了起來。例如QQ 微博的url.cn ，新郎的sinaurl.cn 等。

我們在QQ 微博上發(fā)布網(wǎng)址的時候，微博會自動判別網(wǎng)址，并將其轉(zhuǎn)換，例如：http://url.cn/2hytQx

為什么要這樣做的，原因我想有這樣幾點：

1. 微博限制字?jǐn)?shù)為140字一條，那么如果我們需要發(fā)一些連接上去，但是這個連接非常的長，以至于將近要占用我們內(nèi)容的一半篇幅，這肯定是不能被允許的，所以短網(wǎng)址應(yīng)運(yùn)而生了。

2. 短網(wǎng)址可以在我們項目里可以很好的對開放級URL 進(jìn)行管理。有一部分網(wǎng)址可以會涵蓋暴力，廣告等信息，這樣我們可以通過用戶的舉報，完全管理這個連接將不出現(xiàn)在我們的應(yīng)用中，應(yīng)為同樣的URL 通過加密算法之后，得到的地址是一樣的。

3. 我們可以對一系列的網(wǎng)址進(jìn)行流量，點擊等統(tǒng)計，挖掘出大多數(shù)用戶的關(guān)注點，這樣有利于我們對項目的后續(xù)工作更好的作出決策。

其實以上三點純屬個人觀點，因為在我接下來的部分項目中會應(yīng)用到，所以就了解了一下，下面先來看看短網(wǎng)址映射算法的理論（網(wǎng)上找到的資料）：

1. 將長網(wǎng)址md5生成32位簽名串，分為4段，每段8個字節(jié)；

2. 對這四段循環(huán)處理，取8個字節(jié)，將他看成16進(jìn)制串與0x3fffffff(30位1) 與操作，即超過30位的忽略處理；

3. 這30位分成6段，每5位的數(shù)字作為字母表的索引取得特定字符，依次進(jìn)行獲得6位字符串；

4. 總的md5串可以獲得4個6位串；取里面的任意一個就可作為這個長url 的短url 地址；

很簡單的理論，我們并不一定說得到的URL 是唯一的，但是我們能夠取出4組URL ，這樣幾乎不會出現(xiàn)太大的重復(fù)。

下面來看看程序部分：

1. public static string [] ShortUrl( string url)

2. {

3. //可以自定義生成MD5加密字符傳前的混合KEY

4. string key = "Leejor" ;

5. //要使用生成URL 的字符

6. string [] chars = new string []{

7. "a" , "b" , "c" , "d" , "e" , "f" , "g" , "h" ,

8. "i" , "j" , "k" , "l" , "m" , "n" , "o" , "p" ,

9. "q" , "r" , "s" , "t" , "u" , "v" , "w" , "x" ,

10. "y" , "z" , "0" , "1" , "2" , "3" , "4" , "5" ,

11. "6" , "7" , "8" , "9" , "A" , "B" , "C" , "D" ,

12. "E" , "F" , "G" , "H" , "I" , "J" , "K" , "L" ,

13. "M" , "N" , "O" , "P" , "Q" , "R" , "S" , "T" ,

14. "U" , "V" , "W" , "X" , "Y" , "Z"

15. };

16.

17. //對傳入網(wǎng)址進(jìn)行MD5加密

18. string hex = System.Web.Security.FormsAuthentication.HashPasswordFo

rStoringInConfigFile(key url, "md5" );

19.

20. string [] resUrl = new string [4];

21.

22. for ( int i = 0; i < 4; i )

23. {

24. //把加密字符按照8位一組16進(jìn)制與0x3FFFFFFF 進(jìn)行位與運(yùn)算

25. int hexint = 0x3FFFFFFF & Convert.ToInt32( "0x" hex.Substrin

g(i * 8, 8), 16);

26. string outChars = string .Empty;

27. for ( int j = 0; j < 6; j )

28. {

29. //把得到的值與0x0000003D 進(jìn)行位與運(yùn)算，取得字符數(shù)組chars 索

引

30. int index = 0x0000003D & hexint;

31. //把取得的字符相加

32. outChars = chars[index];

33. //每次循環(huán)按位右移5位

34. hexint = hexint >> 5;

35. }

36. //把字符串存入對應(yīng)索引的輸出數(shù)組

37. resUrl[i] = outChars;

38. }

39. return resUrl;

40. }

現(xiàn)在可以直接使用該方法，可以等到下面四組值：

得到值fAVfui 得到值3ayQry 得到值UZzyUr 得到值36rQZn

在存放這個URL 的數(shù)據(jù)方面，我個人推薦TTServer ，有的朋友可以沒有聽說過，下面是這個數(shù)據(jù)庫的介紹：

Tokyo Cabinet 是日本人 Mikio Hirabayashi（平林幹雄）のページ 開發(fā)的一款DBM 數(shù)據(jù)庫(注：大名鼎鼎的DBM 數(shù)據(jù)庫qdbm 就是他開發(fā)的) ，該數(shù)據(jù)庫讀寫非?？?。

insert:0.4sec/1000000 recordes(2500000qps)，寫入100萬數(shù)據(jù)只需要0.4秒。

search:0.33sec/1000000 recordes (3000000 qps)，讀取100萬數(shù)據(jù)只需要0.33秒。 可以看到對于字典類型的數(shù)據(jù)Key/Value的查詢，這個數(shù)據(jù)庫可以說是我目前見過效率非常高的，況且他如此的小巧，用來對short url/long url的配對再好不過。

該系統(tǒng)使用6個短碼字符來表示任何長度的網(wǎng)址。 有效的字符代碼是ASCII 'A' 到'Z' 和'0' 的'5' ，其中每個字符包含2 ^ 5（32）狀態(tài)。 6短碼字符可用于繪制32 ^ 6（1073741824）

的網(wǎng)址

首先，你需要一個數(shù)據(jù)庫表來存儲和檢索你映射的網(wǎng)址。

1. CREATE TABLE mappedURL (的CREATE TABLE mappedURL（

2. shortCode char (6) not null ,

3. lognURL text not null ,

4. PRIMARY KEY shortCodeInd (shortCode),

5. );

其次，你需要定義一個算法將長的URL 映射到短的URL 。 算法上面已經(jīng)介紹過了。

第三，你需要創(chuàng)建一個網(wǎng)頁，從數(shù)據(jù)庫的短網(wǎng)址的映射找到原始的URL, 并重定向之。 ---------------------------------------------------------

MD5 已經(jīng)被破解了，因此不排除攻擊者偽造相同 MD5 的 url 實現(xiàn)惡意目的的可能性。如果不考慮這種情況，md5 collision 的可能性應(yīng)該是及其低的，估計你我有生之年都看不到。 另外偶不明白“相同的URL 每次算出來的鍵值必須都是一樣的”的實際用途會是什么。就算相同的 URL 對應(yīng)不同的鍵值，一般也不會造成太大的浪費吧？只有 6 位的字母數(shù)字組合都可以容納幾十億種變化。

我正是有md5 collision 的擔(dān)心才問這個問題的。相同的URL 要對應(yīng)相同的鍵值是因為每一個URL 地址都需要唯一的對應(yīng)到數(shù)據(jù)庫中的一條表數(shù)據(jù)，但直接用URL 來查詢會比較慢，因為：

1. 將要存儲的URL 和相關(guān)的記錄數(shù)據(jù)量非常大。

2. 而且有些URL 會很長，所以要用text 字段。

而如果哈希出唯一的鍵值用varchar 來存儲，再根據(jù)這個鍵值去查詢就會非常方便快捷。

就像git 里面的object hash， 目前基本上不用考慮沖突吧。

?

? bit.ly 等url shorter服務(wù)是怎么實現(xiàn)的？ 需不需要從hash 鍵值反向查找url ？ 如果有這樣的要求， url肯定需要存一個地

方， 這樣就可以在沖突的時候進(jìn)行再散列

MD5是128位hash 碼（4個整數(shù)，每個整數(shù)4個字節(jié)）。因此，一個url 的MD5碼，有2的128次方（即2e128）個可能。隨意找出來的兩個url 的MD5碼相等的可能性，是2e128分之一，即r=2e-128

假如url 經(jīng)MD5后插入數(shù)據(jù)庫，第一個url 插入的不會發(fā)生重復(fù)，第二個MD5插入時，它跟

第一條重復(fù)的概率是r 。第三條url 插入時，重復(fù)概率是2×r ，以此類推，第n 條插入時發(fā)生重復(fù)的概率是(n-1)×r 。n 個MD5碼，其中有兩個重復(fù)的概率是這些概率加和。（1＋2＋3＋... (n- 1))×r = (1/2)×n ×(n-1)×r

對于n 個MD5碼的集合，存在重復(fù)的概率是（1/2)*(n/2e64)e2

因此，只有n 大到可以與2e64比擬，才需要考慮它的沖突問題。而2的64次方還是很大的。 所以，只要不是惡意攻擊，一般應(yīng)用是不太會有collision 的