前言

短網(wǎng)址，我想大家應(yīng)該都見過，如果沒有，試著點(diǎn)擊下面這條鏈接 https://git.io/vSY4o，會(huì)跳到我的 GitHub 主頁(yè)，但是它確實(shí)比原始鏈接 https://github.com/hanzichi 要短了一些。關(guān)于短網(wǎng)址的作用，這里不作描述，本文主要講講如何實(shí)現(xiàn)一個(gè)簡(jiǎn)單的短網(wǎng)址系統(tǒng)。

Leetcode 正好 有一題 與此有關(guān)，不妨一試。

思路

如果沒有接觸過短網(wǎng)址，不妨去 https://goo.gl/ 和 https://git.io/ 稍微體驗(yàn)下。體驗(yàn)的結(jié)果是，短網(wǎng)址都把網(wǎng)址壓縮成了六個(gè)字符，這是巧合嗎？

短網(wǎng)址整個(gè)運(yùn)轉(zhuǎn)邏輯非常簡(jiǎn)單，我們以 https://goo.gl/SfzlA2 為例，當(dāng)我們?cè)L問這個(gè)網(wǎng)址的時(shí)候，后端可以獲取 "SfzlA2" 這個(gè)字符串，然后跳轉(zhuǎn)到 https://github.com/hanzichi，很顯然，這個(gè)字符串和這個(gè)地址已經(jīng)綁定，通過某種映射關(guān)系可以從 "SfzlA2" 獲取完整的地址。

那么，看起來我們只需要找到一個(gè)算法，能夠?qū)⒁粋€(gè)長(zhǎng)字符串壓縮成一個(gè)短的字符串，并且該算法應(yīng)該是可逆的。但是實(shí)現(xiàn)這樣的文本壓縮算法，是非常困難的（不存在？），如果真有這么一個(gè)算法和逆運(yùn)算，那么基本上現(xiàn)在的壓縮軟件都可以歇菜了，而世界上所有的信息（網(wǎng)址長(zhǎng)度未知），都可以壓縮成固定長(zhǎng)度個(gè)字符，這可能嗎？所以不要幻想使用壓縮算法，而且對(duì)于 URL 這種不超過 100 bytes 的字符串，壓縮算法的壓縮比通常都大于 1。

所以我們應(yīng)該轉(zhuǎn)變思路。目前流行的短網(wǎng)址算法大概有兩種，一種是利用 md5，將長(zhǎng)網(wǎng)址 md5 后，再進(jìn)行分組壓縮，因?yàn)?md5 實(shí)質(zhì)上是一種哈希算法，所以難免出現(xiàn)碰撞，當(dāng)然，我們有解決哈希沖突的 N 種方法，但是這只會(huì)增加系統(tǒng)的復(fù)雜度，不推薦。另外一種是將網(wǎng)址和一個(gè) 62 進(jìn)制數(shù)（0-9 & a-Z）對(duì)應(yīng)，存入數(shù)據(jù)庫(kù)中，需要的時(shí)候，通過數(shù)據(jù)庫(kù)查詢提取。

實(shí)現(xiàn)

接著我們就根據(jù)以上的思路，來實(shí)現(xiàn)一個(gè)簡(jiǎn)單的短網(wǎng)址系統(tǒng)。

我們先不考慮 62 進(jìn)制的轉(zhuǎn)換，用 Map 來當(dāng)做一個(gè) k-v 的數(shù)據(jù)庫(kù)。當(dāng)存入第一個(gè)網(wǎng)址的時(shí)候，假設(shè)我們的短網(wǎng)址是 xx.com/0，可以將 0 當(dāng)做 key，將實(shí)際網(wǎng)址當(dāng)做 value，需要查詢的時(shí)候直接提取，如果有新的短網(wǎng)址需要生成，將 key 自增。代碼如下。

復(fù)制代碼let [p, index] = [new Map(), 0];/** * Encodes a URL to a shortened URL. * * @param {string} longUrl * @return {string} */var encode = function(longUrl) {
  p.set(index, longUrl);
  return index++;};/** * Decodes a shortened URL to its original URL. * * @param {string} shortUrl * @return {string} */var decode = function(shortUrl) {
  return p.get(shortUrl);};

很顯然，用一個(gè) 62 進(jìn)制數(shù)表示，短網(wǎng)址可以更短。我們可以自己實(shí)現(xiàn)一個(gè)簡(jiǎn)單的 10 進(jìn)制到 62 進(jìn)制的轉(zhuǎn)換算法。

復(fù)制代碼let [p, index] = [new Map(), 0];var base62 = (n) => {
  let str = '0123456789abcdefghigklmnopqrstuvwxyzABCDEFGHIGKLMNOPQRSTUVWXYZ';
  let len = str.length;
  let ret = '';

  do {
    ret += str[n % len];
    n = ~~(n / len);
  } while (n);

  return ret;};/** * Encodes a URL to a shortened URL. * * @param {string} longUrl * @return {string} */var encode = function(longUrl) {
  let shortUrl = base62(index++);
  p.set(shortUrl, longUrl);
  return shortUrl;};/** * Decodes a shortened URL to its original URL. * * @param {string} shortUrl * @return {string} */var decode = function(shortUrl) {
  return p.get(shortUrl);};

這樣實(shí)現(xiàn)的話實(shí)際的短網(wǎng)址的數(shù)量其實(shí)是受限的，理論上應(yīng)該是（JavaScript）能表示的最大的整數(shù)。

其他

這樣的實(shí)現(xiàn)，還有一些其他的問題，比如短網(wǎng)址的長(zhǎng)度并不是固定的，這點(diǎn)容易解決，補(bǔ)位即可。再比如，這些短網(wǎng)址，按照順序排列，并不顯得隨機(jī)，這也好辦，比如可以隨機(jī)生成六位字符串當(dāng)作 key，而不是用整數(shù)的遞增，這樣的話，短網(wǎng)址數(shù)量也不受限了（可以增加短網(wǎng)址位數(shù)）。還有一點(diǎn)，相同的 URL 可能得到不同的短網(wǎng)址，這點(diǎn)可以另外加個(gè)哈?；蛘哂?Set 去解決，還可以加個(gè)緩存來解決（在緩存時(shí)間內(nèi)，重定向到相同地址，一旦緩存失效，重新分配 key）。

除了算法設(shè)計(jì)外，真正的系統(tǒng)還需要考慮很多，比如發(fā)號(hào)器的設(shè)計(jì)，比如緩存（掛個(gè) Redis），比如跳轉(zhuǎn)，等等，本文只是拋磚引玉，這些就留給你們自己去思考了。

短網(wǎng)址系統(tǒng)的設(shè)計(jì)，其實(shí)依賴的并不是文本壓縮算法。有些時(shí)候，需要換個(gè)角度思考問題。

參考

可能是史上最詳細(xì)的 underscore 源碼剖析：https://github.com/hanzichi/underscore-analysis
程序員都應(yīng)該學(xué)點(diǎn)算法：https://github.com/hanzichi/leetcode
了解博主韓子遲：http://www.cnblogs.com/zichi/p/about.html
GitHub：https://github.com/hanzichi Follow 樓主給樓主更多寫作的動(dòng)力~

http://www.cnblogs.com/zichi/p/6648649.html