不過，通過 MurmurHash 算法得到的短鍊還是很長啊。别着急，我們隻需要稍微改變一個哈希值的表示方法，就可以輕松把短鍊變得更短些。
将 10 進制的哈希值，轉化成更高進制的哈希值，這樣哈希值就變短了。
16 進制中，用 A～F，來表示 10～15。在網址 URL 中，常用的合法字元有 0～9、a～z、A～Z 這樣 62 個字元。為了讓哈希值表示起來盡可能短，我們可以将 10 進制的哈希值轉化成 62 進制。具體的計算過程如下圖。最終用 62 進制表示的=短鍊就是 http://sourl.cn/cgSqq。
如何解決哈希沖突
雜湊演算法無法避免的一個問題，就是哈希沖突。盡管 MurmurHash 算法，沖突的機率非常低。但是，一旦沖突，就會導緻兩個原始網址被轉化成同一個短鍊。當使用者通路短鍊的時候，我們就無從判斷，使用者想要通路的是哪一個原始網址了。這個問題該如何解決呢？
一般情況下，我們會儲存短鍊跟原始網址之間的對應關系，以便後續使用者在通路短鍊的時候，可以根據對應關系，查找到原始網址。存儲這種對應關系的方式有很多，比如我們自己設計存儲系統或者利用現成的資料庫比如 MySQL、Redis。
以 MySQL 為例，當有一個新的原始網址需要生成短鍊的時候，我們先利用 MurmurHash 算法，生成短鍊。然後将這個新生成的短鍊，在 MySQL 資料庫中查找：
- 如果沒有找到相同的短鍊，這就表明這個新生成的短鍊沒有沖突。于是我們就将這個短鍊傳回給使用者，然後将這個短鍊與原始網址之間的對應關系，存儲到 MySQL 資料庫中
- 如果在資料庫中找到了相同的短鍊，那也并不一定說明就沖突了。我們先從資料庫中将這個短鍊對應的原始網址取出來：
- 如果資料庫中的原始網址，跟我們現在正在處理的原始網址是一樣的，這就說明已經有人請求過這個原始網址的短鍊了。我們就可以拿這個短鍊直接用。
- 如果資料庫中記錄的原始網址，跟我們正在處理的原始網址不一樣，那就說明雜湊演算法發生了沖突。不同的原始網址，經過計算，得到的短鍊重複了。這個時候，我們可以給原始網址拼接一串特殊字元，比如 DUPLICATED，然後再重新計算哈希值，兩次哈希計算都沖突的機率，顯然是非常低的。假設出現非常極端的情況，又發生沖突了，我們可以再換一個拼接字元串，比如 OHMYGOD，再計算哈希值。然後把計算得到的哈希值，跟原始網址拼接了特殊字元串之後的文本，一并存儲在 MySQL 資料庫中。當使用者通路短鍊的時候，短鍊服務先通過短鍊，在資料庫中查找到對應的原始網址。如果原始網址有拼接特殊字元（這個很容易通過字元串比對算法找到），就先将特殊字元去掉，然後再将不包含特殊字元的原始網址傳回給浏覽器。
如何優化性能
在短鍊生成的過程中，伺服器會執行兩條 SQL 語句：
- 第一個 SQL 語句是通過短鍊查詢短鍊與原始網址的對應關系
- 第二個 SQL 語句是将新生成的短鍊和原始網址之間的對應關系存儲到資料庫
很顯然，第二步是無法避免的，而第一步可以通過給短鍊字段建立唯一索引來優化
這樣，當有新的原始網址需要生成短鍊的時候，并不會拿生成的短鍊在資料庫中查找判重，而是直接将生成的短鍊與對應的原始網址嘗試存儲到資料庫中。如果資料庫能夠将資料正常寫入，那說明并沒有違反唯一索引，也就是說，這個新生成的短鍊并沒有沖突。
當然，如果資料庫回報違反唯一性索引異常，那我們還得重新執行上述的“查詢、寫入”過程，SQL 語句執行的次數不減反增。但是，MurmurHash 的沖突機率還是比較低的，是以，從整體上看，總的 SQL 語句執行次數會大大減少。
那如果資料量非常大，沖突機率大幅上升，這種情況下該怎麼辦？
可以使用布隆過濾器。
把已經生成的短鍊，建構成布隆過濾器。當有新的短鍊生成的時候，我們先拿這個新生成的短鍊，在布隆過濾器中查找。如果查找的結果是不存在，那就說明這個新生成的短鍊并沒有沖突。這個時候，我們隻需要再執行寫入短鍊和對應原始網頁的 SQL 語句就可以了。
方法二：ID 生成器
我們可以維護一個 ID 自增生成器。它可以生成 1、2、3…這樣自增的整數 ID。當短鍊服務接收到一個原始網址轉化成短鍊的請求之後，它先從 ID 生成器中取一個号碼，然後将其轉化成 62 進制表示法，拼接到短鍊服務的域名（比如http://sourl.cn/）後面，就形成了最終的短鍊。最後，我們還是會把生成的短鍊和對應的原始網址存儲到資料庫中。
理論非常簡單好了解。不過，這裡有幾個細節問題需要處理。
相同的原始網址可能會對應不同的短鍊
每次新來一個原始網址，我們就生成一個新的短鍊，這種做法就會導緻兩個相同的原始網址生成了不同的短鍊。這個該如何處理呢？實際上，我們有兩種處理思路。
- 第一種處理思路是不做處理。聽起來有點匪夷所依，但實際上，相同的原始網址對應不同的短鍊，這個使用者是完全可以接受的。在大部分短鍊的應用場景裡，使用者隻關心短鍊能否正确地跳轉到原始網址。至于短鍊長什麼樣子，他其實根本就不關心。
- 第二種處理思路是拿原始網址在資料庫中查找，看資料庫中是否已經存在相同的原始網址了。如果資料庫中存在，那我們就取出對應的短鍊，直接傳回給使用者。不過，這種處理思路有個問題，我們需要給資料庫中的短鍊和原始網址這兩個字段，都添加索引。短鍊上加索引是為了提高使用者查詢短鍊對應的原始網頁的速度，原始網址上加索引是為了加快剛剛講的通過原始網址查詢短鍊的速度。這種解決思路雖然能滿足 “相同原始網址對應相同短鍊” 這樣一個需求，但是是有代價的：一方面兩個索引會占用更多的存儲空間，另一方面索引還會導緻插入、删除等操作性能的下降。
如何實作高性能的 ID 生成器
實作 ID 生成器的方法有很多，比如利用資料庫自增。當然我們也可以自己維護一個計數器，不停地加一加一。但是，一個計數器來應對頻繁的短鍊生成請求，顯然是有點吃力的（因為計數器必須保證生成的 ID 不重複，籠統概念上講，就是需要加鎖）。如何提高 ID 生成器的性能呢？關于這個問題，實際上，有很多解決思路。我這裡給出兩種思路。
第一種思路是給 ID 生成器裝多個前置發号器。我們批量地給每個前置發号器發送 ID 号碼段（這一段的 ID 歸屬于這個發号器，不用擔心ID 重複）。當我們接受到短鍊生成請求的時候，隻需要選擇一個前置發号器來取号碼就行了。這樣通過多個前置發号器，明顯提高了并發發号的能力。
可能不是很好了解，這裡類比下 “無鎖的并發生産者 - 消費者模型”：
對于生産者來說，它往隊列中添加資料之前，先申請可用空閑存儲單元，并且是批量地申請連續的 n 個（n≥1）存儲單元。當申請到這組連續的存儲單元之後，後續往隊列中添加元素，就可以不用加鎖了，因為這組存儲單元是這個線程獨享的。不過，申請存儲單元的過程還是需要加鎖的。
對于消費者來說，處理的過程跟生産者是類似的。它先去申請一批連續可讀的存儲單元（這個申請的過程也是需要加鎖的），當申請到這批存儲單元之後，後續的讀取操作就可以不用加鎖了。
第二種思路跟第一種差不多。不過，我們不再使用一個 ID 生成器和多個前置發号器這樣的架構，而是直接實作多個 ID 生成器同時服務。每個 ID 生成器按照不同的規則來生成 ID 号碼，進而保證每個 ID 生成器生成的 ID 不重複。比如，第一個 ID 生成器隻能生成尾号為 0 的，第二個隻能生成尾号為 1 的，以此類推。這樣通過多個 ID 生成器同時工作，也提高了 ID 生成的效率。
來源：https://mp.weixin.qq.com/s?__biz=MzI0NDc3ODE5OQ==&mid