標籤: 資訊學習

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

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

還沒想通資料量和 hash 有何關係？那就來看看新增時到底要作哪些事情：

1. 查詢資料是否已經存在
2. 產生網址與 key 的對應
3. 儲存結果

問題很明顯出在第一步驟，一千萬筆資料 query 一次到底要花多久的時間？有作索引也要花超過十秒，沒作索引花個半小時可能也算快。

如果將步驟改成這樣：

1. 將網址作 Hash
2. 使用 Hash 的結果查詢資料是否存在
3. 檢查是否發生碰撞
4. 儲存結果

在第一步先產生 hash 結果就可以減少搜尋的範圍，範圍縮小就可以減少第二步驟查詢所需要的時間。

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