雖然我們不希望發(fā)生沖突，但實(shí)際上發(fā)生沖突的可能性仍是存在的。當(dāng)關(guān)鍵字值域遠(yuǎn)大于哈希表的長度，而且事先并不知道關(guān)鍵字的具體取值時。沖突就難免會發(fā) 生。另外，當(dāng)關(guān)鍵字的實(shí)際取值大于哈希表的長度時，而且表中已裝滿了記錄，如果插入一個新記錄，不僅發(fā)生沖突，而且還會發(fā)生溢出。因此，處理沖突和溢出是 哈希技術(shù)中的兩個重要問題。
1、開放定址法
    　用開放定址法解決沖突的做法是：當(dāng)沖突發(fā)生時，使用某種探查(亦稱探測)技術(shù)在散列表中形成一個探查(測)序列。沿此序列逐個單元地查找，直到找到給定 的關(guān)鍵字，或者碰到一個開放的地址(即該地址單元為空)為止（若要插入，在探查到開放的地址，則可將待插入的新結(jié)點(diǎn)存人該地址單元）。查找時探查到開放的 地址則表明表中無待查的關(guān)鍵字，即查找失敗。
注意：
①用開放定址法建立散列表時，建表前須將表中所有單元(更嚴(yán)格地說，是指單元中存儲的關(guān)鍵字)置空。
②空單元的表示與具體的應(yīng)用相關(guān)。
    　按照形成探查序列的方法不同，可將開放定址法區(qū)分為線性探查法、線性補(bǔ)償探測法、隨機(jī)探測等。
（1）線性探查法(Linear Probing)
該方法的基本思想是：
    將散列表T[0..m-1]看成是一個循環(huán)向量，若初始探查的地址為d(即h(key)=d)，則最長的探查序列為：
        d，d+l，d+2，…，m-1，0，1，…，d-1
    　即:探查時從地址d開始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循環(huán)到T[0]，T[1]，…，直到探查到T[d-1]為止。
探查過程終止于三種情況：
    　(1)若當(dāng)前探查的單元為空，則表示查找失敗（若是插入則將key寫入其中）；
    (2)若當(dāng)前探查的單元中含有key，則查找成功，但對于插入意味著失敗；
    　(3)若探查到T[d-1]時仍未發(fā)現(xiàn)空單元也未找到key，則無論是查找還是插入均意味著失敗(此時表滿)。
利用開放地址法的一般形式，線性探查法的探查序列為：
        h_i=(h(key)+i)％m 0≤i≤m-1 //即d_i=i
用線性探測法處理沖突，思路清晰，算法簡單，但存在下列缺點(diǎn)：
① 處理溢出需另編程序。一般可另外設(shè)立一個溢出表，專門用來存放上述哈希表中放不下的記錄。此溢出表最簡單的結(jié)構(gòu)是順序表，查找方法可用順序查找。
② 按上述算法建立起來的哈希表，刪除工作非常困難。假如要從哈希表 HT 中刪除一個記錄，按理應(yīng)將這個記錄所在位置置為空，但我們不能這樣做，而只能標(biāo)上已被刪除的標(biāo)記，否則，將會影響以后的查找。
③ 線性探測法很容易產(chǎn)生堆聚現(xiàn)象。所謂堆聚現(xiàn)象，就是存入哈希表的記錄在表中連成一片。按照線性探測法處理沖突，如果生成哈希地址的連續(xù)序列愈長 ( 即不同關(guān)鍵字值的哈希地址相鄰在一起愈長 ) ，則當(dāng)新的記錄加入該表時，與這個序列發(fā)生沖突的可能性愈大。因此，哈希地址的較長連續(xù)序列比較短連續(xù)序列生長得快，這就意味著，一旦出現(xiàn)堆聚 ( 伴隨著沖突 ) ，就將引起進(jìn)一步的堆聚。
（2）線性補(bǔ)償探測法
線性補(bǔ)償探測法的基本思想是：
將線性探測的步長從 1 改為 Q ，即將上述算法中的 j ＝ (j ＋ 1) % m 改為： j ＝ (j ＋ Q) % m ，而且要求 Q 與 m 是互質(zhì)的，以便能探測到哈希表中的所有單元。
【例】 PDP-11 小型計(jì)算機(jī)中的匯編程序所用的符合表，就采用此方法來解決沖突，所用表長 m ＝ 1321 ，選用 Q ＝ 25 。

（3）隨機(jī)探測
隨機(jī)探測的基本思想是：
將線性探測的步長從常數(shù)改為隨機(jī)數(shù)，即令： j ＝ (j ＋ RN) % m ，其中 RN 是一個隨機(jī)數(shù)。在實(shí)際程序中應(yīng)預(yù)先用隨機(jī)數(shù)發(fā)生器產(chǎn)生一個隨機(jī)序列，將此序列作為依次探測的步長。這樣就能使不同的關(guān)鍵字具有不同的探測次序，從而可以避 免或減少堆聚。基于與線性探測法相同的理由，在線性補(bǔ)償探測法和隨機(jī)探測法中，刪除一個記錄后也要打上刪除標(biāo)記。

2、拉鏈法
（1）拉鏈法解決沖突的方法
    　拉鏈法解決沖突的做法是：將所有關(guān)鍵字為同義詞的結(jié)點(diǎn)鏈接在同一個單鏈表中。若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針組成的指針數(shù) 組T[0..m-1]。凡是散列地址為i的結(jié)點(diǎn)，均插入到以T[i]為頭指針的單鏈表中。T中各分量的初值均應(yīng)為空指針。在拉鏈法中，裝填因子α可以大于 1，但一般均取α≤1。
【例】設(shè)有 m ＝ 5 ， H(K) ＝ K mod 5 ，關(guān)鍵字值序例 5 ， 21 ， 17 ， 9 ， 15 ， 36 ， 41 ， 24 ，按外鏈地址法所建立的哈希表如下圖所示：
          
（2）拉鏈法的優(yōu)點(diǎn)
與開放定址法相比，拉鏈法有如下幾個優(yōu)點(diǎn)：
①拉鏈法處理沖突簡單，且無堆積現(xiàn)象，即非同義詞決不會發(fā)生沖突，因此平均查找長度較短；
②由于拉鏈法中各鏈表上的結(jié)點(diǎn)空間是動態(tài)申請的，故它更適合于造表前無法確定表長的情況；
③開放定址法為減少沖突，要求裝填因子α較小，故當(dāng)結(jié)點(diǎn)規(guī)模較大時會浪費(fèi)很多空間。而拉鏈法中可取α≥1，且結(jié)點(diǎn)較大時，拉鏈法中增加的指針域可忽略不計(jì)，因此節(jié)省空間；
④在用拉鏈法構(gòu)造的散列表中，刪除結(jié)點(diǎn)的操作易于實(shí)現(xiàn)。只要簡單地刪去鏈表上相應(yīng)的結(jié)點(diǎn)即可。而對開放地址法構(gòu)造的散列表，刪除結(jié)點(diǎn)不能簡單地將被刪結(jié) 點(diǎn)的空間置為空，否則將截?cái)嘣谒筇钊松⒘斜淼耐x詞結(jié)點(diǎn)的查找路徑。這是因?yàn)楦鞣N開放地址法中，空地址單元(即開放地址)都是查找失敗的條件。因此在 用開放地址法處理沖突的散列表上執(zhí)行刪除操作，只能在被刪結(jié)點(diǎn)上做刪除標(biāo)記，而不能真正刪除結(jié)點(diǎn)。

（3）拉鏈法的缺點(diǎn)
    　拉鏈法的缺點(diǎn)是：指針需要額外的空間，故當(dāng)結(jié)點(diǎn)規(guī)模較小時，開放定址法較為節(jié)省空間，而若將節(jié)省的指針空間用來擴(kuò)大散列表的規(guī)模，可使裝填因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度。