[高等教育]數(shù)據(jù)結構第9章查找-資料下載頁
2025-01-19 18:43本頁面
【正文】 ? 假設哈希表的長度為 11，即 n=11,哈希函數(shù)H(key)=key MOD 11， 則哈希地址集合為 0 ～ 10，此時的哈希表為空，如下圖所示。表中每一單元都可以存放一個記錄，這里，為了簡單起見， 假定記錄只有一個關鍵字域。 ? 又有一組關鍵字為 17， 60， 29， 38。下面如何構造哈希表？ 0 1 2 3 4 5 6 7 8 9 10 舉例 (1) 采用線性探測再散列的方法處理 ? 由于 H(17)=17 MOD 11=6，所以將 17加入到哈希地址為 6的單元中； ? 由于 H(60)=60 MOD 11=5，所以將 60加入到哈希地址為 5的單元中； ? 由于 H(29)=29 MOD 11=7，所以將 29加入到哈希地址為 7的單元中； ? 由于 H(38)=38 MOD 11=5，此時發(fā)生沖突（即 38與 60），另一個哈希地址 H1= (H(38)+1) MOD 11 =6，仍然沖突 （即 38與 17），下一個哈希地址 H2= (H(38)+2) MOD 11 =7，仍然沖突 （即 38與 29），下一個哈希地址 H3= (H(38)+3) MOD 11 =8，此時沒有沖突，所以 將 38加入到哈希地址為 8的單元中； 0 1 2 3 4 5 6 7 8 9 10 60 17 29 38 舉例 (2) 采用二次探測再散列的方法處理 ? 由于 H(17)=17 MOD 11=6，所以將 17加入到哈希地址為 6的單元中； ? 由于 H(60)=60 MOD 11=5，所以將 60加入到哈希地址為 5的單元中； ? 由于 H(29)=29 MOD 11=7，所以將 29加入到哈希地址為 7的單元中； ? 由于 H(38)=38 MOD 11=5，此時發(fā)生沖突（即 38與 60），另一個哈希地址 H1= (H(38)+12) MOD 11 =6，仍然沖突 （即 38與 17），下一個哈希地址 H2= (H(38) 12) MOD 11 =4，此時沒有沖突，所以 將 38加入到哈希地址為 4的單元中； 0 1 2 3 4 5 6 7 8 9 10 38 60 17 29 舉例 (3) 采用偽隨機探測再散列的方法處理 ? 由于 H(17)=17 MOD 11=6，所以將 17加入到哈希地址為 6的單元中； ? 由于 H(60)=60 MOD 11=5，所以將 60加入到哈希地址為 5的單元中； ? 由于 H(29)=17 MOD 11=7，所以將 29加入到哈希地址為 7的單元中； ? 由于 H(38)=17 MOD 11=5，此時發(fā)生沖突（即 38與 60），另一個哈希地址 H1= 偽隨機數(shù) =3，此時沒有沖突，所以 將 38加入到哈希地址為 3的單元中； 0 1 2 3 4 5 6 7 8 9 10 38 60 17 29 哈希表的查找及其分析 舉例： 計算查找給定關鍵字時的比較次數(shù) ? 在哈希表的對應關鍵字的正下方用帶括號的數(shù)字標注即可。 ? 舉例，采用線性探測再散列的方法處理時，結果如下圖所示。 ? 注意，假定給定關鍵字為 38，找到關鍵字 38需要比較 4次，即 38≠60， 38 ≠ 17， 38 ≠ 29， 38=38。 0 1 2 3 4 5 6 7 8 9 10 60 17 29 38 (1) (1) (1) (4) ? 當發(fā)生沖突時 , 探查下一個關鍵字。當循環(huán) n1次后就會回到開始探查時的位置 , 說明待查關鍵字不在表內 , 而且表已滿 , 不能再插入新關鍵字。 ? 用 平均搜索長度 ASL (Averagy Search Length)衡量散列方法的搜索性能。 ? 根據(jù)搜索成功與否，它又有搜索成功的平均搜索長度和搜索不成功的平均搜索長度之分。 ? 搜索成功的平均搜索長度 是指 搜索到表中已有記錄的平均探查次數(shù) 。它是找到表中各個已有記錄的探查次數(shù)的平均值。
教學課件相關推薦
鄂ICP備17016276號-1