C++數(shù)據(jù)結(jié)構(gòu)哈希表詳解

第C++數(shù)據(jù)結(jié)構(gòu)哈希表詳解目錄實(shí)現(xiàn)散列函數(shù)開散列方法閉散列方法(開地址方法)刪除*

實(shí)現(xiàn)

哈希表，即散列表，可以快速地存儲(chǔ)和查詢記錄。理想哈希表的存儲(chǔ)和查詢時(shí)間都是O(1)。

本《資料》中哈希表分以下幾部分：散列函數(shù)、存儲(chǔ)和查找時(shí)的元素定位、存儲(chǔ)、查找。刪除操作因?yàn)椴怀Ｓ?，所以只給出思想，不給出代碼。

根據(jù)實(shí)際情況，可選擇不同的散列方法。

以下代碼假設(shè)哈希表不會(huì)溢出。

//N表示哈希表長(zhǎng)度，是一個(gè)素?cái)?shù)，M表示額外空間的大小，empty代表“沒(méi)有元素”。

constintN=9997,M=10000,empty=-1;

inta[N];

voidinit()//初始化哈希表

memset(a,empty,sizeof(a));//注意，只有empty等于0或-1時(shí)才可以這樣做！

memset(bucket,empty,sizeof(bucket));

memset(first,0,sizeof(first));

inlineinth(int);//散列函數(shù)

int*locate(int,bool);//用于存儲(chǔ)和查找的定位函數(shù)，并返回對(duì)應(yīng)位置。

//如果用于存儲(chǔ)，則第二個(gè)參數(shù)為true，否則為false①。

voidsave(intx)//存儲(chǔ)數(shù)據(jù)

int*p=locate(x,true);

if(p!=NULL)*p=x;

boolisexist(intx)//查找數(shù)據(jù)

int*p=locate(x,false);

return(p!=NULL*p==x);

}

散列函數(shù)

為了達(dá)到快速存儲(chǔ)和查找的目的，就必須在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系h。

這個(gè)關(guān)系h叫做哈希函數(shù)。

哈希表存取方便但存儲(chǔ)時(shí)容易沖突：即不同的關(guān)鍵字可以對(duì)應(yīng)同一哈希地址。如何確定哈希函數(shù)和解決沖突是關(guān)鍵。以下是幾種常見(jiàn)的哈希函數(shù)的構(gòu)造方法：

1.取余數(shù)法：h(x)＝x％p（pN，且最好是素?cái)?shù)）

2.直接定址法：h(x)＝x或h(x)＝a*x＋b

3.數(shù)字分析法：取關(guān)鍵字的若干數(shù)位（如中間兩位數(shù)）組成哈希地址。

4.平方取中法：關(guān)鍵字平方后取中間幾位數(shù)組成哈希地址。

5.折疊法：將關(guān)鍵數(shù)字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同）然后取幾部分的疊加和（舍去進(jìn)位）作為哈希地址。

6.偽隨機(jī)數(shù)法：事先產(chǎn)生一個(gè)隨機(jī)數(shù)序列r[]，然后令h(x)＝r[x]。

設(shè)計(jì)哈希函數(shù)時(shí)，要注意

對(duì)關(guān)鍵碼值的分布并不了解希望選擇的散列函數(shù)在關(guān)鍵碼范圍內(nèi)能夠產(chǎn)生一個(gè)大致平均的關(guān)鍵碼值隨機(jī)分布，同時(shí)避免明顯的聚集可能性，如對(duì)關(guān)鍵碼值的高位或低位敏感的散列函數(shù)。

對(duì)關(guān)鍵碼值的分布有所了解應(yīng)該使用一個(gè)依賴于分布的散列函數(shù)，避免把一組相關(guān)的關(guān)鍵碼值映射到散列表的同一個(gè)槽中。

開散列方法

哈希表中難免會(huì)發(fā)生沖突。使用開散列方法可以解決這個(gè)問(wèn)題。常用操作方法是拉鏈法，即相同的地址的關(guān)鍵字值均鏈入對(duì)應(yīng)的鏈表中。

如果散列函數(shù)很差，就容易形成長(zhǎng)長(zhǎng)的鏈表，從而影響查找的效率。

下面是用拉鏈法處理沖突時(shí)的定位函數(shù)：

intsize=-1;

structnode{intv;node*next;}*first[N],mem[M];

#defineNEW(p)p=mem[++size];p-next=NULL

int*locate(intx,boolins=false)

intp=h(x);

if(a[p]==x!ins)returna[p];

//處理沖突

node*q=first[p];

if(ins)

if(q==NULL)

NEW(q);

first[p]=q;

returnq-

while(q-next!=NULL)q=q-next;

node*r;NEW(r);

q-next=r;

returnr-

while(q!=NULL)

if(q-v==x)returnq-

q=q-next;

returnNULL;

}

閉散列方法(開地址方法)

處理沖突的另一種方法是為該關(guān)鍵字的記錄找到另一個(gè)空的哈希地址。在處理中可能得到一個(gè)地址序列g(shù)(i)（i＝1，2，，k；0g(i)n－1)，即在處理沖突時(shí)若得到的另一個(gè)哈希地址g(1)仍發(fā)生沖突，再

求下一地址g(2)，若仍沖突，再求g(3)怎樣得到g(i)呢？

溢出桶法：設(shè)一個(gè)溢出桶，不管得到的哈希地址如何，一旦發(fā)生沖突，都填入溢出桶。

再哈希法：使用另外一種哈希函數(shù)來(lái)定位。

線性探查：g(i)＝(h(x)＋di)%N，其中h(x)為哈希函數(shù)，N為哈希表長(zhǎng)，di為增量序列。

1.線性探測(cè)再散列：di＝1，2，3，，m－1

2.二次探測(cè)再散列：

3.偽隨機(jī)探測(cè)序列：事先產(chǎn)生一個(gè)隨機(jī)數(shù)序列random[]，令di＝random[i]。

下面是用溢出桶處理沖突時(shí)的定位函數(shù)：

intbucket[M],top=-1;//用于閉散列方法（溢出桶）

int*locate(intx,boolins=false)

intp=h(x);

if(a[p]==x!ins)//在查找模式下碰到了所需的元素

returna[p];

elseif(ins)

if(a[p]==empty)//可以插入

returna[p];

else//處理沖突

returnbucket[++top];

else//到溢出桶中尋找元素

for(inti=0;i=top;i++)

if(bucket[i]==x)returnbucket[i];

returnNULL;

}

下面是用線性探查處理沖突的定位函數(shù)，當(dāng)然，它也可以用于再哈希法處理沖突

inlineintg(intp,inti){return(p+i)%N;}//根據(jù)需要來(lái)設(shè)計(jì)

int*locate(intx,boolins=false)

intp=h(x);

intp2,c=0;

if(a[p]==x!ins)

returna[p];

elseif(ins)

p2=g(p,c++);

}while(a[p2]!=empty);

returna[p2];

}else{

p2=g(p,c++);

}while(a[p2]!=xa[p2]!=empty);

if(a[p2]==x)returna[p2];

returnNULL;

}

閉散列方法的優(yōu)點(diǎn)是節(jié)省空間。不過(guò)，無(wú)論是溢出桶，還是線性探查，都會(huì)在尋址過(guò)程中浪費(fèi)時(shí)間。線性

探查的探查序列如果太長(zhǎng)，就會(huì)使一些其他元素被迫散列在其他位置，從而影響了其他元素的查找效率。

刪除*

如果使用開散列方法，那么可以直接刪除元素。然而，使用閉散列方法，是不可以直接刪除元素的。假如

直接刪除，很有可能會(huì)影響其他元素的查找。

在這種情況下，有兩種刪除方法：一種是交換法，另一種是標(biāo)記法。

交換法：在刪除某元素時(shí)，不要立刻把它清除。按照線性探查函數(shù)繼續(xù)尋找，直到?jīng)]有數(shù)值為止。將遇到

的最后一個(gè)數(shù)值與它交換。當(dāng)然，交換之前還要進(jìn)行類似的操作，可謂牽一發(fā)而動(dòng)全