2009/08/09

縮短網址 vs. Hash

一直到剛剛才想通為什麼大多數的縮短網址會使用 Hash 產生 key,果然不先死過一次不知道為什麼要這樣作。

先從 key 開始起吧,為了讓 key 更短通常會使用更多的文字或符號,從數字、英文大小寫甚至特殊符號。假設使用數字和英文大小寫作組合,每一位數都有 62 種組合 (10 + 26 + 26),用四個位數的話可以儲存約一千五百萬比資料,這對我這種小網站應該很夠用了。

還沒想通資料量和 hash 有何關係?那就來看看新增時到底要作哪些事情:
  1. 查詢資料是否已經存在
  2. 產生網址與 key 的對應
  3. 儲存結果
問題很明顯出在第一步驟,一千萬筆資料 query 一次到底要花多久的時間?有作索引也要花超過十秒,沒作索引花個半小時可能也算快。

如果將步驟改成這樣:
  1. 將網址作 Hash
  2. 使用 Hash 的結果查詢資料是否存在
  3. 檢查是否發生碰撞
  4. 儲存結果
在第一步先產生 hash 結果就可以減少搜尋的範圍,範圍縮小就可以減少第二步驟查詢所需要的時間。

現在開始後悔沒有好好學演算法了,我要怎麼自己寫一個 hash 函式出來啊???

3 則留言:

  1. 用別人的比較快吧?我記得以前上離散的時候課本就丟了一個問題「Is one-way function exist?」我記得這個命題都還沒證明,真的要研究的話就是那些數學密碼學crap,直接用別人作好的比較快。

    回覆刪除
  2. 就是買了一個網域想要自己玩咩,目前 mod_rewrite 應該沒甚麼問題,卡在 hash 不知道怎麼作,在找機會問問數學系的好了....

    感激你回覆的這麼勤 XD

    回覆刪除
  3. mod_rewrite 作不出來.... = ="

    「RewriteRule ^(.*)$ index.php?s=%0 [L]」有錯

    回覆刪除