數(shù)據(jù)結(jié)構(gòu)-二叉排序樹-資料下載頁
2025-08-09 15:47本頁面
【正文】 度為 13的哈希表，現(xiàn)有四個(gè)記錄，其關(guān)鍵字分別為 （ 19， 70， 33， 18） 。 哈希函數(shù)為 H(key) = key % 13, 則 H(19)=6， H(70)=5， H(33)=7， H(18)=5 用線性探測(cè)再散列方法解決沖突： H1=(H(key)+d1 ) % 13= (5+1) % 13=6 H2=(5+2) % 13=7 , H3 =(5+3) % 13 = 8 18 0 1 2 3 4 5 6 7 8 9 10 例如 : 關(guān)鍵字集合 { 19, 01, 23, 14, 55, 68, 11, 82, 36 } 設(shè)定哈希函數(shù) ： H(key) = key % 11 (表長 =11) 19 1 01 1 23 2 14 1 55 1 68 3 若采用 線性探測(cè)再散列 處理沖突 11 6 82 2 36 5 在查找概率相同的情況下， 查找成功時(shí)的 ASL ASLsucc =(1*4+2*2+3+5+6)/9 =22/9 若采用 線性探測(cè)再散列 處理沖突 0 1 2 3 4 5 6 7 8 9 10 19 1 01 1 23 2 14 1 55 1 68 3 11 6 82 2 36 5 平均查找長度 ASL： 線性探測(cè)再散列的 優(yōu)點(diǎn) ： 只要哈希表未滿，總能找到一個(gè)空地址。 缺點(diǎn)： 會(huì)產(chǎn)生二次聚集。 70 19 33 18 0 1 … 5 6 7 8 9 … 12 下一個(gè) hash地址為 8時(shí)， 將爭奪地址為 9的空間 三、 鏈地址法 將 哈希表的每一個(gè)單元 存放一個(gè)指針 ， 將所有的同義詞連成一個(gè)鏈表。 假設(shè)哈希地址在區(qū)間 [0 .. m1]上， 則 哈希 表為一個(gè) 指針數(shù)組 。 typedef struct node{ //定義鏈表中結(jié)點(diǎn) KeyType key； 其它成員 ； struct node *next； } Node， *Nodeptr； typedef Nodeptr chainhash[m]； // 定義指針數(shù)組 0 1 2 3 4 5 6 ? ? 11 19 82 ? 68 ? 55 14 ? 01 36 ? 23 ? ASLsucc =(6 1+2 2+3)/9 =13/9 例 1: 關(guān)鍵字集合 { 19, 01, 23, 14, 55, 68, 11, 82, 36 } 哈希函數(shù) H(key) = key % 7 (表長 =7) 例 2：有一組關(guān)鍵字 {BITE, EACH, BITTER, BROOM, AND, ALSO,HASH, EGGS} ，現(xiàn)以關(guān)鍵字中第一個(gè)字母在字母表中的位置為該關(guān)鍵字的 哈希函數(shù) 值， 鏈地址哈希表 如下： ASLsucc =(4*1+3*2+1*3)/8 =13/8 1 AND ALSO ? 2 BITE BITTER BROOM ? ┇ 5 EACH EGGS ? ┇ 8 HASH ? ┇ 26 (2) 、 、 (除留余數(shù)法構(gòu)造哈希函數(shù) )
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1