碰撞 (電腦科學)

在電腦科學中，碰撞或衝突是指兩個不同的元素具有相同的雜湊值、校驗和，數字指紋時發生的情況。當數據量足夠多（例如將所有可能的人名和電腦檔名對映到一段字元上）時，碰撞是不可避免的。這僅僅是鴿巢原理的一個實例。

雜湊碰撞是指兩個不同的輸入值經過雜湊函數處理後得到相同的輸出值。 這種情況在雜湊表數據結構中尤為重要，因為它可能影響尋找和儲存的效率。

雜湊碰撞的發生是不可避免的，主要原因如下：

1. 輸入空間通常大於輸出空間：雜湊函數將任意長度的輸入對映到固定長度的輸出，必然會有多個輸入對應同一個輸出.
2. 生日悖論：根據概率論，即使在相對較小的樣本空間中，也有較高的概率出現重複.

處理雜湊碰撞的主要方法有兩種：

1. 開放定址法：當發生碰撞時，繼續探測雜湊表的下一個位置，直到找到空槽.
2. 連結法：在每個雜湊表槽位使用鏈結串列儲存發生碰撞的元素

一個優秀的雜湊函數應該滿足以下條件：

1. 單向性：難以從雜湊值反推原始輸入。
2. 弱無碰撞性：給定一個輸入，難以找到另一個輸入產生相同的雜湊值。
3. 強無碰撞性：難以找到任意兩個不同輸入產生相同的雜湊值.

在實際應用中，雜湊碰撞可能被惡意利用。例如，攻擊者可能通過製造大量碰撞來增加伺服器查詢雜湊表的時間，從而導致效能下降或服務癱瘓.為了減少雜湊碰撞的影響，可以採取以下措施：

1. 選擇高質素的雜湊函數。
2. 使用足夠大的雜湊表以減少碰撞概率。
3. 實現有效的碰撞解決策略，如連結法或開放定址法。
4. 在必要時動態調整雜湊表大小。

總之，雖然雜湊碰撞無法完全避免，但通過合理的設計和實現，可以最大限度地減少其對系統效能的影響。

碰撞的影響依程式而異。當雜湊函數和數字指紋用於標識相似數據時，程式被設計成儘可能增加相似但不同的數據發生碰撞的可能性；校驗和則不同，要求儘可能使得相似的數據輸出不同，而不考慮不同數據輸出相同的情況。

參見

• 生日攻擊

外部連結

• http://permabit.wordpress.com/2008/07/18/what-do-hash-collisions-really-mean/ （頁面存檔備份，存於互聯網檔案館）