【正文】 移位疊加 5 8 6 4 0 2 2 4 0 4 6 0 9 2 H(key)=6092 間界疊加 Data Structure Page 93 2022/1/4 ?除留余數(shù)法 ? 思想 ? 以關(guān)鍵字被某個(gè)數(shù) p除后所得余數(shù)作為哈希地址。 ? 公式 ? H(key) = key MOD p 其中， MOD表示 “ 取模 ” 運(yùn)算； p 為不大于表長(zhǎng)的素?cái)?shù)或不包含小于 20的質(zhì)因素的合數(shù) 。 ? 特點(diǎn) ? 簡(jiǎn)單、常用，可與上述幾種方法結(jié)合使用。 ? p的選取很重要； p選的不好，容易產(chǎn)生同義詞。 Data Structure Page 94 2022/1/4 例如：給定存儲(chǔ)單元地址為 1,000,000?1,000,027，即 表長(zhǎng)度為 28。 則關(guān)鍵字 172,148的哈希地址為 H(key)= 172148 MOD 23 + 1,000,000 = 16+1,000,000 = 1,000,016 Data Structure Page 95 2022/1/4 ?隨機(jī)數(shù)法 ? 思想 ? 當(dāng)關(guān)鍵字不等長(zhǎng)時(shí)， 可取關(guān)鍵字的某個(gè)偽隨機(jī)函數(shù)值 作為哈希地址。 ? 公式 ? H(key) = random(key) ?使用情況 ? 適于 關(guān)鍵字長(zhǎng)度不等 的情況。 Data Structure Page 96 2022/1/4 ?選取哈希函數(shù)，考慮以下因素： ?計(jì)算哈希函數(shù)所需時(shí)間 ?關(guān)鍵字長(zhǎng)度 ?哈希表長(zhǎng)度（哈希地址范圍） ?關(guān)鍵字分布情況 ?記錄的查找頻率 Data Structure Page 97 2022/1/4 處理沖突的方法 ?開(kāi)放定址法 ? 思想 ? 當(dāng)沖突發(fā)生時(shí)，形成一個(gè)探查序列；沿此序列逐個(gè)地址探查，直到找到一個(gè)空位置（開(kāi)放的地址），將發(fā)生沖突的記錄放到該地址中。 ? 公式 ? Hi=(H(key)+di)MOD m， i=1,2,…… k(k?m1) 其中： H(key)—— 哈希函數(shù) m—— 哈希表表長(zhǎng) di—— 增量序列 ? 線性探測(cè)再散列 ： di=1,2,3,…… m1 ? 二次探測(cè)再散列 ： di=1178。,1178。,2178。,2178。,3178。,…… 177。 k178。(k?m/2) ? 偽隨機(jī)探測(cè)再散列 ： di=偽隨機(jī)數(shù)序列 Data Structure Page 98 2022/1/4 線性探測(cè)再散列 H(38)=38 MOD 11=5 沖突 H1=(5+1) MOD 11=6 沖突 H2=(5+2) MOD 11=7 沖突 H3=(5+3) MOD 11=8 不沖突 38 例如：表長(zhǎng)為 11的哈希表中已填有關(guān)鍵字為 1 60、 29的記 錄， H(key)=key MOD 11， 現(xiàn)有第 4條記錄，其 關(guān)鍵字 為 38，按三種處理沖突的方法，將它填入表中。 29 17 60 10 9 8 7 6 5 4 3 2 1 Data Structure Page 99 2022/1/4 38 例如：表長(zhǎng)為 11的哈希表中已填有關(guān)鍵字為 1 60、 29的記 錄， H(key)=key MOD 11， 現(xiàn)有第 4條記錄，其 關(guān)鍵字 為 38，按三種處理沖突的方法，將它填入表中。 29 17 60 10 9 8 7 6 5 4 3 2 1 二次探測(cè)再散列 H(38)=38 MOD 11=5 沖突 H1=(5+1178。) MOD 11=6 沖突 H2=(51178。) MOD 11=4 不沖突 Data Structure Page 100 2022/1/4 38 例如：表長(zhǎng)為 11的哈希表中已填有關(guān)鍵字為 1 60、 29的記 錄， H(key)=key MOD 11， 現(xiàn)有第 4條記錄，其 關(guān)鍵字 為 38，按三種處理沖突的方法，將它填入表中。 29 17 60 10 9 8 7 6 5 4 3 2 1 偽隨機(jī)探測(cè)再散列 H(38)=38 MOD 11=5 沖突 設(shè)偽隨機(jī)數(shù)序列為 9，則： H1=(5+9) MOD 11=3 不沖突 Data Structure Page 101 2022/1/4 ?鏈地址法 ? 思想 ? 將所有 關(guān)鍵字為 同義詞 的記錄鏈接在一個(gè)線性鏈表中 。此時(shí)的哈希表以 指針數(shù)組 的形式出現(xiàn)，數(shù)組內(nèi)各個(gè)分量存儲(chǔ)相應(yīng)哈希地址的鏈表的頭指針。 Data Structure Page 102 2022/1/4 例如：已知一組關(guān)鍵字 (19,56,23,14,68,82,70,36,91 ) 哈希函數(shù)為： H(key)=key MOD 7， 用鏈地址法處理沖突。 ? ? ? ? ? ? ? 6 5 4 3 2 1 0 56 ? 19 ? 23 ? ? 14 ? 68 ? 82 ? 70 36 ? ? 91 Data Structure Page 103 2022/1/4 ?再哈希法 ? 思想 ? 構(gòu)造若干個(gè)哈希函數(shù)， 當(dāng)發(fā)生沖突時(shí)，用另一個(gè)哈希函數(shù)計(jì)算另一個(gè)哈希地址 ，直至不發(fā)生沖突為止。 ? 特點(diǎn) ? 需要預(yù)先設(shè)置一個(gè)哈希函數(shù)的序列； ? 計(jì)算時(shí)間增加 。 ?建立一個(gè)公共溢出區(qū) ? 思想 ? 建立兩個(gè)表，一個(gè)是基本表，另一個(gè)是溢出表（存放所有關(guān)鍵字和基本表中關(guān)鍵字沖突的記錄，一旦沖突發(fā)生，就存入溢出表）。 Data Structure Page 104 2022/1/4 哈希表的查找及其分析 ?哈希查找過(guò)程 給定 k值 計(jì)算 H(k) 此地址為空 關(guān)鍵字 ==k 查找失敗 查找成功 按處理沖突 方法計(jì)算 Hi Y N Y N Data Structure Page 105 2022/1/4 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 已知一組關(guān)鍵字 (19,14,23,1,68,20,84,27,55,11,10,79)，按哈希函數(shù) H(key)=key MOD 13和 線性探測(cè)再散列處理沖突 構(gòu)造哈希表， 設(shè)每個(gè)記錄的查找概率相等，求平均查找長(zhǎng)度。（哈希表長(zhǎng) 16） 14 1 68 27 55 19 20 84 79 23 11 10 1 H(19)=6 H(14)=1 H(23)=10 H(1)=1 H(68)=3 H(20)=7 H(84)=6 1 1 沖突， H1=(1+1) MOD16=2 2 1 1 沖突， H1=(6+1)MOD16=7 沖突， H2=(6+2)MOD16=8 3 H(27)=1 沖突， H3=(1+3)MOD16=4 沖突， H1=(1+1)MOD16=2 沖突， H2=(1+2)MOD16=3 4 Data Structure Page 106 2022/1/4 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 已知一組關(guān)鍵字 (19,14,23,1,68,20,84,27,55,11,10,79)，按哈希函數(shù) H(key)=key MOD 13和 線性探測(cè)再散列處理沖突 構(gòu)造哈希表， 設(shè)每個(gè)記錄的查找概率相等，求平均查找長(zhǎng)度。（哈希表長(zhǎng) 16） 14 1 68 27 55 19 20 84 79 23 11 10 1 1 1 2 1 1 3 4 H(55)=3 H(10)=10 H(11)=11 沖突， H1=(3+1)MOD16=4 沖突， H2=(3+2)MOD16=5 3 沖突， H1=(10+1)MOD16=11 沖突， H2=(10+2)MOD16=12 3 1 Data Structure Page 107 2022/1/4 H(79)=1 ASL= 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 已知一組關(guān)鍵字 (19,14,23,1,68,20,84,27,55,11,10,79)，按哈希函數(shù) H(key)=key MOD 13和 線性探測(cè)再散列處理沖突 構(gòu)造哈希表， 設(shè)每個(gè)記錄的查找概率相等，求平均查找長(zhǎng)度。（哈希表長(zhǎng) 16） 14 1 68 27 55 19 20 84 79 23 11 10 沖突， H1=(1+1)MOD16=2 沖突， H2=(1+2)MOD16=3 沖突， H3=(1+3)MOD16=4 沖突， H4=(1+4)MOD16=5 沖突， H5=(1+5)MOD16=6 沖突， H6=(1+6)MOD16=7 沖突， H7=(1+7)MOD16=8 沖突， H8=(1+8)MOD16=9 1 1 1 2 1 1 3 4 3 3 1 9 (1*6+2+3*3+4+9)/12 = Data Structure Page 108 2022/1/4 已知一組關(guān)鍵字 (19,14,23,1,68,20,84,27,55,11,10,79)，按哈希函數(shù) H(key)=key MOD 13和 鏈地址法處理沖突 構(gòu)造哈希表， 設(shè)每個(gè)記錄的查找概率相等，求平均查找長(zhǎng)度。 ^ ^ ^ ^ ^ ^ ^ 79 27 1 14 ^ 55 68 ^ 84 19 ^ 20 ^ 10 23 ^ 11 ^ 0 1 2 3 4 5 6 7 8 9 10 11 12 ASL= (1*6+2*4+3+4)/12 = Data Structure Page 109 2022/1/4 ?哈希法的分析 ? 哈希法比其它查找方法的效率高。 ? 沖突不可避免， 發(fā)生沖突的次數(shù)與表的裝填程度有關(guān) ，表越滿，發(fā)生沖突的可能性就越大，查找也越慢。 ? 在 哈希函數(shù)相同 的情況下， 處理沖突的方法不同 ，所得 哈希表的平均查找長(zhǎng)度也不同 。 ? 線性探測(cè)再散列處理沖突容易造成記錄的 “ 二次聚集 ” ，即使得本不是同義詞的關(guān)鍵字又產(chǎn)生新的沖突； ? 對(duì) 開(kāi)放定址處理沖突的哈希表 而言， 表長(zhǎng)必須 ≥ 記錄數(shù) 。 ? 鏈地址處理沖突的哈希表不要求表長(zhǎng)必須 ≥ 記錄數(shù)， 它的平均查找長(zhǎng)度主要取決于哈希函數(shù)本身。 ? 表 中 添 入 的 記 錄 數(shù)裝 填 因 子 = 表 的 長(zhǎng) 度Data Structure Page 110 2022/1/4 ?在等概率查找的情況下，可以證明： ? 線性探測(cè)再散列的哈希表查找成功 的平均查找長(zhǎng)度為 ? 隨機(jī)探測(cè)再散列、二次探測(cè)再散列和再哈希的哈希表查找成功 的平均查找長(zhǎng)度為 ? 鏈地址處理沖突的哈希表查找成功 的平均查找長(zhǎng)度為 11(1 )21nlS ??? ?1 l n ( 1 )nrS ??? ? ?1 2ncS ???Data Structure Page 111 2022/1/4 ? 線性探測(cè)再散列的哈希表查找不成功 的平均查找長(zhǎng)度為 ? 隨機(jī)探測(cè)再散列、二次探測(cè)再散列和再哈希的哈希表查找不成功的平均查找長(zhǎng)度為 ? 鏈地址處理沖突的哈希表查找不成功 的平均查找長(zhǎng)度為 211( 1 )2 ( 1 )nlU ??? ?11nrU ?? ?ncUe ?? ???Data Structure Page 112 2022/1/4 本章小結(jié) ?查找表即為集合結(jié)構(gòu) ，表中記錄之間本不存在約束條件，但為了提高查找速度，在計(jì)算機(jī)中構(gòu)建查找表時(shí)，應(yīng)人為地在記錄的關(guān)鍵字之間加上某些約束條件，即以其它結(jié)構(gòu)表示之。由于 查找過(guò)程中的主要操作是關(guān)鍵字和給定值進(jìn)行比較 ，因此以一次查找所需進(jìn)行的比較次數(shù)的期望值作為 查找方法效率的衡量標(biāo)準(zhǔn) ，稱之謂 平均查找長(zhǎng)度 。 ?在本章中介紹了查找表的三類存儲(chǔ)表示方法： 順序表、樹(shù)表和哈希表 。這里的 順序表 指的是順序存儲(chǔ)結(jié)構(gòu)，包括有序表和索引順序表，因此 主要用于表示靜態(tài)查找表 ，樹(shù)表包括靜態(tài)查找樹(shù)、二叉查找樹(shù)和二叉平衡樹(shù)， 樹(shù)表和哈希表主要用于表示動(dòng)態(tài)查找表 。 Data Structure Page 113 2022/1/4 ?所有順序結(jié)構(gòu)的表和查找樹(shù)的平均查找長(zhǎng)度都是隨之查找表中記錄數(shù)的增加而增大，而哈希表的平均查找長(zhǎng)度是裝填因子的函數(shù)，因此有 可能設(shè)計(jì)出使平均查找長(zhǎng)度不超過(guò)某個(gè)期望值的哈希表 。 Data Structure Page 114 2022/1/4 基礎(chǔ)知識(shí)題 ?若對(duì)大小均為 n 的有序的順序表和無(wú)序的順序表分別進(jìn)行順序查找，試在下列三種情況下分別討論兩者在等概時(shí)的平均查找長(zhǎng)度是否相同 ? ? 查找不成功，即表中沒(méi)有關(guān)鍵字等于給定值 K 的記錄； ? 查找成功，且表中只有一個(gè)關(guān)鍵字等于給定值 K 的記錄； ? 查找成功，且表中有若干個(gè)關(guān)鍵字等于給定值 K的記錄，一次查找