想用簡單的散列法來創建一個內部使用的縮短url服務。我打算使用的功能如下使用散列法編寫縮短url服務時，我們應該擔心衝突
string s = base64Convert(md5(salt: time in million seconds))
string url = s.substring(0, len: 6)
Map url to real url
會有64^6 = 68,719,476,736個可能的組合。對於我們的內部服務應該綽綽有餘。
但是有一件事讓我擔心，我怎麼才能確保在64^6 +1時間散列之前不會有重複的url？
有什麼想法？
我怎樣才能確保不會有重複的網址，直到64^6 +1時間哈希？
使用簡單散列法，您不能確保此屬性。
假設MD5的等分佈，如果你有ň的URL散列，並添加一個，然後有ň可能的結果會是如何碰撞和64 - ñ怎麼會有衝突。因此，該新元素碰撞的機會是n/64 。即使n = 1，此值也不爲零，因此第二個網址在理論上可能已經發生碰撞，即使實際發生的機會非常低。數據庫中的非衝突URL越多，新哈希將與任何現有哈希衝突的機會就越高，直到機會變爲100％爲止，直到== 64 。
如果你這樣想，請務必記住birthday 「paradox」。如果你有一組n你想添加的網址，那麼他們碰撞的任意兩個的機會是方式大於最後一個與你之前添加的任何一個碰撞的機會。如果你使用do the math，你會發現使用你的方案，你可以期望在它們中任何兩個之間發生碰撞的可能性超過1％之前，散列約37.000個URL。
因此，您現在必須決定是否有1％的碰撞概率是可以接受的，以及37.000個URL是否足以滿足您的需求。如果概率結果不滿足你，你可以通過例如調整機會來調整。使用6位以上的數字，否則您必須執行collision resolution。