數(shù)據(jù)結(jié)構(gòu)主講人：石云常州信息職業(yè)技術(shù)學(xué)院8.3哈希沖突解決方法由于任一種哈希函數(shù)也不能避免產(chǎn)生沖突，因此選擇好的解決沖突的方法十分重要。處理沖突的方法與哈希表本身的組織形式有關(guān)。按組織形式的不同，通常分兩大類：開放定址法和鏈地址法。引言IntroductionPart01開放定址法開放定址法哈希沖突解決方法開放定址法的基本思想是：當(dāng)沖突發(fā)生時,沿一序列逐個探查下一個空閑地址(開放的地址)，如果哈希表足夠大，肯定會找到空閑地址來存放發(fā)生沖突的元素。開放定址法的一般形式：

Hi=[H(key)+di]%n 1≤i≤n-1

其中：H(key)為哈希函數(shù)，di為增量序列，n為表長。根據(jù)di取值的不同，可分為線性探測法和二次探測法。開放定址法-線性探測法哈希沖突解決方法增量序列：di=1,2,3…,n-1該方法將散列表假想成一個循環(huán)表，發(fā)生沖突時，依次探查下一臨近地址，如果到最后一個地址也沒找到空閑位置，則回到表頭開始繼續(xù)查找，直到找到一個空位，就把此元素放入此空位中。如果找不到空位，則說明散列表已滿，需要進(jìn)行溢出處理。開放定址法-線性探測法示例5：關(guān)鍵字集合{19，14，23，01，68，20，84，27，55},哈希函數(shù)H(key)=keyMOD11,擬用線性探測法處理沖突，

則哈希表如下：①H(1)=1哈希地址沖突，H1=(H(1)+1)mod11=2,表中哈希地址2為空,將01存入。01234567891019分析14230101686820842755②H(68)=2,哈希地址沖突；H1=(H(2)+1)mod11=3,仍然沖突;H2=(H(3)+1)mod11=4,哈希地址4為空,將68存入。開放定址法-二次探測法哈希沖突解決方法探查下一空閑地址公式：Hi=[H(key)+di]%n 1≤i≤n-1其增量序列:di=12,-12,22,-22,32……,±k2

(k≤n/2)開放定址法-二次探測法示例6：有關(guān)鍵字集合{19，14，23，01，68，20，84，27，55},哈希函數(shù)H(key)=keyMOD11,擬用二次探測法處理沖突，

則哈希表如下：01234567891019分析1423010168682084275568關(guān)鍵碼的沖突處理如下：H(68)=2,哈希地址上沖突；H1=(H(2)+12)mod11=3,仍然沖突;H2=(H(2)-12)mod11=1,仍然沖突；H3=(H(2)+22)mod11=6,找到空的哈希地址,存入。Part02鏈表法鏈表法哈希沖突解決方法鏈表法解決哈希沖突的方法：把具有相同哈希地址的記錄放在同一個單鏈表中。若選定的哈希表長度為n，則定義一個數(shù)組Array[0...n-1]來存放單鏈表頭指針。數(shù)組Array[0...n-1]中各元素的初始值為null。哈希表構(gòu)造過程中，哈希地址為i的結(jié)點(diǎn)，均插入到以Array[i]為頭指針的單鏈表中。鏈表法示例7：有關(guān)鍵字集合{03，14，23，01，68，20，84，27，25},哈希函數(shù)H(key)=keyMOD11,使用鏈表法構(gòu)造的哈希表如下：0123456789102301