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

1、2016數(shù)據(jù)結(jié)構(gòu)Data structure講授：賀寧哈希函數(shù)沖突解決方法-1常州信息職業(yè)技術(shù)學(xué)院0203解決哈希沖突的方法 在使用哈希函數(shù)構(gòu)造哈希表時，一旦發(fā)生沖突，應(yīng)有較好的解決沖突的方法。解決沖突的方法有很多，這里只介紹開放定址法和拉鏈法，前者是將所有結(jié)點均存放在哈希表T0n-1中；后者通常是將互為同義詞的結(jié)點鏈成一個單鏈表，而將此鏈表的頭指針放在哈希表T0n-1中。1、開放定址法 線性探查法 二次（平方）探查法 線性補償探查法2、拉鏈法04開放定址法一般形式 由關(guān)鍵字key得到的哈希地址H(key)一旦產(chǎn)生了沖突，即該地址已經(jīng)存放了數(shù)據(jù)元素，就去尋找下一個空的哈希地址，只要哈希表足夠大

2、，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。H(Key) 開放定址法的一般形式 Hi=(H(key)+di)%n（1in-1） 其中：H(key)為沖突的哈希地址，di為增量序列，n為表長。 即按照將已發(fā)生沖突的哈希地址加上一個增量的方法尋找下一個空的哈希地址，依據(jù)增量序列不同的選取方法得到不同的解決沖突的方法。05線性探查法 將哈希表T0n-1看成是一個循環(huán)向量，若初始探查的地址為d（即H(key)=d），則最長的探查序列為：d,d+1,d+2,n-1,0,1,d-1。即探查時從地址d開始，首先探查Td，然后依次探查Td+1 直到Tn-1，此后又循環(huán)到T0直到Td-1為止。 探查過程終止于三種

3、情況： 若當前探查的單元為空，對于構(gòu)造哈希表則將key寫入其中，對于查找則表示查找失??； 若當前探查的單元中含有key，對于構(gòu)造表則表示該記錄已存入哈希表，對于查找則查找成功； 若探查到Td-1時仍未發(fā)現(xiàn)空單元也未找到key，對于構(gòu)造表則此時表滿，對于查找表示查找失敗。06線性探查法 設(shè)關(guān)鍵字集合為47,18,29,11,16,95,22,8,3，哈希表表長為11，哈希函數(shù)為H(key)=key mod 11。采用線性探查法構(gòu)造哈希表及在哈希表中查找過程如下： 構(gòu)造哈希表：依次按哈希函數(shù)將關(guān)鍵字記錄放入哈希表，47的地址為3，18的地址為7，29的地址也為7，與關(guān)鍵字18發(fā)生沖突，按線性探查法

4、，探查地址為8（8=7+1）的單元，由于地址為8的單元為空，所以將29放入，同樣關(guān)鍵字95、8均需線性探查三次找到地址為9和10的空單元將其放入，關(guān)鍵字3需線性探查兩次找到地址為4的空單元將其放入。按線性探查法構(gòu)造的哈希表如下圖所示。圖示 線性探查法構(gòu)造的哈希表07二次（平方）探查法 將哈希表T0n-1看成是一個循環(huán)向量，若初始探查的地址為d（即H(key)=d），則探查序列為：d,d+12,d-12,d+22,d-22,。即探查時從地址d開始，首先探查Td，然后依次探查Td+1, Td-1,Td+4,Td-4等等。 探查過程終止于三種情況： 若當前探查的單元為空，對于構(gòu)造哈希表則將key寫入其中，對于查找則表示查找失??； 若當前探查的單元中含有key，對于構(gòu)造表則表示該記錄已存入哈希表，對于查找則查找成功； 若探查到Td-1時仍未發(fā)現(xiàn)空單元也未找到key，對于構(gòu)造表則此時表滿，對于查找表示查找失敗。08二次（平方）探查法設(shè)關(guān)鍵字集合為47,18,29,11,16,95,22,8,3，哈希表表長為11，哈希函數(shù)為H(key)=key mod 11。采用二次探查法構(gòu)造哈希表及在哈希表中查找過程如下：構(gòu)造哈希表：依次按哈希函數(shù)將關(guān)鍵字記錄放入哈希表，其中關(guān)鍵字29需按二次探查法，探查兩次得到地址為8的單元，將29放入，同樣關(guān)鍵字95、需探查三次找到地