(8.6.1)--ch8-6哈希处理冲突.pdf

《(8.6.1)--ch8-6哈希处理冲突.pdf》由会员分享，可在线阅读，更多相关《(8.6.1)--ch8-6哈希处理冲突.pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 Data Structures and AlgorithmsConflict-Handing Methods of Hash Table Data Structures and Algorithms Data Structures and Algorithms SearchSearchFind an address sequence for the conflicting address H(key)：H0,H1,H2,Hs 1 sm-1 Among them：H0=H(key)Hi=(H(key)+di)MOD m i=1,2,s8.4 Hash table and its search3

2、)conflict-handing methods1.Open addressing“Handle conflicts”is to find a proper next hash address instead of the conflicted one.Data Structures and Algorithms Data Structures and Algorithms SearchSearchThere are three options for the increment di：1)Linear probing rehash di=c i the simplest case c=12

3、)Quadratic probing rehash di=12,-12,22,-22,3)pseudo-random probing rehash di=pseudo-random number sequence8.4 Hash table and its search3)conflict-handing methods1.Open addressingData Structures and Algorithms Data Structures and Algorithms SearchSearchFor example:keyword collection19,01,23,14,55,68,

4、11,82,36Set hash function H(key)=key MOD 11(table length=11)0123456789101901 23 145568 11 82 36key19 01 23 14 55 68 11 82 36K%118113020531)Linear probing rehashFeatures：When a conflict occurs,check the next unit in the table in order until an empty unit is found or the entire table is searched.8.4 H

5、ash table and its search3)conflict-handing methods1.Open addressingData Structures and Algorithms Data Structures and Algorithms SearchSearchFor example:keyword collection19,01,23,14,55,68,11,82,36Set hash function H(key)=key MOD 11(table length=11)0123456789101901 23 145568 11 82 36ASLsucc=(1121362

6、51)/922/9112136251109876543211ASLunsucc=(10+9+8+7+6+5+4+3+2+1+1)/1156/118.4 Hash table and its search1.Open addressing1)Linear probing rehash3)conflict-handing methodsData Structures and Algorithms Data Structures and Algorithms SearchSearchFor example:keyword collection19,01,23,14,55,68,11,82,36Set

7、 hash function H(key)=key MOD 11(table length=11)key19 01 23 14 55 68 11 82 36K%11811302053Features：When a conflict occurs,jump detection is performed on the right and left of the table,which is more flexible.012345678910190123 145536 82 68118.4 Hash table and its search1.Open addressing2)Quadratic

8、probing rehash3)conflict-handing methodsData Structures and Algorithms Data Structures and Algorithms SearchSearchFor example:keyword collection19,01,23,14,55,68,11,82,36Set hash function H(key)=key MOD 11(table length=11)012345678910190123 145536 82 6811ASLsucc=(112121413)/916/911212143159548421213ASLunsucc=(5954842121+3)/11 44/118.4 Hash table and its search1.Open addressing3)conflict-handing methods2)Quadratic probing rehashData Structures and Algorithms Data Structures and Algorithms SearchSearch Thanks Thanks！