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