數(shù)據(jù)結(jié)構(gòu)散列表

數(shù)據(jù)結(jié)構(gòu)散列表第一頁，共三十四頁，編輯于2023年，星期三7.3散列表的查找技術(shù)順序查找、折半查找等。這些查找技術(shù)都是通過一系列的給定值與關(guān)鍵碼的比較，查找效率依賴于查找過程中進行的給定值與關(guān)鍵碼的比較次數(shù)。查找操作要完成什么任務(wù)？待查值k確定k在存儲結(jié)構(gòu)中的位置我們學(xué)過哪些查找技術(shù)？這些查找技術(shù)的共性？在存儲位置和關(guān)鍵碼之間建立一個確定的對應(yīng)關(guān)系能否不用比較，通過關(guān)鍵碼直接確定存儲位置？第二頁，共三十四頁，編輯于2023年，星期三概述散列的基本思想：在記錄的存儲地址和它的關(guān)鍵碼之間建立一個確定的對應(yīng)關(guān)系。這樣，不經(jīng)過比較，一次讀取就能得到所查元素的查找方法。7.3散列表的查找技術(shù)關(guān)鍵碼集合kiriH(ki)…………H第三頁，共三十四頁，編輯于2023年，星期三散列表：采用散列技術(shù)將記錄存儲在一塊連續(xù)的存儲空間中，這塊連續(xù)的存儲空間稱為散列表。概述7.3散列表的查找技術(shù)關(guān)鍵碼集合kiriH(ki)…………H散列表數(shù)組第四頁，共三十四頁，編輯于2023年，星期三散列函數(shù)：將關(guān)鍵碼映射為散列表中適當(dāng)存儲位置的函數(shù)。概述7.3散列表的查找技術(shù)散列表關(guān)鍵碼集合kiriH(ki)…………H散列函數(shù)數(shù)組第五頁，共三十四頁，編輯于2023年，星期三散列地址：由散列函數(shù)所得的存儲位置。概述7.3散列表的查找技術(shù)散列表關(guān)鍵碼集合kiriH(ki)…………H散列函數(shù)散列地址下標(biāo)數(shù)組第六頁，共三十四頁，編輯于2023年，星期三例子一組數(shù)：12，37，52，43，84，99散列函數(shù)為:H(k)=k%11散列表：長度為11012345678910123752438499第七頁，共三十四頁，編輯于2023年，星期三概述7.3散列表的查找技術(shù)散列技術(shù)僅僅是一種查找技術(shù)嗎？散列既是一種查找技術(shù)，也是一種存儲技術(shù)。散列只是通過記錄的關(guān)鍵碼定位該記錄，沒有完整地表達記錄之間的邏輯關(guān)系，所以，散列主要是面向查找的存儲結(jié)構(gòu)。散列是一種完整的存儲結(jié)構(gòu)嗎？第八頁，共三十四頁，編輯于2023年，星期三散列技術(shù)的關(guān)鍵問題：⑴散列函數(shù)的設(shè)計。如何設(shè)計一個簡單、均勻、存儲利用率高的散列函數(shù)。⑵沖突的處理。如何采取合適的處理沖突方法來解決沖突。7.3散列表的查找技術(shù)概述第九頁，共三十四頁，編輯于2023年，星期三沖突：對于兩個不同關(guān)鍵碼ki≠kj，有H(ki)＝H(kj)，即兩個不同的記錄需要存放在同一個存儲位置,ki和kj相對于H稱做同義詞。7.3散列表的查找技術(shù)概述ri關(guān)鍵碼集合ki…………H(ki)kjH(kj)第十頁，共三十四頁，編輯于2023年，星期三散列函數(shù)7.3散列表的查找技術(shù)設(shè)計散列函數(shù)一般應(yīng)遵循以下原則：⑴計算簡單。散列函數(shù)不應(yīng)該有很大的計算量，否則會降低查找效率。⑵函數(shù)值即散列地址分布均勻。函數(shù)值要盡量均勻散布在地址空間，這樣才能保證存儲空間的有效利用并減少沖突。第十一頁，共三十四頁，編輯于2023年，星期三1、散列函數(shù)——直接定址法散列函數(shù)是關(guān)鍵碼的線性函數(shù)，即：H(key)=a

key+b（a，b為常數(shù)）例：關(guān)鍵碼集合為{10,30,50,70,80,90}，選取的散列函數(shù)為H(key)=key/10，則散列表為：0123456789103050708090適用情況？事先知道關(guān)鍵碼，關(guān)鍵碼集合不是很大且連續(xù)性較好。7.3散列表的查找技術(shù)第十二頁，共三十四頁，編輯于2023年，星期三散列函數(shù)為：H(key)=keymodp

7.3散列表的查找技術(shù)2、散列函數(shù)——除留余數(shù)法如何選取合適的p，產(chǎn)生較少同義詞？一般情況下，選p為小于或等于表長（最好接近表長）的最小素數(shù)。適用情況？除留余數(shù)法是一種最簡單、也是最常用的構(gòu)造散列函數(shù)的方法，并且不要求事先知道關(guān)鍵碼的分布。第十三頁，共三十四頁，編輯于2023年，星期三根據(jù)關(guān)鍵碼在各個位上的分布情況，選取分布比較均勻的若干位組成散列地址。

例：關(guān)鍵碼為8位十進制數(shù)，散列地址為2位十進制數(shù)81346

5

3

281372

2

4281387

4

2281301

3

6781322

8

1781338

9

67①②③④⑤⑥⑦⑧7.3散列表的查找技術(shù)3、散列函數(shù)——數(shù)字分析法第十四頁，共三十四頁，編輯于2023年，星期三適用情況:能預(yù)先估計出全部關(guān)鍵碼的每一位上各種數(shù)字出現(xiàn)的頻度，不同的關(guān)鍵碼集合需要重新分析。7.3散列表的查找技術(shù)3、散列函數(shù)——數(shù)字分析法第十五頁，共三十四頁，編輯于2023年，星期三對關(guān)鍵碼平方后，按散列表大小，取中間的若干位作為散列地址（平方后截取）。7.3散列表的查找技術(shù)4、散列函數(shù)——平方取中法事先不知道關(guān)鍵碼的分布且關(guān)鍵碼的位數(shù)不是很大。適用情況:例：散列地址為2位，則關(guān)鍵碼123的散列地址為：(1234)2＝1522756第十六頁，共三十四頁，編輯于2023年，星期三將關(guān)鍵碼從左到右分割成位數(shù)相等的幾部分，將這幾部分疊加求和，取后幾位作為散列地址。7.3散列表的查找技術(shù)5、散列函數(shù)——折疊法例：設(shè)關(guān)鍵碼為25346358705，散列地址為三位。

253463587

+05───1308

移位疊加

253364587+50───1254

間界疊加適用情況:關(guān)鍵碼位數(shù)很多，事先不知道關(guān)鍵碼的分布。第十七頁，共三十四頁，編輯于2023年，星期三1、處理沖突的方法——開放定址法由關(guān)鍵碼得到的散列地址一旦產(chǎn)生了沖突，就去尋找下一個空的散列地址，并將記錄存入。如何尋找下一個空的散列地址?7.3散列表的查找技術(shù)（1）線性探測法（2）二次探測法（3）隨機探測法第十八頁，共三十四頁，編輯于2023年，星期三（1）線性探測法當(dāng)發(fā)生沖突時，從沖突位置的下一個位置起，依次尋找空的散列地址。

對于鍵值key，設(shè)H(key)=d，閉散列表的長度為m，則發(fā)生沖突時，尋找下一個散列地址的公式為：Hi=(H(key)＋di)%m

（di=1，2，…，m-1）

7.3散列表的查找技術(shù)用開放定址法處理沖突得到的散列表叫閉散列表。第十九頁，共三十四頁，編輯于2023年，星期三例：關(guān)鍵碼集合為{47,7,29,11,16,92,22,8,3}，散列表表長為11，散列函數(shù)為H(key)=keymod11，用線性探測法處理沖突，則構(gòu)造的散列表為：012345678947729111692292222883333堆積：在處理沖突的過程中出現(xiàn)的非同義詞之間對同一個散列地址爭奪的現(xiàn)象。7.3散列表的查找技術(shù)（1）線性探測法第二十頁，共三十四頁，編輯于2023年，星期三用線性探測法構(gòu)造的散列表中查找算法——偽代碼1.計算散列地址j;2.若ht[j]=k，則查找成功，返回記錄在散列表中的下標(biāo)；否則3.若ht[j]為空或?qū)⑸⒘斜硖綔y一遍，則查找失敗，轉(zhuǎn)4；否則，j指向下一單元，轉(zhuǎn)2；4.若整個散列表探測一遍，則表滿，拋出溢出異常；否則，將待查值插入；7.3散列表的查找技術(shù)第二十一頁，共三十四頁，編輯于2023年，星期三intHashSearch1(intht[],intm,intk){ intj=k%m; if(ht[j]==k) returnj;//沒有發(fā)生沖突，比較一次查找成功inti=(j+1)%m;while(i!=j) { if(ht[i]==k) returni;//發(fā)生沖突if(ht[i]==0)break; i=(i+1)%m;//向后探測一個位置 }if(i==j) throw"溢出";else { ht[i]=k; returni; }}7.3散列表的查找技術(shù)在線性探測法構(gòu)造的散列表中查找算法——C++描述第二十二頁，共三十四頁，編輯于2023年，星期三（2）二次探測法當(dāng)發(fā)生沖突時，尋找下一個散列地址的公式為：

Hi=(H(key)＋di)%m（di=12，－12，22，－22，…，q2，－q2且q≤m/2）

7.3散列表的查找技術(shù)第二十三頁，共三十四頁，編輯于2023年，星期三01234567894772911169229222288333例：關(guān)鍵碼集合為{47,7,29,11,16,92,22,8,3}，散列表表長為11，散列函數(shù)為H(key)=keymod11，用二次探測法處理沖突，則散列表為：（2）二次探測法7.3散列表的查找技術(shù)第二十四頁，共三十四頁，編輯于2023年，星期三（3）隨機探測法當(dāng)發(fā)生沖突時，下一個散列地址的位移量是一個隨機數(shù)列，即尋找下一個散列地址的公式為：

Hi=(H(key)+di)%m

（di是一個隨機數(shù)列，i=1，2，……，m-1）7.3散列表的查找技術(shù)計算機中產(chǎn)生隨機數(shù)的方法通常采用線性同余法，其中，d稱為隨機種子。當(dāng)b、c和m的值確定后，給定一個隨機種子，產(chǎn)生確定的隨機數(shù)序列。0=da=+=-1,2,Lmod)(1nmcbaann第二十五頁，共三十四頁，編輯于2023年，星期三基本思想：將所有散列地址相同的記錄，即所有同義詞的記錄存儲在一個單鏈表中（稱為同義詞子表），在散列表中存儲的是所有同義詞子表的頭指針。

用拉鏈法處理沖突構(gòu)造的散列表叫做開散列表。

設(shè)n個記錄存儲在長度為m的散列表中，則同義詞子表的平均長度為n/m。7.3散列表的查找技術(shù)2、處理沖突的方法——拉鏈法（鏈地址法）第二十六頁，共三十四頁，編輯于2023年，星期三例：關(guān)鍵碼集合{47,7,29,11,16,92,22,8,3}，散列函數(shù)為H(key)=keymod11，用拉鏈法處理沖突，構(gòu)造的開散列表為：

7.3散列表的查找技術(shù)012345678910

11∧∧∧∧∧∧2247∧392∧16∧7∧298∧第二十七頁，共三十四頁，編輯于2023年，星期三在拉鏈法構(gòu)造的散列表查找算法——偽代碼1.計算散列地址j；2.在第j個同義詞子表中順序查找；3.若查找成功，則返回結(jié)點的地址；否則，將待查記錄插在第j個同義詞子表的表頭。7.3散列表的查找技術(shù)第二十八頁，共三十四頁，編輯于2023年，星期三Node<int>*HashSearch2(Node<int>*ht[],intm,intk){j=H(k);p=ht[j];while(p&&p->data!=k)p=p->next;if(p->data==k)returnp;else{q=newNode<int>;q->data=k;q->next=ht[j];ht[j]=q;}}7.3散列表的查找技術(shù)在拉鏈法構(gòu)造的散列表查找算法——C++描述第二十九頁，共三十四頁，編輯于2023年，星期三基本思想：散列表包含基本表和溢出表兩部分（通常溢出表和基本表的大小相同），將發(fā)生沖突的記錄存儲在溢出表中。查找時，對給定值通過散列函數(shù)計算散列地址，先與基本表的相應(yīng)單元進行比較，若相等，則查找成功；否則，再到溢出表中進行順序查找。

7.3散列表的查找技術(shù)3、處理沖突的方法——公共溢出區(qū)第三十頁，共三十四頁，編輯于2023年，星期三例：關(guān)鍵碼集合{47,