獨一、不重複的網址, MD5 與短網址

日前看到網路上一則網友提問,提到他想要儲存不重複的網址,問有什麼比較好的作法。接著,他所構想的方案立刻跳躍到 MD5 取分配對應值,因此立刻聯想到 MD5 演算法的碰撞問題。而其他網友回答問題,又跳躍到短網址,而且立刻聯想到 Google 的短網址服務是否足夠穩當。

由上述可見,未經過思考之下,所編列的問題,足以媲美「要你命三千」,各個都是殺傷工具,卻彼此沒有必然的關聯。邏輯理論有一種謬誤,稱為「滑坡謬誤」,說將誇大的因果效應串連起來推論,而造成不合理的結論。

以 MD5 編碼來說,遭遇碰撞的機會少之又少,但新手卻往往為了迴避碰撞,而在過度的設計中,發揮了太多智慧。

其實問題應該要各個擊破。以下分別談這三件事:儲存不重複的網址、 MD5 的碰撞、短網址。

儲存不重複的網址

儲存不重複的網址,要嘛就是使用以下 SQL 建立表格,並且在填表之前先檢查 value 是否重複:

create table URL ( id int identity(1,1) primary key, value varchar(2048) );

要嘛則是改為讓 value 欄位可以自行排除重複,且對每一個網址都有獨一代號:

create table URL ( id int identity(1,1), value varchar(2048) unique );

反正,只要讓網址可以儲存好,並且可以由 URL.id 取得該網址,即可。

MD5 的碰撞

在此情境,使用 MD5 是為了給每一個網址獲得一個可以用的代碼,對用戶來說,這個代碼是不是隨機的或者是不是保密的,都比較不重要。在編碼的意義上, MD5 代碼與任何一個網址之間所對應的關係,是比較重要的:我們不能接受由原本的那個 MD5 代碼,卻找到另一個網址。因此,在背景所發生的 MD5 碰撞,也就是二個不同的網址,經過 MD5 編碼之後,獲得相同一組代碼,這種情況是不容許的。

接續前一段對於網址儲存的設計,使用 md5(URL.id) 即可代表由 URL.id 所對應的網址。我們可以有一個 MD5_URL 表,讓已編碼的資料放進 value 欄位。 url_id 欄位參考 URL.id 。

create table MD5_URL ( value char(32) primary key, url_id int );

那麼,如果 md5(URL.id) 遭遇碰撞了呢?那麼就改用 md5(URL.value) 做出另一組編碼,當作備胎。

雖然並沒有認真處理 MD5 的碰撞,但是做為一時可用的迴避辦法,是可行的。

短網址

短網址跟 MD5 很不一樣的是,短網址就是要短。在演算法的運用上,我們不能隨便將 MD5 編碼取出局部文字來代表短網址,因為你可能不知道遭遇碰撞的機會有多高。

在精神上,短網址對應到原網址,與由 MD5 代碼對應到原網址,以及與 URL.id 對應到原網址,三件事是相互等價的。因此,其實從最早我們做出由 URL.id 對應到 URL.value 的時候,已經建立了短網址製作的基礎。

短網址是另一種數字進位系統。

如果我們使用六位文字來表示短網址,每一位文字為 a-z 或 A-Z 英文字,一個位置可以表達 52 種符號,因此,是在六位數之內,表達 52 進位的整數。因此,我們都知道怎麼做短網址了,首先設定足夠的位數,而假如將來遇到位數用完了,就增加位數。

十進位數字系統,不管目前是在多少位數之內,數字 1 都表示為 “1″ ,三位數之內表示 1 與二位數之內表示 1 ,結果相同。而短網址對於同樣一個數字 1 ,三位數的短網址表示為 “aaa" 而四位數的短網址表示為 “aaaa",二者彼此不同。

***

以上是我對於電腦系統在網址儲存、 MD5 對應、以及短網址對應等三件事情的一些淺見。

廣告

About 黃耀賢 (Yau-Hsien Huang)

熱愛 Erlang ,並且有相關工作經驗。喜歡程式語言。喜歡邏輯。目前用 Python 工作。
本篇發表於 Programming, Uncategorized。將永久鏈結加入書籤。