《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述）（第2版）》教學(xué)課件7-10哈希函數(shù)沖突解決方法2

1、2016數(shù)據(jù)結(jié)構(gòu)Data structure講授：賀寧哈希函數(shù)沖突解決方法-2常州信息職業(yè)技術(shù)學(xué)院0203解決哈希沖突的方法 在使用哈希函數(shù)構(gòu)造哈希表時(shí)，一旦發(fā)生沖突，應(yīng)有較好的解決沖突的方法。解決沖突的方法有很多，這里只介紹開(kāi)放定址法和拉鏈法，前者是將所有結(jié)點(diǎn)均存放在哈希表T0n-1中；后者通常是將互為同義詞的結(jié)點(diǎn)鏈成一個(gè)單鏈表，而將此鏈表的頭指針?lè)旁诠１鞹0n-1中。1、開(kāi)放定址法 線(xiàn)性探查法 二次（平方）探查法 線(xiàn)性補(bǔ)償探查法2、拉鏈法04線(xiàn)性補(bǔ)償探查法 將線(xiàn)性探查的步長(zhǎng)從1改為Q，即若初始探查的地址為d（H(key)=d），則探查序列為：d,d+Q,d+2Q,d+3Q,，而且要求Q與

2、n是互質(zhì)的, 以便能探測(cè)到哈希表中的所有單元。05線(xiàn)性補(bǔ)償探查法 設(shè)關(guān)鍵字集合為47,7,29,11,16,95,22,8,3，哈希表表長(zhǎng)為11，哈希函數(shù)為H(key)=key mod 11，Q=3。采用線(xiàn)性補(bǔ)償探查法構(gòu)造哈希表及在哈希表中查找過(guò)程如下： 構(gòu)造哈希表：依次按哈希函數(shù)將關(guān)鍵字記錄放入哈希表，其中關(guān)鍵字29需按線(xiàn)性補(bǔ)償探查法，探查兩次得到地址為10的空單元，將29放入，同樣關(guān)鍵字95、22、3均需探查三次找到地址為2、6和9的空單元將其放入。按線(xiàn)性補(bǔ)償探查法構(gòu)造的哈希表如下圖所示。圖示 線(xiàn)性補(bǔ)償探查法構(gòu)造的哈希表06拉鏈法采用順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)相結(jié)合的存儲(chǔ)結(jié)構(gòu)，由多個(gè)單鏈表構(gòu)成，每

3、個(gè)單鏈表的頭指針存放在數(shù)組中。將所有關(guān)鍵字為同義詞的結(jié)點(diǎn)鏈接在同一個(gè)單鏈表中。若選定的散列表長(zhǎng)度為n，則散列表是一個(gè)由n個(gè)頭指針組成的數(shù)組T0n-1。凡是散列地址為i的結(jié)點(diǎn)，均插入到以Ti為頭指針的單鏈表中，T中各分量的初值均應(yīng)為空指針。07拉鏈法設(shè)關(guān)鍵字集合為47,18,29,11,16,95,22,8,3，哈希表表長(zhǎng)為11，哈希函數(shù)為H(key)=key mod 11。采用拉鏈法構(gòu)造哈希表及在哈希表中查找過(guò)程如下：構(gòu)造哈希表：將數(shù)組的每個(gè)元素值為空指針，依次按哈希函數(shù)將關(guān)鍵字記錄生成的結(jié)點(diǎn)鏈到頭指針指向的單鏈表中，其中關(guān)鍵字11、22鏈到下標(biāo)為0的頭指針指向的單鏈表，47、3鏈到下標(biāo)為3的頭指針指向的單鏈表，16鏈到下標(biāo)為5的頭指針指向的單鏈表，18、29、95鏈到下標(biāo)為7的頭指針指向的單鏈表，8鏈