數(shù)據(jù)結(jié)構(gòu)-基于C++語言（微課版） 課件 1-1 散列表

散列表的基本概念；散列函數(shù)的設(shè)計方法；處理沖突的方法。本節(jié)目錄：本節(jié)內(nèi)容：散列表散列表

散列表

什么是查找?

確定待查找值k在存儲結(jié)構(gòu)中的位置。有哪些查找技術(shù)？

順序查找、折半查找、二叉排序樹查找等技術(shù)都是通過一系列的給定值與關(guān)鍵碼的比較，查找效率依賴于查找過程中進(jìn)行的給定值與關(guān)鍵碼的比較次數(shù)。關(guān)鍵碼可以直接確定存儲位置？

在記錄的存儲地址和它的關(guān)鍵碼之間建立一個確定的對應(yīng)關(guān)系散列表

散列的基本思想：在記錄的存儲地址和它的關(guān)鍵碼之間建立一個確定的對應(yīng)關(guān)系。這樣，不經(jīng)過比較，一次讀取就能得到所查元素的查找方法。3關(guān)鍵碼集合kiriH(ki)…………H散列表

散列表：采用散列技術(shù)將記錄存儲在一塊連續(xù)的存儲空間中，這塊連續(xù)的存儲空間稱為散列表，可以用一維數(shù)組來描述。關(guān)鍵碼集合kiriH(ki)…………H散列表散列表

散列函數(shù)：將關(guān)鍵碼映射為散列表中適當(dāng)存儲位置的函數(shù)。關(guān)鍵碼集合kiriH(ki)…………H散列表散列函數(shù)散列表

散列地址：由散列函數(shù)所得的存儲地址。關(guān)鍵碼集合kiriH(ki)…………H散列表散列函數(shù)散列地址下標(biāo)散列表

由于在散列表中記錄的存儲位置是根據(jù)關(guān)鍵碼和散列函數(shù)計算所得，因此散列表并不支持范圍查找，例如，散列表不支持查找關(guān)鍵碼最大、最小、大于等于某值、小于等于某值等范圍查找。散列表最適合的問題是，散列表中哪個記錄的關(guān)鍵碼等于待查找的關(guān)鍵碼值。散列技術(shù)在計算機(jī)領(lǐng)域具有廣泛的應(yīng)用，例如信息加密、數(shù)據(jù)校驗、負(fù)載均衡等。對于兩個不同的關(guān)鍵碼ki≠kj，有H(ki)=H(kj)，即兩個不同的記錄需要存儲到同一個散列地址中，這種現(xiàn)象稱為沖突。ki和kj相對于H稱做同義詞。沖突太多會降低查找效率，因此要設(shè)計一個均勻、存儲利用率高的散列函數(shù)，即散列函數(shù)計算出來的地址應(yīng)能均勻分布在整個地址空間中。但是沖突難以避免。散列查找中最關(guān)鍵的兩個問題為散列函數(shù)的設(shè)計和沖突的處理。散列函數(shù)

散列函數(shù)設(shè)計原則：散列函數(shù)的定義域必須包括需要存儲的全部數(shù)據(jù)元素的關(guān)鍵字，而如果散列表允許有m個地址時，其值域必須在0到m-1之間；散列函數(shù)計算出來的地址應(yīng)能均勻分布在整個地址空間中，若key是從關(guān)鍵字集合中隨機(jī)抽取的一個關(guān)鍵字，散列函數(shù)應(yīng)能以同等概率取0到m-1中的每一個值；散列函數(shù)應(yīng)是簡單的，能在較短的時間內(nèi)計算出結(jié)果。散列函數(shù)

散列函數(shù)——直接定址法

0123456789103050708090散列函數(shù)

散列函數(shù)——數(shù)字分析法分析關(guān)鍵碼，例如前幾位數(shù)字大體相同的一組學(xué)號，如果選用前幾位數(shù)字構(gòu)造散列地址，則出現(xiàn)沖突的概率較大。如選擇差別較大的幾位數(shù)字構(gòu)造散列地址，則沖突的概率會明顯降低。找出數(shù)字的規(guī)律，利用這些數(shù)據(jù)來構(gòu)造沖突較少的散列地址。例：關(guān)鍵碼為8位十進(jìn)制數(shù)，散列地址為2位十進(jìn)制數(shù)81346

5

3

281372

2

4281387

4

2281301

3

6781322

8

1781338

9

67①②③④⑤⑥⑦⑧散列函數(shù)

散列函數(shù)——除留余數(shù)法

1470147014散列地址56494235282114關(guān)鍵碼例：若取p=21，產(chǎn)生了大量沖突散列表

在構(gòu)造散列表的過程中，在存儲關(guān)鍵碼對應(yīng)的記錄時，如果H(key)已經(jīng)被占用，則必須另外再尋找一個空閑的位置來存儲記錄。采用不同的處理沖突的方法，就會得到不同的散列表。常用的處理沖突的方法有開地址方法和鏈地址方法。散列表

處理沖突的方法——開放定址法由關(guān)鍵碼得到的散列地址一旦產(chǎn)生了沖突，就去尋找下一個空的散列地址，并將記錄存入。使用開放定址法構(gòu)造的散列表稱為閉散列表。如何尋找下一個空的散列地址?線性探測法二次探測法隨機(jī)探測法散列表

線性探測法當(dāng)發(fā)生沖突時，從沖突位置的下一個位置起，依次尋找空的散列地址。假設(shè)對于關(guān)鍵碼key，H(key)=d，閉散列表的長度為m，則線性探測法尋找下一個空閑位置的公式為：Hi=(H(key)+di)

%

m

(di=1,2,?,m?1)例：關(guān)鍵碼集合為{47,7,29,11,16,92,22,8,3}，散列表表長為11，散列函數(shù)為H(key)=keymod11，用線性探測法處理沖突，則散列表為：47729111692292222883333堆積：在處理沖突的過程中出現(xiàn)的非同義詞之間對同一個散列地址爭奪的現(xiàn)象。012345678910線性探測法散列表

二次探測法當(dāng)發(fā)生沖突時，尋找下一個散列地址的公式為：

Hi=(H(key)＋di)%m，di=12，-12，22，-22，…，q2，-q2

且q≤m/2例：關(guān)鍵碼集合為{47,7,29,11,16,92,22,8,3}，散列表表長為11，散列函數(shù)為H(key)=keymod11，用線性探測法處理沖突，則散列表為：4772911169229222288333012345678910散列表

雙散列法使用雙散列方法處理沖突時，需要兩個散列函數(shù)。第一個散列函數(shù)Hash()按數(shù)據(jù)元素的關(guān)鍵字key計算出數(shù)據(jù)元素存放地址。一旦發(fā)生沖突，利用第二個散列函數(shù)ReHash()計算出數(shù)據(jù)元素下一地址，它的取值與key的值有關(guān)，應(yīng)小于地址空間的大小。散列表

散列表

處理沖突的方法——鏈地址法解決沖突的另一種方法稱為開散列法，也稱為鏈地址法、拉鏈法?；舅枷霝椋簩⑺械耐x詞的記錄存儲為一個單鏈表，稱為同義詞子表，散列表存儲的是同義詞子表的頭指針。使用鏈地址方法處理沖突構(gòu)造的散列表稱為開散列表。開散列表不會出現(xiàn)堆積現(xiàn)象。散列表

例：關(guān)鍵碼集合{47,7,29,11,16,92,22,8,3}，散列函數(shù)為H(key)=keymod11，用拉鏈法處理沖突，構(gòu)造的開散列表為：012345678910

11∧∧∧∧∧∧

22

47∧

3

92∧

16∧

7∧

29

8∧散列表

處理沖突的方法——鏈地址法解決沖突的另一種方法稱為開散列法，也稱為鏈地址法、拉鏈法?；舅枷霝椋簩⑺械耐x詞的記錄存儲為一個單鏈表，稱為同義詞子表，散列表存儲的是同義詞子表的頭指針。使用鏈地址方法處理沖突構(gòu)造的散列表稱為開散列表。開散列表不會出現(xiàn)堆積現(xiàn)象。散列表

散列表的裝載因子是散列表中的記錄數(shù)n和散列表表長m的比值，可表示為：