數(shù)據(jù)結(jié)構(gòu)課件ppt第09章02

1、 一、一、哈希表是什么？哈希表是什么？ 二、哈希函數(shù)的構(gòu)造方法哈希函數(shù)的構(gòu)造方法 三、處理沖突的方法處理沖突的方法 四、哈希表的查找哈希表的查找 9.3 哈哈 希希 表表 以上兩節(jié)討論的表示查找表的各種結(jié)構(gòu)結(jié)構(gòu) 的共同特點(diǎn)特點(diǎn)：記錄在表中的位置位置和它的關(guān)關(guān) 鍵字鍵字之間不存在不存在一個(gè)確定的關(guān)系， 一、哈希表是什么？哈希表是什么？ 查找的過程查找的過程為給定值給定值依次和關(guān)鍵字集 合中各個(gè)關(guān)鍵字關(guān)鍵字進(jìn)行比較比較， 查找的效率查找的效率取決于和給定值進(jìn)行比較進(jìn)行比較 的關(guān)鍵字個(gè)數(shù)個(gè)數(shù)。 只有一個(gè)辦法：預(yù)先知道所查關(guān)鍵 字在表中的位置， 對于頻繁使用的查找表， 希望 ASL = 0。 即要求：

2、記錄在表中位置和其關(guān)鍵 字之間存在一種確定的關(guān)系。 若以下標(biāo)為以下標(biāo)為000 999 的順序表的順序表表示之。 例如：為每年招收的 1000 名新生建立 一張查找表，其關(guān)鍵字為學(xué)號，其值的 范圍為 xx000 xx999 (前兩位為年份)。 則查找過程可以簡單進(jìn)行：取給定值 （學(xué)號）的后三位，不需要經(jīng)過比較不需要經(jīng)過比較便 可直接從順序表中找到待查關(guān)鍵字。 因此在一般情況下，需在關(guān)鍵字與記錄 在表中的存儲位置之間建立一個(gè)函數(shù)關(guān) 系，以 f(key) 作為關(guān)鍵字為 key 的記錄 在表中的位置，通常稱這個(gè)函數(shù) f(key) 為哈希函數(shù)。 Zhao, Qian, Sun, Li, Wu, Chen

3、, Han, Ye, Dei 例如：對于如下 9 個(gè)關(guān)鍵字 設(shè)設(shè) 哈希函數(shù)哈希函數(shù) f(key) = (Ord(第一個(gè)字母第一個(gè)字母) -Ord(A)+1)/2 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 ChenZhaoQianSunLiWuHanYeDei 問題問題: 若添加關(guān)鍵字 Zhou , 怎么辦？怎么辦？ 能否找到能否找到另一個(gè)哈希函數(shù)？ 1) 哈希函數(shù)是一個(gè)映象映象，即： 將關(guān)鍵字的集合映射到某個(gè)地址集合上，將關(guān)鍵字的集合映射到某個(gè)地址集合上， 它的設(shè)置很靈活靈活，只要這個(gè)地址集地址集合的 大小不超出允許范圍不超出允許范圍即可； 從這個(gè)例子可見：從這個(gè)

4、例子可見： 2) 由于哈希函數(shù)是一個(gè)壓縮映象壓縮映象，因此， 在一般情況下，很容易產(chǎn)生“沖突沖突”現(xiàn) 象，即： key1 key2，而 f(key1) = f(key2)。 3) 很難很難找到一個(gè)不產(chǎn)生沖突的哈希函數(shù)。 一般情況下，只能選擇恰當(dāng)?shù)墓：瘮?shù)， 使沖突盡可能少地產(chǎn)生。 因此，在構(gòu)造這種特殊的“查找表” 時(shí)，除了需要選擇一個(gè)“好”(盡可能 少產(chǎn)生沖突)的哈希函數(shù)之外；還需要 找到一種“處理沖突” 的方法。 哈希表的定義： 根據(jù)設(shè)定的哈希函數(shù)哈希函數(shù) H(key) 和所選中的處處 理沖突的方法理沖突的方法，將一組關(guān)鍵字映象到映象到一個(gè)有 限的、地址連續(xù)的地址集 (區(qū)間) 上，并以關(guān) 鍵

5、字在地址集中的“象”作為相應(yīng)記錄在表 中的存儲位置存儲位置，如此構(gòu)造所得的查找表稱之 為“哈希表哈希表”或“散列表散列表”。這一映象過程 稱為“哈希造表哈希造表”或“散列散列”。所得存儲地 址稱為“哈希地址哈希地址”或“散列地址散列地址”。 二、構(gòu)造哈希函數(shù)的方法構(gòu)造哈希函數(shù)的方法 對數(shù)字?jǐn)?shù)字的關(guān)鍵字可有下列構(gòu)造方法： 若是非數(shù)字關(guān)鍵字非數(shù)字關(guān)鍵字，則需先需先對其進(jìn)行進(jìn)行 數(shù)字化處理數(shù)字化處理。 1. 直接定址法直接定址法 3. 平方取中法平方取中法 5. 除留余數(shù)法除留余數(shù)法 4. 折疊法折疊法 6. 隨機(jī)數(shù)法隨機(jī)數(shù)法 2. 數(shù)字分析法數(shù)字分析法 哈希函數(shù)為關(guān)鍵字的線性函數(shù) H(key) =

6、 key 或者 H(key) = a key + b 1. 直接定址法直接定址法 此法僅適合于：此法僅適合于： 地址集合的大小地址集合的大小 = = 關(guān)鍵字集合的大小關(guān)鍵字集合的大小 2. 除留余數(shù)法除留余數(shù)法 設(shè)定哈希函數(shù)為設(shè)定哈希函數(shù)為: H(key) = key MOD p 其中其中， pm ( (表長表長) ) 并且并且 p 應(yīng)為不大于應(yīng)為不大于 m 的素?cái)?shù)的素?cái)?shù) 或是或是 不含不含 20 以下的質(zhì)因子以下的質(zhì)因子 給定一組關(guān)鍵字為：12, 39, 18, 24, 33, 21， 若取 p=9, 則他們對應(yīng)的哈希函數(shù)值將為： 3, 3, 0, 6, 6, 3 例如：例如： 為什么要對

7、p 加限制？ 可見，若 p 中含質(zhì)因子 3， 則所有含質(zhì)則所有含質(zhì) 因子因子 3 的關(guān)鍵字均映射到的關(guān)鍵字均映射到“3 的倍數(shù)的倍數(shù)”的的 地址上地址上，從而增加了“沖突”的可能。 實(shí)際造表時(shí)，采用何種采用何種構(gòu)造哈希 函數(shù)的方法方法取決于建表的關(guān)鍵字集合 的情況(包括關(guān)鍵字的范圍和形態(tài))， 總的原則是使產(chǎn)生沖突的可能性降到的原則是使產(chǎn)生沖突的可能性降到 盡可能地小盡可能地小。 三、處理沖突的方法處理沖突的方法 “處理沖突處理沖突” 的實(shí)際含義是： 為產(chǎn)生沖突的地址尋找下一個(gè)尋找下一個(gè)哈希地址。 1. 開放定址法開放定址法 2. 再哈希法再哈希法 3. 鏈地址法（不講）鏈地址法（不講） 為產(chǎn)生

8、沖突的地址 H(key) 求得一個(gè) 地址序列地址序列： H0, H1, H2, , , Hs 1 sm-1 其中：H0 = H(key) Hi = ( H(key) + di ) MOD m i=1, 2, , s 1. 開放定址法開放定址法 對增量 di 有三種取法： o1) 線性探測再散列線性探測再散列 di = c i 最簡單的情況 c=1 o2) 平方探測再散列平方探測再散列 di = 12, -12, 22, -22, , , o3) 隨機(jī)探測再散列隨機(jī)探測再散列 di 是一組偽隨機(jī)數(shù)列偽隨機(jī)數(shù)列 注意：注意：增量增量 di 應(yīng)具有應(yīng)具有“完備性完備性” 例如例如: 關(guān)鍵字集合 19

9、, 01, 23, 14, 55, 68, 11, 82, 36 設(shè)定設(shè)定哈希函數(shù) H(key) = key MOD 11 ( 表長=11 ) 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 190123 145568 190123 1468 若采用線性探測再散列線性探測再散列處理沖突 若采用二次探測再散列二次探測再散列處理沖突 11 8236 55118236 1 1 2 1 3 6 2 5 1 1 1 2 1 2 1 4 1 3 兩種方法的平均查找長度： o 線性探測再散列： n ASL(9)=1/9(14+22+3+5+6)=22/9 o 二次

10、探測再散列： n ASL(9)=1/9(15+22+3+4)=16/9 o1) 選用的哈希函數(shù)哈希函數(shù)； o2) 選用的處理沖突的方法處理沖突的方法； o3) 哈希表飽和的程度，裝載因子裝載因子 =n/m 值的大小大?。╪記錄數(shù)，記錄數(shù)，m表的長度）表的長度） 決定哈希表查找的決定哈希表查找的ASL的因素的因素： 哈希表查找的分析: 從查找過程得知，哈希表查找的 平均查找長度實(shí)際上并不等于零實(shí)際上并不等于零。 哈希表的平均查找長度 利用裝填因子所計(jì)算的平均查找長度是近似 值！ o 線性探測再散列哈希表： o 二次探測再散列、隨即探測再散列哈希表： 1 1 1 2 1 nl S 1ln 1 nr

11、 S 2. 再哈希法再哈希法 oHi=RHi(key) i=1,2,.k RHi是不同的哈希函數(shù)，當(dāng)產(chǎn)生地址是不同的哈希函數(shù)，當(dāng)產(chǎn)生地址 沖突時(shí)計(jì)算另一個(gè)哈希函數(shù)地址，直沖突時(shí)計(jì)算另一個(gè)哈希函數(shù)地址，直 到?jīng)_突不再發(fā)生。到?jīng)_突不再發(fā)生。 這種方法不易產(chǎn)生這種方法不易產(chǎn)生“聚集聚集”，但增加了，但增加了 計(jì)算時(shí)間。計(jì)算時(shí)間。 課堂習(xí)題 o 設(shè)有一個(gè)按各元素的值排好序的線性表且長 度大于2，對給定的值K，分別用順序查找 法和折半查找法查找一個(gè)與K相等的元素， 比較次數(shù)分別是s和b；在查找不成功的情 況下，正確的s和b的數(shù)量關(guān)系是（ ）。 A. 總有s=b B. 總有sb C. 總有sb D. 與K值大小有關(guān) 答案：B o 對有18個(gè)元素的有序表A作二分（折半）查 找，則查找A3的比較序列的下標(biāo)為（） A. 1,2,3 B. 9,5,2,3 C. 9,5,3 D. 9,4,2,3 答案：D o設(shè)散列表長m=14，散列函數(shù)為h(k)=k%11,表 中已有4個(gè)記錄，如果用二次探測再散列來處理沖 突，則關(guān)鍵字為49的記錄其存儲地址是（）。 A. 8 B. 3 C. 5 D. 9 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 15 386184 答案：D o 在采用線性