6-4散列表的查找技術(shù)v第六章查找技術(shù)回顧查找技術(shù)查找操作要完成什么任務(wù)？待查值k確定k在存儲(chǔ)結(jié)構(gòu)中的位置前面學(xué)過哪些查找技術(shù)？這些查找技術(shù)有什么共性呢？10152461235409855012345678（1）順序查找（2）折半查找101520253035404550012345678==、!=<、==、>O(n)O(log2n)O(n)~(log2n)635542907058（3）二叉搜索樹查找通過一系列的給定值與關(guān)鍵碼的比較，查找效率依賴于查找過程中進(jìn)行的給定值與關(guān)鍵碼的比較次數(shù)Ω(log2n)查找技術(shù)的分類能否不用比較，通過關(guān)鍵碼能夠直接確定存儲(chǔ)位置？在存儲(chǔ)位置和關(guān)鍵碼之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系查找技術(shù)比較式查找計(jì)算式查找設(shè)關(guān)鍵碼key在存儲(chǔ)結(jié)構(gòu)中的位置是addr，則有addr=H(key)。

學(xué)什么？散列查找的基本思想散列函數(shù)的設(shè)計(jì)處理沖突的方法散列查找的性能分析開散列表與閉散列表的比較6-4-1散列查找的基本思想v第六章查找技術(shù)散列的基本思想關(guān)鍵碼集合ri…………H(ki)Hki散列的基本思想：在記錄的關(guān)鍵碼和存儲(chǔ)地址之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系，通過計(jì)算得到待查記錄的地址。散列技術(shù)能進(jìn)行范圍查找嗎？適合于哪種類型的查找？散列技術(shù)最適合回答的問題是：如果有的話，哪個(gè)記錄的關(guān)鍵碼等于待查值？散列的基本概念關(guān)鍵碼集合ri…………H(ki)Hki散列表：采用散列技術(shù)存儲(chǔ)查找集合的連續(xù)存儲(chǔ)空間。散列表數(shù)組散列函數(shù)：將關(guān)鍵碼映射為散列表中適當(dāng)存儲(chǔ)位置的函數(shù)。散列函數(shù)散列地址：由散列函數(shù)所得的存儲(chǔ)地址。散列地址下標(biāo)散列的關(guān)鍵問題關(guān)鍵碼集合ri…………H(ki)Hki如何設(shè)計(jì)散列函數(shù)？如何解決沖突？沖突：對(duì)于兩個(gè)不同關(guān)鍵碼ki≠kj，有H(ki)＝H(kj)。同義詞：ki和kj相對(duì)于H稱做同義詞。

kj散列是一種完整的存儲(chǔ)結(jié)構(gòu)嗎？散列只是通過記錄的關(guān)鍵碼定位該記錄，沒有完整地表達(dá)記錄之間的邏輯關(guān)系，所以，散列主要是面向查找的存儲(chǔ)結(jié)構(gòu)。6-4-2散列函數(shù)的設(shè)計(jì)v第六章查找技術(shù)設(shè)計(jì)原則關(guān)鍵碼集合ri…………H(ki)Hki如何設(shè)計(jì)散列函數(shù)？（1）計(jì)算簡(jiǎn)單。散列函數(shù)不應(yīng)該有很大的計(jì)算量，否則會(huì)降低查找效率。（2）地址均勻。函數(shù)值要盡量均勻散布在地址空間，保證存儲(chǔ)空間的有效利用并減少?zèng)_突。Hash哈希雜湊散列散列技術(shù)名稱的演變過程：常見的散列函數(shù)散列函數(shù)是關(guān)鍵碼的線性函數(shù)，即：H(key)=a

key+b（a，b為常數(shù)）例1關(guān)鍵碼集合為{10,30,50,70,80,90}，選取的散列函數(shù)為H(key)=key/10，散列表構(gòu)造過程如下：0123456789103050708090直接定址法適用于：事先知道關(guān)鍵碼，關(guān)鍵碼集合不是很大且連續(xù)性較好平方取中法對(duì)關(guān)鍵碼平方后，按散列表大小，取中間的若干位作為散列地址。適用于：事先不知道關(guān)鍵碼的分布且關(guān)鍵碼的位數(shù)不是很大例2散列地址為2位，設(shè)計(jì)平方取中法的散列函數(shù)。(1234)2＝1522756(1235)2＝1525225平方擴(kuò)大了相近數(shù)之間的差別常見的散列函數(shù)除留余數(shù)法H(key)=keymodp

如何選取p，才能產(chǎn)生較少的同義詞？1470147014散列地址56494235282114關(guān)鍵碼例如：p=21=3×777常見的散列函數(shù)例3散列表長(zhǎng)為15，設(shè)計(jì)除留余數(shù)法的散列函數(shù)。

H(key)=keymod13適用于：最簡(jiǎn)單、最常用，不要求事先知道關(guān)鍵碼的分布小于等于表長(zhǎng)（最好接近表長(zhǎng)）的最小素?cái)?shù)或不包含小于20質(zhì)因子6-4-3處理沖突的方法v第六章查找技術(shù)開放定址法開放定址法如何處理沖突？對(duì)于給定的關(guān)鍵碼key執(zhí)行下述操作：（1）計(jì)算散列地址：j=H(key)如何尋找一個(gè)空的散列地址呢？（3）如果在地址j發(fā)生沖突，則尋找一個(gè)空的散列地址，存儲(chǔ)key對(duì)應(yīng)的記錄；（2）如果地址j

的存儲(chǔ)單元沒有存儲(chǔ)記錄，則存儲(chǔ)key對(duì)應(yīng)的記錄；（1）線性探測(cè)法；（2）二次探測(cè)法；（3）隨機(jī)探測(cè)法……閉散列表：用開放定址法處理沖突得到的散列表閉散列表的類定義constintMaxSize=100;classClosedHashTable{public:ClosedHashTable();~ClosedHashTable();intInsert(intk);intDelete(intk);intSearch(intk);private:intH();intht[MaxSize];};ClosedHashTable::ClosedHashTable(){for(inti=0;i<MaxSize;i++)ht[i]=0;}ClosedHashTable::~ClosedHashTable(){}線性探測(cè)法Hi=(H(key)＋di)%m

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

線性探測(cè)法：從沖突位置的下一個(gè)位置起，依次尋找空的散列地址。設(shè)散列表的長(zhǎng)度為m，對(duì)于鍵值key，發(fā)生沖突時(shí)，尋找空散列地址的公式為：例1設(shè)關(guān)鍵碼集合為{47,7,29,11,16,92,22,8,3}，散列表表長(zhǎng)為11，散列函數(shù)為H(key)=keymod11，用線性探測(cè)法處理沖突，散列表的構(gòu)造過程如下：47729111692292222883333012345678910堆積：非同義詞對(duì)同一個(gè)散列地址爭(zhēng)奪的現(xiàn)象偽代碼算法：Search輸入：閉散列表ht[]，待查值k輸出：如果查找成功，則返回記錄的存儲(chǔ)位置，否則返回查找失敗的標(biāo)志-11.計(jì)算散列地址j；2.探測(cè)下標(biāo)i初始化：i=j；3.執(zhí)行下述操作，直到ht[i]為空：3.1若ht[i]等于k，則查找成功，返回記錄在散列表中的下標(biāo)；3.2否則，i指向下一單元；4.查找失敗，返回失敗標(biāo)志-1；算法實(shí)現(xiàn)intClosedHashTable::Search(intk){inti,j=H(k);//計(jì)算散列地址i=j;//設(shè)置比較的起始位置while(ht[i]!=0){if(ht[i]==k)returni;//查找成功elsei=(i+1)%m;//向后探測(cè)一個(gè)位置}return-1;//查找失敗}二次探測(cè)法Hi=(H(key)＋di)%m

（di=12,-12,22,-22,…,q2,-q2(q≤m/2)）二次探測(cè)法：以沖突位置為中心，跳躍式尋找空的散列地址。設(shè)散列表的長(zhǎng)度為m，對(duì)于鍵值key，發(fā)生沖突時(shí)，尋找空散列地址的公式為：例2設(shè)關(guān)鍵碼集合為{47,7,29,11,16,92,22,8,3}，散列表表長(zhǎng)為11，散列函數(shù)為H(key)=keymod11，用二次探測(cè)法處理沖突，散列表的構(gòu)造過程如下：4772911169229222288333012345678910相對(duì)于線性探測(cè)法，二次探測(cè)法能夠在一定程度上減少堆積設(shè)H(ki)=6，H(kj)=5，對(duì)于線性探測(cè)法：ki的探測(cè)序列：6,7,8,9,…kj的探測(cè)序列：5,6,7,8,…重合之后再不分開設(shè)H(ki)=6，H(kj)=5，對(duì)于二次探測(cè)法：ki的探測(cè)序列：6,7,5,10,2,…kj的探測(cè)序列：5,6,4,9,1,…重合之后很快分開二次探測(cè)法拉鏈法拉鏈法如何處理沖突？對(duì)于給定的關(guān)鍵碼key執(zhí)行下述操作：（1）計(jì)算散列地址：j=H(key)（2）將key對(duì)應(yīng)的記錄插入到同義詞子表j中；開散列表：用拉鏈法處理沖突得到的散列表。開散列表中存儲(chǔ)同義詞子表的頭指針，開散列表不會(huì)出現(xiàn)堆積現(xiàn)象同義詞子表：所有散列地址相同的記錄構(gòu)成的單鏈表。開散列表會(huì)出現(xiàn)堆積現(xiàn)象嗎？開散列表的類定義constintMaxSize=100;classOpenHashTable{public:OpenHashTable();

~OpenHashTable();

intInsert(intk);

intDelete(intk);

Node<int>*Search(intk);private:

intH();

Node<int>*ht[MaxSize];};OpenHashTable::OpenHashTable(){

for(inti=0;i<MaxSize;i++){

ht[i]=nullptr;

}

}012345678910

∧∧∧∧∧∧∧∧∧∧∧析構(gòu)函數(shù)OpenHashTable::~OpenHashTable(){

Node<int>*p=nullptr,*q=nullptr;

for(inti=0;i<MaxSize;i++)

{

p=q=ht[i];

while(p!=nullptr)

{

p=p->next;

deleteq;

q=p;

}

}}012345678910

∧∧∧∧∧11∧

22

47∧

3

92∧

16∧

7∧

29

8∧插入算法例3設(shè)關(guān)鍵碼集合為{47,7,29,11,16,92,22,8,3}，散列表表長(zhǎng)為11，散列函數(shù)為H(key)=keymod11，用拉鏈法處理沖突，在散列表中插入元素33。012345678910

∧∧∧∧∧11∧

22

47∧

3

92∧

16∧

7∧

29

8∧

p33

qNode<int>*OpenHashTable::Insert(intk){j=H(k);Node<int>*p=ht[j];while(p!=nullptr){if(p->data==k)break;elsep=p->next;}if(p==nullptr){q=newNode<int>;q->data=k;q->next=ht[j];ht[j]=q;}}查找算法012345678910

∧∧∧∧∧11∧

22

47∧

3

92∧

16∧

7∧

29

8∧Node<int>*OpenHashTable::Search(intk){intj=H(k);Node<int>*p=ht[j];while(p!=nullptr){if(p->data==k)returnp;elsep=p->next;}returnnullptr;}

p例4設(shè)散列函數(shù)為H(key)=keymod11，在如下開散列表中，分別給出元素47和14的查找過程。6-4-4散列查找的性能分析v第六章查找技術(shù)衡量方法散列技術(shù)的查找性能取決于什么？產(chǎn)生沖突后，仍然是給定值與關(guān)鍵碼進(jìn)行比較（1）散列函數(shù)是否均勻影響沖突產(chǎn)生的因素有什么？（2）處理沖突的方法例1設(shè)關(guān)鍵碼集合為{47,7,29,11,16,92,22,8,3}，散列表表長(zhǎng)為11，散列函數(shù)為H(key)=keymod11，用線性探測(cè)法和拉鏈法處理沖突，分析查找性能。477291116922922228833012345678910查找成功的平均查找長(zhǎng)度是：(1×5+2×3+4×1)/9=15/9例3設(shè)關(guān)鍵碼集合為{47,7,29,11,16,92,22,8,3}，散列表表長(zhǎng)為11，散列函數(shù)為H(key)=keymod11，用線性探測(cè)法和拉鏈法處理沖突，分析查找性能。012345678910

∧∧∧∧∧11∧

22

47∧

3

92∧

16∧

7∧

29

8∧查找成功的平均查找長(zhǎng)度是：(1×6+2×3)/9=12/9衡量方法產(chǎn)生沖突后，仍然是給定值與關(guān)鍵碼進(jìn)行比較（1）散列函數(shù)是否均勻影響沖突產(chǎn)生的因素有什么？（2）處理沖突的方法散列技術(shù)的查找性能取決于什么？表中填入的記錄數(shù)散列表的長(zhǎng)度

=（3）散列表的裝填因子α查找性能散列表的平均查找長(zhǎng)度是裝填因子α的函數(shù)，而不是查找集合中記錄個(gè)數(shù)n的函數(shù)——O(1)！6-4-5閉散列表和開散列表的比較v第六章查找技術(shù)空間比較閉散列表：開散列表：受數(shù)組空間限制，需要考慮存儲(chǔ)容量沒有記錄個(gè)數(shù)的限制，但子表過長(zhǎng)會(huì)降低查找效率存儲(chǔ)效率較高指針的結(jié)構(gòu)性開銷有堆積現(xiàn)象，降低查找效率不會(huì)產(chǎn)生堆積現(xiàn)象，效率較高僅適用于靜態(tài)查找適用于靜態(tài)查找和動(dòng)態(tài)查找時(shí)間比較閉散列表：開散列表：開散列表的刪除操作例4設(shè)關(guān)鍵碼集合{47,7,29,11,16,92,22,8,3}，散列表表長(zhǎng)為