處理沖突的方法
通常有兩類方法處理沖突開放定址(Open Addressing)法和拉鏈(Chaining)法前者是將所有結點均存放在散列表T[m
]中;後者通常是將互為同義詞的結點鏈成一個單鏈表而將此鏈表的頭指針放在散列表T[m]中
開放定址法
()開放地址法解決沖突的方法
用開放定址法解決沖突的做法是當沖突發生時使用某種探查(亦稱探測)技術在散列表中形成一個探查(測)序列沿此序列逐
個單元地查找直到找到給定的關鍵字或者碰到一個開放的地址(即該地址單元為空)為止(若要插入在探查到開放的地址則可
將待插入的新結點存人該地址單元)查找時探查到開放的地址則表明表中無待查的關鍵字即查找失敗
注意
①用開放定址法建立散列表時建表前須將表中所有單元(更嚴格地說是指單元中存儲的關鍵字)置空
②空單元的表示與具體的應用相關
【例】關鍵字均為非負數時可用來表示空單元而關鍵字為字符串時空單元應是空串
總之應該用一個不會出現的關鍵字來表示空單元
()開放地址法的一般形式
開放定址法的一般形式為 h i =(h(key)+d i )%m ≤i≤m
其中
①h(key)為散列函數d i 為增量序列m為表長
②h(key)是初始的探查位置後續的探查位置依次是h l h …h m 即h(key)h l h …h m 形成了一
個探查序列
③若令開放地址一般形式的i從開始並令d =則h =h(key)則有
h i =(h(key)+d i )%m ≤i≤m
探查序列可簡記為h i (≤i≤m)
()開放地址法堆裝填因子的要求
開放定址法要求散列表的裝填因子α≤l實用中取α為到之間的某個值為宜
()形成探測序列的方法
按照形成探查序列的方法不同可將開放定址法區分為線性探查法二次探查法雙重散列法等
①線性探查法(Linear Probing)
該方法的基本思想是
將散列表T[m]看成是一個循環向量若初始探查的地址為d(即h(key)=d)則最長的探查序列為
dd+ld+…m…d
即:探查時從地址d開始首先探查T[d]然後依次探查T[d+]…直到T[m]此後又循環到T[]T[]…直到探查到
T[d]為止
探查過程終止於三種情況
()若當前探查的單元為空則表示查找失敗(若是插入則將key寫入其中);
()若當前探查的單元中含有key則查找成功但對於插入意味著失敗;
()若探查到T[d]時仍未發現空單元也未找到key則無論是查找還是插入均意味著失敗(此時表滿)
利用開放地址法的一般形式線性探查法的探查序列為
h i =(h(key)+i)%m ≤i≤m //即d i =i
From:http://tw.wingwit.com/Article/program/sjjg/201311/23680.html
