引言集合在線性表和樹表的表示中，元素在結(jié)構(gòu)中的位置與元素的關(guān)鍵字間無直接確定關(guān)系，搜索時需通過關(guān)鍵字的一系列比較完成。本節(jié)的散列表，在元素的關(guān)鍵字與其在結(jié)構(gòu)中的位置建立直接聯(lián)系，以實現(xiàn)直接快速搜索。第8章跳表和散列表

數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE

8.1

字典8.3散列表

8.1字典

字典

是記錄的集合。

有重復(fù)記錄的字典

允許字典中有多個相同關(guān)鍵字值的記錄，在實現(xiàn)搜索、插入和刪除操作時需要一個規(guī)則來消除歧義。

8.3散列表

1.介紹散列技術(shù)

2.討論幾種常用的散列函數(shù)

3.討論幾種解決沖突的方法8.3散列表課堂提要第8章跳表和散列表8.3散列表

8.3.1散列技術(shù)

8.3.2散列函數(shù)

8.3.3拉鏈法

8.3.4開地址法

8.3.5線性探查法

8.3.6其他開地址法

在線性表、二叉排序樹、B-樹中，元素在存儲結(jié)構(gòu)中的位置與元素的關(guān)鍵字值之間不存在直接的確定關(guān)系。搜索時，需進行一系列關(guān)鍵字值間的比較。散列表提供了一種完全不同的存儲和搜索方式：將關(guān)鍵字值映射到表中的某個位置來存儲元素。則通過給定的關(guān)鍵字值，可以直接計算得到元素的存儲位置。8.3.1散列技術(shù)

在元素的存儲位置和關(guān)鍵字值(key)之間建立一種對應(yīng)關(guān)系h，把關(guān)鍵字值映射到表中的某個位置，即：

Loc(key)=h(key)散列函數(shù)：反映元素的關(guān)鍵字(key)與其存儲位置(loc)之間的關(guān)系的函數(shù)h稱為散列函數(shù)。Loc(key)：表示關(guān)鍵字值為key的元素的存儲地址。散列表(hash,哈希表)：用散列函數(shù)建立起來的表。散列表是一種表示集合的數(shù)據(jù)結(jié)構(gòu)。在理想狀態(tài)下，可以不進行任何關(guān)鍵字值的比較，直接通過散列函數(shù)h找到該元素。散列表舉例

建立31個省、自治區(qū)、直轄市的人口統(tǒng)計表。散列表：V[0..30]關(guān)鍵字：名稱的漢語拼音編碼：A-Z

01-26兩種h:h1(key)=第一個字母的編碼h2(key)=第一個字母的編碼+最后一個字母的編碼,若和大于30,則減去30keyBEIJINGJIANGSUSHANGHAISICHUANJIANGXITIANJINSHANXIh1(key) 0210 1919102019h2(key)09012803190428

所有關(guān)鍵字都能映射到V[0..30]中。

…

…

…012…

…

…散列表keyBEIJINGJIANGSUSHANGHAISICHUANJIANGXITIANJINSHANXIh1(key) 0210 1919102019h2(key)09012803190428

問題一：對H1:JIANGSHU與JIANGXI等被映射到相同位置對H2:SHANGHAI與SHANXI等被映射到相同位置產(chǎn)生沖突沖突：key1≠key2,但h(key1)=h(key2)的現(xiàn)象。同義詞：對同一散列函數(shù)，具有相同h值的關(guān)鍵字。上式中key1和key2即為同義詞。h2(key)沖突少于h1(key)問題二：能否避免沖突？不現(xiàn)實如上例：設(shè)計H(key)=各字母編碼序列使key

H(key)（山西，陜西除外）H(SHANXI)=190801142409但是，關(guān)鍵字變化范圍廣泛，比地址集合大得多，地址空間有限V(0..30)，而且找一一對應(yīng)的h很耗費時間，故一般不這樣做。分析上表：h2(key)沖突少于h1(key)，說明沖突與散列函數(shù)有關(guān)。散列函數(shù)是一個壓縮映象，沖突不可避免！可以做到的是：1、選擇“好”的h,盡量減少沖突。2、若發(fā)生沖突，如何處理？用沖突處理技術(shù)。課堂提要第8章跳表和散列表8.3散列表

8.3.1散列技術(shù)

8.3.2散列函數(shù)

8.3.3拉鏈法

8.3.4開地址法

8.3.5線性探查法

8.3.6其他開地址法8.3.2散列函數(shù)“好”的散列函數(shù)：

(1)均分布，少沖突；

(2)計算簡便，快速。均分布：元素經(jīng)散列函數(shù)映象到散列表中的任何位置是等概率的。下面介紹幾種目前比較通用的散列函數(shù)。

h(key)=keymodM(M為散列表表長)

一般取不超過M的素數(shù)P會更好。例：M=1000,P=997

關(guān)鍵字內(nèi)部編碼散列地址

KEYA11052501756KEYB11052502757AKEY01110502864BKEY02110502873

散列地址相近，可以先將關(guān)鍵字的內(nèi)部編碼循環(huán)移若干位后，再%。1、除留余數(shù)法

h(key)=(key)2的中間若干位k

其中：位數(shù)k應(yīng)滿足：10k-1＜n≤10k

，n為集合中元素個數(shù)。例：n=765,k取3。

103-1<765103,故k=3,即取k=3。

關(guān)鍵字(內(nèi)部編碼）2

散列地址

KEYA122157778355001778KEYB122157800460004800AKEY001233265775625265BKEY0044543157756253152、平方取中法把關(guān)鍵字值自左到右，分成位數(shù)相等的幾部分，每一部分位數(shù)與散列表地址的位數(shù)相同，只有最后一部分的位數(shù)可以短些。把這些部分的數(shù)據(jù)疊加起來，得到該關(guān)鍵字的散列地址。（1）移位法：把各部分最后以為對齊相加（2）分界法：沿各部分的分界來回折疊，然后對齊相加3、折疊法例：設(shè)關(guān)鍵字key=12320324111220，散列地址取3位，則key被劃分位5段：

12320324111220123203241112＋20699(a)移位法123302241211＋20897(b)分界法適用于關(guān)鍵字很長的情況取分布均勻的若干位。例如，一組關(guān)鍵字如下：位123

456

關(guān)鍵字942148

942356942572942664943395942472942731941287942345

通過分析，可以看出第4、5、6位分布均勻，故取第4、5、6位這三位為散列函數(shù)的值。4、數(shù)字分析法

沖突是不可避免的。當沖突發(fā)生時，必須對沖突進行處理。

處理沖突的方法有：

（1）拉鏈法（2）線性探查法（3）二次探查法（4）雙散列法課堂提要第8章跳表和散列表8.3散列表

8.3.1散列技術(shù)

8.3.2散列函數(shù)

8.3.3拉鏈法

8.3.4開地址法

8.3.5線性探查法

8.3.6其他開地址法

將所有具有同義詞的關(guān)鍵字建立一個單鏈表，單鏈表可以按升序排列。所有單鏈表的頭指針存入一數(shù)組中。

01

2

34

5113616335566694982

散列函數(shù)采用除留余數(shù)法，除數(shù)取11。H(key)=key%11有n個元素的散列表，其每個單鏈表的平均長度為n/M。8.3.3拉鏈法插入228.3.4開地址法對散列表插入新元素的方法：從h(key)開始，按照某種規(guī)定的次序探查允許插入新元素的空位置。基位置：h(key)探查序列：如果h(key)已經(jīng)被占用，需要有一種解決沖突的策略來確定如何探查下一個空位置。不同的解決沖突的策略，可產(chǎn)生不同的需要被檢查的位置的序列，稱為探查序列。S根據(jù)生成探查序列的規(guī)則的不同，開地址法有：1、線性探查法2、二次探查法3、雙散列法線性探查法使用以下循環(huán)探測序列進行探測：

h(key),h(key)+1,h(key)+2

…,M-1,0,1,…,h(key)-1

插入新元素時，從h(key)開始探測，若被占用，檢查h(key)+1，若也占用，再檢查探測序列中的下個位置h(key)+2，…

，直到某個位置為空時，將關(guān)鍵字插入該位置。012345678910804065ht插入58，24。012345678910804065ht2458插入35。012345678910804065ht2458351、線性探查法上例中，散列函數(shù)用除留余數(shù)法，除數(shù)取11，H(key)=key%11

線性探查散列表的搜索012345678910804065ht245835散列函數(shù)H(key)=key%11搜索35搜索成功：按照線性循環(huán)探查序列找到為key的元素搜索25搜索失敗：按照線性循環(huán)探查序列遇到空位置012345678910804065ht24583510986搜索25搜索失?。喊凑站€性循環(huán)探查序列搜索一遍，回到h(key)（表滿）

線性探查散列表的搜索基本思想：從基位置h(key)開始,按照線性循環(huán)探查序列查找該元素。搜索成功：找到關(guān)鍵字值為key的元素；搜索失?。?、遇到一個空位置

2、回到h(key)（表滿）

線性探查散列表的刪除散列表中刪除元素的過程刪除58：58804065012345678910ht2435若直接刪除，后果是什么？例如：搜索35遇到空位置，搜索失??！如何解決？

線性探查散列表的刪除刪除時需考慮兩點：1、不能簡單清除元素，否則會隔離探查序列后面的元素，影響搜索；2、刪除后，該元素的位置能夠重新使用。課堂提要第8章跳表和散列表8.3散列表

8.3.1散列技術(shù)

8.3.2散列函數(shù)

8.3.3拉鏈法

8.3.4開地址法

8.3.5線性探查法

8.3.6其他開地址法解決的辦法：1.為每個元素增加標志域2.刪除58時，不改變標志位，仍為false，元素處改為NeverUsed。刪除元素的方法：1.首先搜索該元素2.若搜索成功，則置該位置為空值NeverUsed

，但empty域不作更改！804065012345678910ht24NU35emptyFFFFFFTTTTTNUNUNUNUNU58

線性探查散列表的搜索改進算法：從基位置h(key)開始,按照線性循環(huán)探查序列查找該元素。搜索成功：找到關(guān)鍵字值為key的元素；搜索失?。?、遇到一個空位置（empty[i]=true）

2、回到h(key)（表滿）

804065012345678910ht24NU35emptyFFFFFFTTTTTNUNUNUNUNU搜索35，25

線性開地址法散列表的C++類Template<classE,classK>classHashTable:DynamicSet<T>{public:

HashTable(intdivisor=11);

~HashTable(){delete[]ht;delete[]empty;}

ResultCode

Search(T&x)const;

ResultCode

Insert(T&x);

ResultCode

Remover(T&x);private:

ResultCode

Find(T&x,int&pos)const;

intM;//散列表長

T*ht;//散列表

bool*empty;//標志域}

線性開地址法散列表的構(gòu)造函數(shù)template<classT>HashTable<T>::HashTable(int

divitor){M=divitor;ht=newT[M];empty=newbool[M];

inti;for(i=0;i<M;i++)empty[i]=true;//標志位空

for(i=0;i<M;i++)ht[i]=NeverUsed;//空值}

線性探查散列表的搜索改進算法：從基位置h(key)開始,按照線性循環(huán)探查序列查找該元素。搜索成功：找到關(guān)鍵字值為key的元素；搜索失?。?、遇到一個空位置（empty[i]=true）2、回到h(key)（表滿）

804065012345678910ht24NU35emptyFFFFFFTTTTTNUNUNUNUNU搜索35，25template<classT>ResultCode

HashTable<T>::Search(T&x)const{

intpos;

if(Find(x,pos)==Success)returnSuccess;returnNotPresent;}template<classT>ResultCode

HashTable<T>::Find(T&x,int&pos)const{pos=h(x);

inti=pos,j=-1;do{

if(ht[pos]==NeverUsed&&j==-1)j=pos;//記錄首次遇到NeverUsed的位置

if(empty[pos])break;//若empty[pos]的值為true,搜索失敗

if(ht[pos]==x){x=ht[pos];returnSuccess;//搜索成功,返回主調(diào)函數(shù)

}pos=(pos+1)%M;}while(pos!=i);

if(j==-1)returnOverflow;//若j為-1，說明沒遇到空值，表已滿

pos=j;returnNotPresent;//將首次遇到的空值位置通過pos返回

}804065012345678910ht24NU35emptyFFFFFFTTTTTNUNUNUNUNU解決的辦法：1.為每個元素增加標志域2.刪除58時，不改變標志位，仍為false，元素處改為NeverUsed。刪除元素的方法：1.首先搜索該元素2.若搜索成功，則置該位置為空值NeverUsed

，但empty域不作更改！804065012345678910ht24NU35emptyFFFFFFTTTTTNUNUNUNUNU58程序8.10線性探查散列表的刪除template<classT>ResultCode

HashTable<T>::Remove(T&x){

intpos;

if(Find(x,pos)==Success)//搜索

{

ht[pos]=NeverUsed;//設(shè)為空值

returnSuccess;}returnNotPresent;}線性開地址法散列表的插入

函數(shù)探查第一個空值NeverUsed的位置，插入新元素。例如：插入2函數(shù)Insert首先調(diào)用Find函數(shù)，若函數(shù)返回值為存在重復(fù)元素或表已滿，則插入失敗。若返回值為NotPresent

則在第一個空值位置插入元素e，插入成功。804065012345678910ht24NU35emptyFFFFFFTTTTTNUNUNUNUNU程序8.9線性探查散列表的插入template<classT>ResultCode

HashTable<T>::Insert(T&x){

intpos;

ResultCoderesult=Find(x,pos);

if(result==NotPresent)//如果表未滿且不包含重復(fù)元素

{//將新元素插入第一個空值處

ht[pos]=x;

empty[pos]=false;returnSuccess;}

if(result==Success)returnDuplicate;//存在重復(fù)元素

returnOverflow;//表滿}8.3.6其他開地址法58804065012345678910ht2435線性探查法的缺點：易使元素在表中連成一片，使得探查次數(shù)增加，影響搜索效率——基本聚焦改進方法：1、二次探查法

2、雙散列法課堂提要第8章跳表和散列表8.3散列表

8.3.1散列技術(shù)

8.3.2散列函數(shù)

8.3.3拉鏈法

8.3.4開地址法

8.3.5線性探查法

8.3.6其他開地址法1、二次探查法二次探測法使用下列探測序列進行探測，直到某個位置為空時，將關(guān)鍵字為key的元素插入該位置。探查序列為：

h(key),h1(key),h2(key),…,h2i-1(key),h2i(key),…。探測序列由下列函數(shù)得到：

h2i-1(key)=(h(key)+i2)%Mh2i(key)=(h(key)-i2)%Mi=1,2,…,(M-1)/2M是表長，應(yīng)該是4k+3的素數(shù)，k是一整數(shù)。

i=1，h1(key)=(h(key)+12)%Mh2(key)=(h(key)-12)%Mi=2,h3(key)=(h(key)+22)