hash : 翻譯為“散列”，就是把任意長度的輸入，通過散列算法，變成固定長度的輸出，該輸出就是散列值。

開放地址法

當(dāng)關(guān)鍵字key的哈希地址p=H（key）出現(xiàn)沖突時，以p為基礎(chǔ)，產(chǎn)生另一個哈希地址p1，如果p1仍然沖突，再以p為基礎(chǔ)，產(chǎn)生另一個哈希地址p2，…，直到找出一個不沖突的哈希地址pi ，將相應(yīng)元素存入其中。這種方法有一個通用的再散列函數(shù)形式：

其中

其中為哈希函數(shù)， 為表長，稱為增量序列。增量序列的取值方式不同，相應(yīng)的再散列方式也不同。主要有以下三種：

• 線性探測法：沖突發(fā)生時，順序查看表中下一單元，直到找出一個空單元或查遍全表
  
• 二次探測法：沖突發(fā)生時，在表的左右進(jìn)行跳躍式探測，比較靈活。
  
• 偽隨機(jī)探測：應(yīng)建立一個偽隨機(jī)數(shù)發(fā)生器，（如，并給定一個隨機(jī)數(shù)做起點(diǎn)。
  

對于利用開放地址法處理沖突所產(chǎn)生的哈希表中刪除一個元素時需要謹(jǐn)慎，不能直接地刪除，因?yàn)檫@樣將會截斷其他具有相同哈希地址的元素的查找地址，所以，通常采用設(shè)定一個特殊的標(biāo)志以示該元素已被刪除。

再哈希法

這種方法是同時構(gòu)造多個不同的哈希函數(shù)：

當(dāng)哈希地址發(fā)生沖突時，再計(jì)算……，直到?jīng)_突不再產(chǎn)生。這種方法不易產(chǎn)生聚集，但增加了計(jì)算時間。

鏈地址法(拉鏈法)

為每個 Hash 值建立一個單鏈表，當(dāng)發(fā)生沖突時，將記錄插入到鏈表中

建立公共溢出區(qū)

將哈希表分為基本表和溢出表兩部分，凡是和基本表發(fā)生沖突的元素，一律填入溢出表

拉鏈法的優(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)的空間置為空，否則將截斷在它之后填人散列表的同義詞結(jié)點(diǎn)的查找路徑。這是因?yàn)楦鞣N開放地址法中，空地址單元(即開放地址)都是查找失敗的條件。因此在 用開放地址法處理沖突的散列表上執(zhí)行刪除操作，只能在被刪結(jié)點(diǎn)上做刪除標(biāo)記，而不能真正刪除結(jié)點(diǎn)。

缺點(diǎn)：

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