哈希碰撞

如果兩個輸入串的哈希函數的值一樣，則稱這兩個串是一個碰撞。既然是把任意長度的字符串變成固定長度的字符串，所以必有一個輸出串對應無窮多個輸入串，碰撞是必然存在的。

一個優良的哈希函數 f 應當滿足以下三個條件：

（1）對於任意y，尋找x，使得f(x)=y，在計算上是不可行的。

（2）給定x1∈A,找x2∈B，，使得f(x1)=f(x2)，在計算上是不可能的，這也就是弱無碰撞性。

（3）尋找x1，x2，使得f(x1)=f(x2)，在計算上也是不可行的，這也就是強無碰撞性。

這樣就稱為安全保密的哈希函數，除了枚舉外不可能有別的更快的方法。如第3條，根據生日定理，要想找到這樣的x1，x2，理論上需要大約2^(n/2)的枚舉次數。

因為前兩條都能被破壞的哈希函數太弱而被拋棄，幾乎所有的哈希函數的破解，都是指的破壞上面的第3條性質，即找到一個碰撞。在密碼學上還有一個概念是理論破解，指的是提出一個算法，使得可以用低於理論值得枚舉次數找到碰撞。

通常有兩類方法處理碰撞：開放尋址(Open Addressing)法和鏈接(Chaining)法。前者是將所有結點均存放在散列表T[0..m-1]中；後者通常是把散列到同一槽中的所有元素放在一個鏈表中，而將此鏈表的頭指針放在散列表T[0..m-1]中。

(1)開放尋址法

所有的元素都在散列表中，每一個表項或包含動態集合的一個元素，或包含NIL。這種方法中散列表可能被填滿，以致於不能插入任何新的元素。在開放尋址法中，當要插入一個元素時，可以連續地檢查或探測散列表的各項，直到有一個空槽來放置待插入的關鍵字為止。有三種技術用於開放尋址法：線性探測、二次探測以及雙重探測。

（2）線性探測

給定一個普通的散列函數h'：U —>{0，1，.....，m-1}，線性探測方法採用的散列函數為：h(k,i) = (h'(k)+i)mod m，i=0,1,....,m-1　　

探測時從i=0開始，首先探查T[h'(k)]，然後依次探測T[h'(k)+1]，…，直到T[h'(k)+m-1]，此後又循環到T[0]，T[1]，…，直到探測到T[h'(k)-1]為止。探測過程終止於三種情況：

(1)若當前探測的單元為空，則表示查找失敗（若是插入則將key寫入其中）；

(2)若當前探測的單元中含有key，則查找成功，但對於插入意味着失敗；

(3)若探測到T[h'(k)-1]時仍未發現空單元也未找到key，則無論是查找還是插入均意味着失敗(此時表滿)。

線性探測方法較容易實現，但是存在一次羣集問題，即連續被佔用的槽的序列變的越來越長。採用例子進行説明線性探測過程，已知一組關鍵字為(26，36，41，38，44，15，68，12，6，51)，用除餘法構造散列函數，初始情況如下圖所示：

散列過程如下圖所示：

（3）二次探測

二次探測法的探查序列是：h(k,i) =(h'(k)+i*i)％m ,0≤i≤m-1 。初次的探測位置為T[h'(k)]，後序的探測位置在次基礎上加一個偏移量，該偏移量以二次的方式依賴於i。該方法的缺陷是不易探查到整個散列空間。

（4）雙重散列

該方法是開放尋址的最好方法之一，因為其產生的排列具有隨機選擇的排列的許多特性。採用的散列函數為：h(k,i)=(h1(k)+ih2(k)) mod m。其中h1和h2為輔助散列函數。初始探測位置為T[h1(k)]，後續的探測位置在此基礎上加上偏移量h2(k)模m。

（5）鏈接法

將所有關鍵字為同義詞的結點鏈接在同一個鏈表中。若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針組成的指針數組T[0..m-1]。凡是散列地址為i的結點，均插入到以T[i]為頭指針的單鏈表中。T中各分量的初值均應為空指針。在拉鍊法中，裝填因子α可以大於1，但一般均取α≤1。

舉例説明鏈接法的執行過程，設有一組關鍵字為(26，36，41，38，44，15，68，12，6，51)，用除餘法構造散列函數，初始情況如下圖所示：

最終結果如下圖所示：