第十章散列結(jié)構(gòu)

1算法與數(shù)據(jù)結(jié)構(gòu)枚舉向量，這種向量中使用的下標(biāo)不是整數(shù)，而是某枚舉類型的實(shí)例。

對(duì)枚舉向量，查詢的出發(fā)點(diǎn)是一個(gè)枚舉值，要做就是由這個(gè)枚舉值出發(fā)，確定有關(guān)數(shù)據(jù)元素的存儲(chǔ)位置。2算法與數(shù)據(jù)結(jié)構(gòu)作為查詢出發(fā)點(diǎn)的值可能有各種不同情況，需要進(jìn)一步研究有關(guān)的技術(shù)和方法。

在集合與字典的一章里，已經(jīng)討論了一些結(jié)構(gòu)和技術(shù)，那里使用的根本技術(shù)是關(guān)鍵碼比較。3算法與數(shù)據(jù)結(jié)構(gòu)散列結(jié)構(gòu)與枚舉向量有類似之處：這里采用的根本存儲(chǔ)結(jié)構(gòu)也是一個(gè)向量，要做的也是從關(guān)鍵碼出發(fā)，直接確定數(shù)據(jù)元素的存儲(chǔ)位置。但是散列結(jié)構(gòu)更具一般性，原那么上說(shuō)它允許任意種類的關(guān)鍵碼。4算法與數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)良好的散列結(jié)構(gòu)可以具有非常高的操作效率，因此這種結(jié)構(gòu)在計(jì)算機(jī)領(lǐng)域中應(yīng)用廣泛，是一種非常有效的存儲(chǔ)和查詢結(jié)構(gòu)。

5算法與數(shù)據(jù)結(jié)構(gòu)下面將首先介紹散列結(jié)構(gòu)的根本思想，然后重點(diǎn)討論散列結(jié)構(gòu)實(shí)現(xiàn)的兩個(gè)根本要素：散列函數(shù)和“碰撞〞的各種解決技術(shù)。本章的后面局部把散列結(jié)構(gòu)作為集合和字典的重要實(shí)現(xiàn)技術(shù)，討論這些方面的有關(guān)問(wèn)題。

6算法與數(shù)據(jù)結(jié)構(gòu)10.1根本概念7算法與數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)方式和檢索方法：

散列函數(shù)

關(guān)鍵碼——>——>地址(固定，連續(xù)空間)8算法與數(shù)據(jù)結(jié)構(gòu)“散列〞一詞的意思是進(jìn)行某種隨機(jī)的混合，有的中文教科書(shū)或文獻(xiàn)中把它稱為“雜湊〞，對(duì)應(yīng)的英文詞是一樣的——hash。

9算法與數(shù)據(jù)結(jié)構(gòu)

散列函數(shù)是一種數(shù)據(jù)轉(zhuǎn)換函數(shù)，它的參數(shù)應(yīng)該是某種查詢的依據(jù)，一般稱為“關(guān)鍵詞〞或“關(guān)鍵碼〞，而函數(shù)返回的是一個(gè)無(wú)符號(hào)整數(shù)值，作為確定下標(biāo)的依據(jù)。

散列的根本想法就是構(gòu)造一個(gè)對(duì)應(yīng)關(guān)系，把每個(gè)關(guān)鍵碼對(duì)應(yīng)到一個(gè)整數(shù)〔存儲(chǔ)位置〕。這樣，如果需要存儲(chǔ)與某個(gè)關(guān)鍵碼相關(guān)的數(shù)據(jù)，就將它存到與關(guān)鍵碼對(duì)應(yīng)的存儲(chǔ)位置里去；如果需要查詢與某個(gè)關(guān)鍵碼有關(guān)的信息，就到與這個(gè)關(guān)鍵碼對(duì)應(yīng)的位置中去找。

10算法與數(shù)據(jù)結(jié)構(gòu)“散列〞〔hash〕一詞的意思是進(jìn)行某種混合性的變換，從關(guān)鍵碼本身看，這種變換可能并沒(méi)有很清楚的具體意義。散列這個(gè)詞在有些中文教科書(shū)或文獻(xiàn)中被譯為“雜湊〞，散列結(jié)構(gòu)也被稱為“散列表〞、“雜湊表〞，或者按照音譯稱為“哈希表〞等。11算法與數(shù)據(jù)結(jié)構(gòu)根據(jù)散列函數(shù)概念，可以定義一種新向量類，叫作simpleHashVector類〔簡(jiǎn)單散列向量類〕。這里把它定義為向量類Vector的一個(gè)子類。簡(jiǎn)單散列向量比普通向量多一個(gè)數(shù)據(jù)成分，那就是一個(gè)指向散列函數(shù)的指針hashfun。對(duì)具體的簡(jiǎn)單散列向量而言，這個(gè)數(shù)據(jù)成分是在構(gòu)造時(shí)建立，是一種不能改變的性質(zhì)。12算法與數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單散列向量類有兩個(gè)類型參數(shù)，一個(gè)是向量的索引〔關(guān)鍵碼〕類型H，另一個(gè)是向量元素類型T。

13算法與數(shù)據(jù)結(jié)構(gòu)template<classH,classT>classsimpleHashVector:publicvector<T>

{

public:

//構(gòu)造函數(shù)

simpleHashVector(intmax,int(f)(constH&));

simpleHashVector(intmax,int(f)(constH&),T&initialValue);

simpleHashVector(constsimpleHashVector<H,T>&v);

//下標(biāo)操作

T&operator[](constH&index);

private:

//記錄散列函數(shù)的函數(shù)指針

constint(hashfun)(constH&);[qzy1]

};

類10.1simpleHashVector類標(biāo)準(zhǔn)說(shuō)明

14算法與數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單散列向量類的定義與枚舉向量有相似的地方，例如對(duì)它們都可以用字符序列形式的向量下標(biāo)直接存取相關(guān)元素。15算法與數(shù)據(jù)結(jié)構(gòu)但是對(duì)于枚舉向量，作為下標(biāo)的字符序列必須是某個(gè)枚舉類型的值，下標(biāo)操作的實(shí)現(xiàn)是由系統(tǒng)自動(dòng)將枚舉值轉(zhuǎn)換成內(nèi)部整數(shù)值。而對(duì)于簡(jiǎn)單散列向量，那么可以使用真正的字符串，這種字符串可以送去打印等。16算法與數(shù)據(jù)結(jié)構(gòu)在查詢?cè)匚恢脮r(shí)，散列結(jié)構(gòu)首先用給定的散列函數(shù)，把H類型的關(guān)鍵碼〔可以看作是一種廣義“下標(biāo)〞〕轉(zhuǎn)換成一個(gè)適當(dāng)?shù)恼麛?shù)值，然后再把該整數(shù)轉(zhuǎn)換成對(duì)于向量合法的下標(biāo)值。后一轉(zhuǎn)換一般直接采用按向量大小取余數(shù)的方式。

17算法與數(shù)據(jù)結(jié)構(gòu)template<classH,classT>T&

hashVector<H,T>::operator[](constH&index)

{

returnvector<T>::operator[]((

hashfun)(index)%size);

}

簡(jiǎn)單散列向量類的其他成員函數(shù)都非常簡(jiǎn)單。讀者不難自己實(shí)現(xiàn)它們。

10.2散

列

函

數(shù)

18算法與數(shù)據(jù)結(jié)構(gòu)理想的散列函數(shù)是個(gè)一對(duì)一映射，它能把有關(guān)的一組關(guān)鍵碼映射到連續(xù)的一組整數(shù)值，每個(gè)關(guān)鍵碼對(duì)應(yīng)一個(gè)整數(shù)值，反之依然。19算法與數(shù)據(jù)結(jié)構(gòu)假設(shè)用h(x)代表散列函數(shù)，一般來(lái)說(shuō)，h應(yīng)該滿足三個(gè)條件：

h的定義域是全體可能出現(xiàn)的關(guān)鍵碼的集合，h的值域是散列表空間位置(向量下標(biāo))的集合；

希望函數(shù)值分布對(duì)于散列空間位置而言要盡量均勻；

h函數(shù)應(yīng)該是足夠簡(jiǎn)單的。

20算法與數(shù)據(jù)結(jié)構(gòu)對(duì)一般類型的關(guān)鍵碼，運(yùn)用散列函數(shù)的過(guò)程通常分成兩步：

第一步是將關(guān)鍵碼轉(zhuǎn)化成適當(dāng)?shù)恼麛?shù)值；

第二步是將得到的整數(shù)轉(zhuǎn)化為散列向量的合法下標(biāo)。

21算法與數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)第一步有很多種方法，下面列舉常見(jiàn)的幾種。

1)映射：將關(guān)鍵碼以某種數(shù)值方式映射成整數(shù)值。

對(duì)于比較復(fù)雜的映射，一般可用一個(gè)映射數(shù)組來(lái)定義。數(shù)組中的元素都在程序編制前預(yù)先給出。程序執(zhí)行時(shí)，求散列值信息就是在映射數(shù)組中找到該元素，對(duì)于一組確定的關(guān)鍵碼來(lái)說(shuō)，這是產(chǎn)生一個(gè)理想的散列函數(shù)的根本方法。

22算法與數(shù)據(jù)結(jié)構(gòu)2)折疊：先把關(guān)鍵碼分割成小塊，各局部的值必要時(shí)可以先散列處理，然后再混合起來(lái)便形成整個(gè)關(guān)鍵碼的散列值。

混合又有多種不同的方法，如加法、乘法或邏輯運(yùn)算。

23算法與數(shù)據(jù)結(jié)構(gòu)下面的小程序段實(shí)現(xiàn)了一種把字符串str變成整數(shù)值的過(guò)程，所用的方法便是將所有字母值加起來(lái)。

unsignedinthashval=0;

inti=str.length();

while(i>0)

hashval+=str[

i];

24算法與數(shù)據(jù)結(jié)構(gòu)3)移位：移位可以防止在折疊處理中由于運(yùn)算的可交換帶來(lái)的碰撞。

如上段程序便對(duì)apt、tap、pat會(huì)產(chǎn)生相同的散列值，而使用移位便可能減少這些碰撞。下面是參加移位處理后的程序段：

25算法與數(shù)據(jù)結(jié)構(gòu)unsignedinthashval=0;

inti=str.length();

while(i>0)

hashval=(hashval<<1)+str[

1];

26算法與數(shù)據(jù)結(jié)構(gòu)4)數(shù)字分析法：常常有這樣的情況：關(guān)鍵碼的位數(shù)比存儲(chǔ)區(qū)域的地址碼的位數(shù)多，同時(shí)其中各位的出現(xiàn)不是隨機(jī)的，在這種情況下可以通過(guò)事先對(duì)關(guān)鍵碼的各位情況進(jìn)行分析，散列時(shí)丟掉分布不均勻的位，留下分布均勻的位。

27算法與數(shù)據(jù)結(jié)構(gòu)例如，需要對(duì)以下關(guān)鍵碼集合進(jìn)行轉(zhuǎn)換，實(shí)際關(guān)鍵碼有9位數(shù)字，經(jīng)過(guò)數(shù)字分析法可以丟掉6位。

keyh(key)

000319426326

000718309709

000629443643

000758615715

000910497997

000310329329

28算法與數(shù)據(jù)結(jié)構(gòu)這個(gè)方法的缺點(diǎn)是散列函數(shù)依賴于關(guān)鍵碼集合，具體到這6個(gè)關(guān)鍵碼值，經(jīng)過(guò)分析留下第4、8、9位，假設(shè)換一個(gè)關(guān)鍵碼集合，就要重新分析，也許留下第3、6、7位。通過(guò)比照較大的實(shí)例集合進(jìn)行分析，就可能得到比較合理的結(jié)果。

29算法與數(shù)據(jù)結(jié)構(gòu)散列函數(shù)的第二步工作是將已得到的整數(shù)值轉(zhuǎn)化成散列表的合法下標(biāo)值，這時(shí)采用最多的是除余法。

所謂除余法，就是選擇一個(gè)恰當(dāng)?shù)恼麛?shù)B，用B去除前一步驟得到的整數(shù)，取其余數(shù)作為散列表的下標(biāo)值。

30算法與數(shù)據(jù)結(jié)構(gòu)這個(gè)方法的關(guān)鍵是選取恰當(dāng)?shù)腂。如果B選為一個(gè)偶數(shù)，那么它將總是把奇整數(shù)值轉(zhuǎn)換到奇數(shù)的下標(biāo)，把偶整數(shù)值轉(zhuǎn)換到偶數(shù)的下標(biāo)，這當(dāng)然不太好。選B為10的冪次就更不好，因?yàn)槟菢泳偷扔谶x擇整數(shù)的最后幾位數(shù)字作為地址。例如，選B=100，那么實(shí)際上就是取整數(shù)的最后兩位作為地址。

31算法與數(shù)據(jù)結(jié)構(gòu)在實(shí)際工作中一般認(rèn)為選取B為適當(dāng)?shù)乃財(cái)?shù)為好。例如：

B=7，13，31，61，127，251，503，1019

32算法與數(shù)據(jù)結(jié)構(gòu)除余法的地址計(jì)算公式簡(jiǎn)單。然而實(shí)踐證明，恰恰是這種簡(jiǎn)單的方法在許多情況下效果比較好。需要注意的是B的選擇，也就是散列表中桶的個(gè)數(shù)確實(shí)定，因?yàn)橛贸喾ㄋ?jì)算的結(jié)果一定在0~B-1的范圍之中。

33算法與數(shù)據(jù)結(jié)構(gòu)

同義詞

負(fù)載因子

碰撞〔開(kāi)地址，桶〕

34算法與數(shù)據(jù)結(jié)構(gòu)兩個(gè)關(guān)鍵碼散列成相同的值的現(xiàn)象被稱為“碰撞〞。碰撞的產(chǎn)生使散列的使用產(chǎn)生了問(wèn)題。

35算法與數(shù)據(jù)結(jié)構(gòu)下面我們先引入“同義詞〞的概念。設(shè)有關(guān)鍵碼k1和k2，經(jīng)過(guò)散列函數(shù)f的作用，把它們映射成相同的值，即f(k1)=f(k2)，稱k1和k2在函數(shù)f的解釋下含義相同，簡(jiǎn)稱為“同義詞〞。顯然同義詞越多，碰撞的可能性就越大。

36算法與數(shù)據(jù)結(jié)構(gòu)

另外一個(gè)重要概念是“負(fù)載因子〞。簡(jiǎn)單地講，一種結(jié)構(gòu)的負(fù)載因子可以定義為這個(gè)結(jié)構(gòu)中實(shí)際元素的個(gè)數(shù)與能夠容納的元素個(gè)數(shù)之比。即：

=結(jié)構(gòu)中實(shí)際元素的個(gè)數(shù)/結(jié)構(gòu)中能夠容納的元素個(gè)數(shù)

37算法與數(shù)據(jù)結(jié)構(gòu)

10.3開(kāi)地址散列向量

38算法與數(shù)據(jù)結(jié)構(gòu)為了解決碰撞，人們提出了許多方法，本節(jié)先介紹其中的一種，稱為“開(kāi)地址法〞。用這種方法建立的散列結(jié)構(gòu)稱為“開(kāi)地址散列向量〞。

39算法與數(shù)據(jù)結(jié)構(gòu)類10.2給出openHashVector的標(biāo)準(zhǔn)說(shuō)明。為了表達(dá)簡(jiǎn)單，我們假設(shè)向量中每個(gè)元素都只包含關(guān)鍵碼自身，元素類型就是關(guān)鍵碼類型。這時(shí)模板類的參數(shù)只需要一個(gè)元素類型T〔也是關(guān)鍵碼類型〕；進(jìn)一步還假設(shè)對(duì)T類型有一個(gè)特定值，這個(gè)值不表示任何真正有意義的關(guān)鍵碼。因此，如果向量中某元素取這個(gè)值，就說(shuō)明該元素處于空閑狀態(tài)。40算法與數(shù)據(jù)結(jié)構(gòu)

template<classT>classopenHashVector

{

public:

//構(gòu)造函數(shù)

openHashVector(intmax,int(f)(constT&),T&value);

openHashVector(constopenHashVector<T>&);

//操作

intadd(constT&);

intincludes(T&);

voidremove(constT&);

private:

//數(shù)據(jù)域：散列函數(shù)，基向量和向量長(zhǎng)度及初值

constint(hashfun)(constT&);

vector<T>data;

intsize;

constTspareValue;

};

類10.2openHashVector類標(biāo)準(zhǔn)說(shuō)明

41算法與數(shù)據(jù)結(jié)構(gòu)

template<classT>

openHashVector<T>::openHashVector(intmax,int(

f)(constT&),T&value)

:hashfun(f),data(max),spareValue(value)

{//設(shè)置向量大小

size=data.length();

for(unsignedi=0;i<size;i++)

data[i]=spareValue;

}

42算法與數(shù)據(jù)結(jié)構(gòu)

template<classT>intopenHashVector<T>::add(constT&v)

{//把一個(gè)確定數(shù)據(jù)記錄存放到開(kāi)地址散列向量

unsignedstart=(

hashfun)(v)%size,index=start;

//檢查位置是否已被占用

while(data[index]!=spareValue)

{

index=(index+1)%size;//考察下一個(gè)位置

if(index==start)return0;

}

data[index]=v;//發(fā)現(xiàn)空位，插入新元素

return1;

}

43算法與數(shù)據(jù)結(jié)構(gòu)

template<classT>intopenHashVector<T>::includes(T&value)

{

unsignedstart=(

hashfun)(value)%size;

unsignedindex=start;

TcurValue=data[index];

while(curValue!=value)//未找到對(duì)應(yīng)值就繼續(xù)循環(huán)

{

if(curValue==spareValue)return0;

index=(index+1)%size;

if(index==start)return0;

curValue=data[index];

}

return1;

}

44算法與數(shù)據(jù)結(jié)構(gòu)開(kāi)地址散列的思想很簡(jiǎn)單，但是它的碰撞處理方式也有些缺點(diǎn)。如果碰撞經(jīng)常發(fā)生，插入和查找的時(shí)間代價(jià)就要增加，特別是在向量中增加同義詞的時(shí)候，可能使原來(lái)并不是同義詞的關(guān)鍵碼也被牽連進(jìn)來(lái)〔這種現(xiàn)象也被稱為“堆積〞〕，進(jìn)一步增加了查找的時(shí)間。45算法與數(shù)據(jù)結(jié)構(gòu)還有另外一點(diǎn)，在開(kāi)地址散列向量中的做刪除時(shí)要特別謹(jǐn)慎，如果簡(jiǎn)單地把被刪除向量元素置成初始值，結(jié)果就可能導(dǎo)致某些原有同義詞信息的喪失。這里面的具體原因和解決方法請(qǐng)讀者自己考慮。

46算法與數(shù)據(jù)結(jié)構(gòu)10.4桶散列——用桶解決碰撞

本節(jié)介紹碰撞的另一種處理方法。如果把散列表的元素?cái)U(kuò)充定義為一個(gè)能存放多個(gè)數(shù)據(jù)元素的結(jié)構(gòu)，用這種結(jié)構(gòu)存放同義詞，能夠大大增強(qiáng)散列結(jié)構(gòu)處理碰撞的能力。人們把這種存放同義詞的結(jié)構(gòu)稱為“存儲(chǔ)桶〞，或簡(jiǎn)稱“桶〞。47算法與數(shù)據(jù)結(jié)構(gòu)采用桶方式實(shí)現(xiàn)散列結(jié)構(gòu)，向結(jié)構(gòu)里參加一個(gè)元素的動(dòng)作就需要分兩步走：首先在散列向量中選擇應(yīng)該放入元素的桶，然后再向這個(gè)桶做元素插入。尋找和刪除元素的操作過(guò)程與插入類似。由于每個(gè)桶可以容納多個(gè)元素，碰撞問(wèn)題自然就解決了。我們把以這種方式實(shí)現(xiàn)的散列結(jié)構(gòu)稱為桶散列結(jié)構(gòu)或桶散列表。

48算法與數(shù)據(jù)結(jié)構(gòu)桶散列的抽象模板類

抽象的桶散列模板類bucketHashVector帶有三個(gè)類型參數(shù)：類B是桶的實(shí)現(xiàn)類型，其實(shí)現(xiàn)細(xì)節(jié)方面的情況后面討論；類H是元素的關(guān)鍵碼類型，它也是散列函數(shù)處理的對(duì)象類型；類T是桶散列表中元素的類型。49算法與數(shù)據(jù)結(jié)構(gòu)template<classB,classH,classT>classbucketHashVector

{

public:

//構(gòu)造函數(shù)

bucketHashVector(unsignedintmax,unsignedint(f)(constH&));

virtualintisEmpty();//判斷是否為空散列表

virtualvoiddeleteAllValues();//刪除散列表里所有元素

protected:

friendclassbucketHashVectorIterator<B,H,T>;

constunsignedinttablesize;//散列表里桶個(gè)數(shù)

vector<B>buckets;//散列表用一個(gè)以桶為元素的向量

constunsignedint(hashfun)(constH&);//散列函數(shù)指針

unsignedinthash(constH&key)const;//實(shí)際使用的散列函數(shù)

//建立指定桶的遍歷器

virtualiterator<T>makeIterator(unsignedint)=0;

};

類10.3bucketHashVector類的標(biāo)準(zhǔn)說(shuō)明

50算法與數(shù)據(jù)結(jié)構(gòu)bucketHashVector類的對(duì)象有三個(gè)數(shù)據(jù)域：buckets是桶類型的向量，各個(gè)桶里存放散列表元素；整數(shù)tablesize是桶向量的元素個(gè)數(shù)(桶的個(gè)數(shù))，由于桶的數(shù)目與散列函數(shù)直接相關(guān)，這里采用確定之后就不能再修改的方式，把它說(shuō)明為一個(gè)整型常量；hashfun是散列函數(shù)指針，在散列表定義時(shí)設(shè)定到選定的散列函數(shù)。這個(gè)散列函數(shù)以H類型的關(guān)鍵碼作參數(shù)，計(jì)算出一個(gè)無(wú)符號(hào)的整數(shù)結(jié)果。

51算法與數(shù)據(jù)結(jié)構(gòu)在bucketHashVector類里只定義了兩個(gè)公用操作：一個(gè)操作測(cè)試散列表是否為空，另一個(gè)操作完成所有桶的去除工作，其他操作都必須在這個(gè)類的子類里定義。

上面兩個(gè)公有函數(shù)都需要遍歷所有的桶。要?jiǎng)h除散列表里所有的項(xiàng)，必須去除每個(gè)桶的所有元素。

52算法與數(shù)據(jù)結(jié)構(gòu)template<classB,classH,classT>

voidbucketHashVector<B,H,T>::deleteAllValues()

{

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

buckets[i].deleteAllValues();

}

53算法與數(shù)據(jù)結(jié)構(gòu)類似的，檢查一個(gè)散列表里是否有元素就必須檢測(cè)每個(gè)桶的情況。在這些桶都為空的時(shí)候，才能說(shuō)散列表是空的。

template<classB,classH,classT>intbucketHashVector<B,H,T>::isEmpty()

{//如果任一個(gè)筒非空就返回0值

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

if(!buckeds[i].isEmpty())return0;

return1;//全都為空，散列表空

}

54算法與數(shù)據(jù)結(jié)構(gòu)函數(shù)hash定義了對(duì)關(guān)鍵碼的散列值計(jì)算。由于該函數(shù)不改變散列表本身，所以被說(shuō)明為const。函數(shù)hash通過(guò)函數(shù)指針hashfun調(diào)用桶散列表建立時(shí)設(shè)定的根本散列函數(shù)，并把散列值歸入0與tablezise-1之間。函數(shù)hash在類的保護(hù)局部中說(shuō)明，在bucketHashVector的子類和友元類里都可以直接調(diào)用它。

55算法與數(shù)據(jù)結(jié)構(gòu)template<classB,classH,calssT>

unsignedintbucketHashVector<B,H,T>::hash(constH&key)const

{//返回關(guān)鍵字的散列值

return(

hashfun)(key)%tablesize;

}

56算法與數(shù)據(jù)結(jié)構(gòu)在bucketHashVector的保護(hù)局部還定義了一個(gè)名為makeIterator的純虛函數(shù)，其參數(shù)是一個(gè)整數(shù)。這個(gè)函數(shù)的作用是根據(jù)參數(shù)值生成指定的桶遍歷器。由于桶類型B是模板參數(shù)，所以函數(shù)的實(shí)現(xiàn)目前無(wú)法具體給出。所有bucketHashVector的子類都必須重新定義這個(gè)函數(shù)。例如下面的子類hashTree定義時(shí)就給出了它的重新定義。

57算法與數(shù)據(jù)結(jié)構(gòu)用樹(shù)作為桶的實(shí)現(xiàn)

要使用桶散列數(shù)據(jù)結(jié)構(gòu)，必須建立bucketHashVector的非虛的子類，首先要做的是提供桶的實(shí)現(xiàn)類型。桶的實(shí)現(xiàn)類型應(yīng)該適合進(jìn)行插入和刪除操作，以便支持散列表的實(shí)現(xiàn)。58算法與數(shù)據(jù)結(jié)構(gòu)例如鏈接實(shí)現(xiàn)的表或者某種樹(shù)結(jié)構(gòu)。采用鏈接表實(shí)現(xiàn)桶比較簡(jiǎn)單，如果能保證散列表里每個(gè)鏈表都很短，各種操作的效率是可以保證的。定義hashList類的工作留做練習(xí)。59算法與數(shù)據(jù)結(jié)構(gòu)如果對(duì)桶中可能出現(xiàn)的元素?cái)?shù)目無(wú)法做出合理估計(jì)，采用鏈表實(shí)現(xiàn)桶就可能出現(xiàn)操作效率比較低的情況，因?yàn)樵诜磸?fù)的插入操作中，散列表里某些桶〔鏈表〕可能變得很長(zhǎng)，這時(shí)鏈表的線性查尋時(shí)間對(duì)操作效率就會(huì)產(chǎn)生決定性的影響。60算法與數(shù)據(jù)結(jié)構(gòu)類10.4給出了hashTree類的標(biāo)準(zhǔn)說(shuō)明，它也定義為bucketHashVector的子類。這個(gè)類中采用第七章中討論的AVL樹(shù)作為類型參數(shù)B的實(shí)現(xiàn)類型。這樣做無(wú)論桶的大小如何變化，都可以較好地保證桶內(nèi)的查尋效率。在這個(gè)類里定義了插入、刪除、包含測(cè)試三個(gè)成員函數(shù)，并提供了實(shí)際的構(gòu)造函數(shù)和一個(gè)桶遍歷器生成函數(shù)。

61算法與數(shù)據(jù)結(jié)構(gòu)template<classT>classhashTree:publicbucketHashVector<avlTree<T>,T,T>

{

public:

//構(gòu)造函數(shù)

hashTree(unsignedintmax,unsignedint(f)(constT&));

voidadd(Tnewele);//增加一元素

intincludes(Tele)const;//元素包含

voidremove(Tele);//刪除一元素

protected:

virtualiterator<T>makeIterator(unsignedinti);

};

類10.4hashTree類的標(biāo)準(zhǔn)說(shuō)明〔用AVL樹(shù)作桶實(shí)現(xiàn)散列表〕

62算法與數(shù)據(jù)結(jié)構(gòu)在桶散列表里增加或刪除元素，采用的實(shí)現(xiàn)方式應(yīng)該與檢測(cè)元素是否在散列表中類似：首先調(diào)用散列函數(shù)完成桶的選擇，然后對(duì)選定的桶進(jìn)行具體操作。hashTree類里桶的類型已經(jīng)確定，這些操作的實(shí)現(xiàn)都非常簡(jiǎn)單。下面是add操作的實(shí)現(xiàn)。

63算法與數(shù)據(jù)結(jié)構(gòu)template<classT>voidhashTree<T>::add(Tnewele)

{//先找到適宜的桶，再把元素插入桶中

buckets[hash(newele)].add(newele);

}

64算法與數(shù)據(jù)結(jié)構(gòu)桶散列結(jié)構(gòu)操作時(shí)間的分析

人們經(jīng)常使用桶散列表結(jié)構(gòu)，一個(gè)重要原因是在這種結(jié)構(gòu)上各種操作的執(zhí)行效率比較高。但是，另一方面，這種散列結(jié)構(gòu)操作的執(zhí)行時(shí)間估計(jì)卻比較復(fù)雜，它一方面與選定的散列函數(shù)和實(shí)際關(guān)鍵碼的分布情況有關(guān)，另一方面又與結(jié)構(gòu)的具體設(shè)計(jì)有關(guān)。后者又不但受到桶類型選擇的影響，也受到桶的個(gè)數(shù)即向量大小的影響。

65算法與數(shù)據(jù)結(jié)構(gòu)首先看桶的數(shù)目對(duì)處理速度的影響。很明顯：桶散列表里的桶越少，發(fā)生碰撞的可能性就越大。對(duì)桶個(gè)數(shù)的選擇還有另一個(gè)需要考慮的因素：為使實(shí)際元素的關(guān)鍵碼能較均勻地映射到各桶里，人們經(jīng)常將桶的個(gè)數(shù)取定為某個(gè)素?cái)?shù)，也用它作為散列函數(shù)的最后數(shù)值范圍。66算法與數(shù)據(jù)結(jié)構(gòu)

其次，桶類型的選擇對(duì)處理速度的影響也是顯然的。在根據(jù)關(guān)鍵碼選定某個(gè)桶后，下一步處理的速度就依賴于在桶內(nèi)處理的情況。如果采用AVL樹(shù)類型的桶，桶內(nèi)查找元素的平均時(shí)間代價(jià)是O(logk)(這里k是桶內(nèi)元素個(gè)數(shù))；如果用簡(jiǎn)單鏈表結(jié)構(gòu)作為桶，桶內(nèi)查找元素就需要O(k)時(shí)間。67算法與數(shù)據(jù)結(jié)構(gòu)

在所有有關(guān)因素中，最難分析的是散列函數(shù)的影響。由于散列表的內(nèi)容是不斷變化的，插入和刪除的關(guān)鍵碼不能事先確定，對(duì)一個(gè)選定的散列函數(shù)，它某時(shí)刻可能正好把所有元素均勻映射到各個(gè)桶中，而另一時(shí)刻也可能把所有元素都映射到同一個(gè)桶里。這里還有一個(gè)重要因素，那就是散列函數(shù)本身的計(jì)算復(fù)雜性。68算法與數(shù)據(jù)結(jié)構(gòu)設(shè)在一個(gè)桶散列表里有n個(gè)元素、m個(gè)桶，如果散列函數(shù)具有最理想的效果，每個(gè)桶中應(yīng)該有大約n/m個(gè)元素。假定散列函數(shù)的計(jì)算時(shí)間是常量，確定一個(gè)元素對(duì)應(yīng)的桶里只需要常數(shù)時(shí)間，那么，在這個(gè)散列表里增加一個(gè)元素，花費(fèi)的時(shí)間主要就是向一個(gè)有n/m個(gè)元素的桶中增加一個(gè)元素所需要的時(shí)間。對(duì)于有k個(gè)元素的AVL樹(shù)而言，加一個(gè)元素的時(shí)間代價(jià)是Ｏ(logk)，這意味著在對(duì)應(yīng)散列結(jié)構(gòu)里，增加一個(gè)元素的時(shí)間為Ｏ(logn/m)。如果參加表中的數(shù)據(jù)元素個(gè)數(shù)有限，能夠保證n/m非常小，在一定的限制范圍里Ｏ(logn/m)幾乎就可以看作常數(shù)。

69算法與數(shù)據(jù)結(jié)構(gòu)10.5桶散列結(jié)構(gòu)的遍歷器

為了遍歷一個(gè)桶散列表，我們必須遍歷表中的每個(gè)桶，因此，對(duì)整個(gè)結(jié)構(gòu)的遍歷過(guò)程實(shí)際上包含了散列表向量本身的遍歷和各個(gè)桶的遍歷兩個(gè)層次。要實(shí)現(xiàn)這種遍歷過(guò)程，在桶散列表遍歷器里就必須必須保存兩個(gè)值，以便能刻畫(huà)遍歷過(guò)程的當(dāng)前進(jìn)展情況：一個(gè)值是當(dāng)時(shí)正在被遍歷的那個(gè)桶的下標(biāo)；另一個(gè)值是個(gè)指針，它指向在桶散列表遍歷過(guò)程中動(dòng)態(tài)生成的當(dāng)前桶的遍歷器。

70算法與數(shù)據(jù)結(jié)構(gòu)

template<classB,classH,classT>classbucketHashVectorIterator:publiciterator<T>

{

public:

//構(gòu)造函數(shù)

bucketHashVectorIterator(bucketHashVector<B,H,T>&v);

bucketHashVectorIterator(constbucketHashVectorIterator&);

//遍歷器原型

virtualintinit();

virtualToperator()();

virtualintoperator!();

virtualintoperator++();

virtualvoidoperator=(Tvalue);

protected:

constbucketHashVector<B,H,T>&base;

unsignedintcurrentIndex;

iterator<T>itr;

intgetNextIterator();

};

類10.5bucketHashVectorIterator類的標(biāo)準(zhǔn)說(shuō)明

71算法與數(shù)據(jù)結(jié)構(gòu)在開(kāi)始散列表遍歷時(shí)，首先必須創(chuàng)立一個(gè)桶遍歷器。由于未必每個(gè)桶都實(shí)際存有元素，所以在創(chuàng)立遍歷器時(shí)就需要進(jìn)行檢查，可能要連續(xù)檢測(cè)假設(shè)干個(gè)桶才能找到第一個(gè)非空的桶。創(chuàng)立遍歷器的工作由getNextIterator函數(shù)完成。

72算法與數(shù)據(jù)結(jié)構(gòu)template<classB,classH,classT>intbucketHashVectorIterator<B,H,T>::init()

{//初始化遍歷器

currentIndex=0;//尋找第一個(gè)桶

itr=0;

returngetNextIterator();

}

73算法與數(shù)據(jù)結(jié)構(gòu)template<classB,classH,classT>intbucketHashVectorIterator<B,H,T>::getNextIterator()

{//如果存在舊遍歷器那么刪除

if(itr!=0)deleteitr;

//尋找一個(gè)新的遍歷器

for(;currentIndex<base.tablesize;currentIndex++)

{//在當(dāng)前位置上創(chuàng)立一個(gè)新的遍歷器

itr=base.makeIterator(currentIndex);

assert(itr!=0);

//遍歷器有元素〔找到有元素的桶〕那么繼續(xù)執(zhí)行

if(itr->init())return1;

//否那么刪除它，再試下一個(gè)桶

deleteitr;

}

//沒(méi)有下一個(gè)有效遍歷器時(shí)結(jié)束

itr=0;

return0;

}

74算法與數(shù)據(jù)結(jié)構(gòu)在遞增運(yùn)算中也會(huì)遇到類似的情況，如果當(dāng)前桶的遍歷器本身還能執(zhí)行增量操作，那么這個(gè)遍歷器所訪問(wèn)的元素就是下一個(gè)元素；否那么就需要調(diào)用getNextIterator函數(shù)，到隨后的桶中去尋找下一個(gè)元素。

75算法與數(shù)據(jù)結(jié)構(gòu)template<classB,clasH,classT>intbucketHashVectorIterator<B,H,T>::operator++()

{//檢查當(dāng)前遍歷器是否還能找到下一個(gè)元素

if(itr&&(itr)++)return1;

//假設(shè)不能，那么轉(zhuǎn)到下一個(gè)遍歷器

currentIndex++;

returngetNextIterator();

}

76算法與數(shù)據(jù)結(jié)構(gòu)bucketHashVectorIterator類的子類也只是對(duì)其父類的一些標(biāo)識(shí)符換名。下面給出散列樹(shù)遍歷器類的定義，其中散列樹(shù)是桶類為AVL樹(shù)的桶散列表。

77算法與數(shù)據(jù)結(jié)構(gòu)template<classT>classhashTreeIterator

:publicbucketHashVectorIterator<avlTree<T>,T,T>

{

public:

hashTreeIterator(hashTree<T>&x);

};

78算法與數(shù)據(jù)結(jié)構(gòu)template<classT>hashTreeIterator<T>::hashTreeIterator

(hashTree<T>&x):bucketHashVectorIterator<avlTree<T>,T,T>(x)

{}

79算法與數(shù)據(jù)結(jié)構(gòu)10.6用散列表實(shí)現(xiàn)集合

采用存儲(chǔ)桶方式的散列表，元素分別放在各個(gè)桶里，每桶存放假設(shè)干元素?？疾煸貢r(shí)首先用散列函數(shù)確定對(duì)應(yīng)的桶，然后再進(jìn)行桶內(nèi)操作。

這種實(shí)現(xiàn)方法的一個(gè)優(yōu)點(diǎn)是能有效地實(shí)現(xiàn)集合求并與求交等運(yùn)算，對(duì)兩個(gè)集合的操作可以通過(guò)兩個(gè)集合中對(duì)應(yīng)的各對(duì)桶的操作完成。80算法與數(shù)據(jù)結(jié)構(gòu)類10.7是基于桶散列表定義的集合的標(biāo)準(zhǔn)，提供的操作包括相關(guān)的插入、刪除、判斷元素包含關(guān)系等等，要實(shí)現(xiàn)這些運(yùn)算，只需把有關(guān)參數(shù)散列到適當(dāng)?shù)耐袄?，然后再在各個(gè)桶中進(jìn)行下一步的操作。

81算法與數(shù)據(jù)結(jié)構(gòu)

template<classT>classsetTable:publicbucketHashVector<setList<T>,T,T>

{

public:

//構(gòu)造函數(shù)

setTable(unsignedintmax,unsignedint(f)(constT&));

//成員函數(shù)

void add(Tval);

void differenceFrom(setTable<T>&);

int includes(Tval)const;

void intersectWith(setTable<T>&);

void remove(T val);

void unionWith(setTable<T>&);

int subset(setTable<T>&)const;

int operator==(setTable<T>&)const;

protected:

iterator<T>makeIterator(unsignedinti);

};

類10.7setTable類的標(biāo)準(zhǔn)說(shuō)明。

82算法與數(shù)據(jù)結(jié)構(gòu)這里我們沒(méi)有把setTable定義為set類的子類，主要是考慮集合操作的效率，考慮到上面提出的集合運(yùn)算實(shí)現(xiàn)方式。如果把一個(gè)桶散列表作為這個(gè)集合的數(shù)據(jù)成分，程序里就不能直接訪問(wèn)其中的各個(gè)桶了。在這里采用了繼承方式，把bucketHashVector作為基類，集合的有關(guān)操作都可以通過(guò)直接訪問(wèn)bucketHashVector的數(shù)據(jù)成分buckets而實(shí)現(xiàn)。83算法與數(shù)據(jù)結(jié)構(gòu)下面是一些操作的實(shí)現(xiàn)：

template<classT>voidsetTable<T>::add(Tval)

{

buckets[hash(val)].add(val);

}

template<classT>setTable<T>::includes(Tval) const

{

returnbuckets[hash(val)].includes(val);

}

84算法與數(shù)據(jù)結(jié)構(gòu)求并集和交集的運(yùn)算，通過(guò)對(duì)桶向量進(jìn)行循環(huán)，一桶一桶地實(shí)施相應(yīng)操作來(lái)完成。

template<classT>voidsetTable<T>::unionWith(setTable<T>&right)

{

assert(tablesize==right.tablesize);

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

buckets[i].unionWith(right.buckets[i]);

}

85算法與數(shù)據(jù)結(jié)構(gòu)template<classT>intsetTable<T>::subset(setTable<T>&right)

{

assert(tablesize==right.tablesize);

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

if(!buckets[i].subset(right.buckets[i]))

return0;

return1;

}

86算法與數(shù)據(jù)結(jié)構(gòu)注意，在上面實(shí)現(xiàn)中，參加運(yùn)算的兩個(gè)集合(接受者和參數(shù))必須同是setTable<T>類型。實(shí)際上，這里不僅要求它們都是桶散列表，而且要求它們具有相同的散列函數(shù)，相同的桶類型和tablesize值。只有這樣才能保證操作的正確性87算法與數(shù)據(jù)結(jié)構(gòu)10.7用桶散列表實(shí)現(xiàn)字典

下面用的是繼承方式，從bucketHashVector類出發(fā)建立dictionaryTable類。dictionaryTable類從bucketHashVector類那里繼承了所有行為，定義了作為字典的必要操作。88算法與數(shù)據(jù)結(jié)構(gòu)template<classK,classV>classdictionaryTable:public

bucketHashVector<dictionaryList<K,V>,K,association<K,V>>

{

public:

//構(gòu)造函數(shù)

dictionaryTable(unsignedintmax,unsignedint(f)(constK&));

dictionaryTable(unsignedintmax,unsignedint(f)(constK&),V&);

//新的dictionaryTable類的操作

V&operator[](Kkey);

voidremoveKey(Kkey);

voidsetInitial(VinitialValue);

protected:

iterator<association<K,V>>makeIterator(unsignedinti);

}

類10.8dictionaryTable類的標(biāo)準(zhǔn)說(shuō)明

89算法與數(shù)據(jù)結(jié)構(gòu)我們?cè)谶@里沒(méi)有把dictionaryTable類定義為dictionary類的子類，考慮的問(wèn)題與前面定義setTable時(shí)類似。90算法與數(shù)據(jù)結(jié)構(gòu)

template<classK,classV>dictionaryTable<K,V>::dictionaryTable

(unsignedintmax,unsignedint(

f)(constK&),V&v)

:bucketHashVector<dictionaryList<K,V>,K,association<K,V>

>(max,f)

{//在每一個(gè)桶中置初值

setInitial(v);

}

91算法與數(shù)據(jù)結(jié)構(gòu)成員函數(shù)setInitial設(shè)置各個(gè)桶的初值。注意桶的類型是dictionaryList，實(shí)現(xiàn)這里的初值設(shè)置，只要對(duì)每個(gè)桶(buckets[i])執(zhí)行dictionaryList類的setInitial函數(shù)即可。

92算法與數(shù)據(jù)結(jié)構(gòu)template<classK,classV>voiddictionaryTable<K,V>::setInitial(Vval)

{//在每一個(gè)桶中置初值

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

buckets[i].setInitial(val);

}

93算法與數(shù)據(jù)結(jié)構(gòu)下標(biāo)操作和removeKey函數(shù)的實(shí)現(xiàn)很簡(jiǎn)單，先根據(jù)給定關(guān)鍵碼確定桶對(duì)象(dictionaryList類的對(duì)象)，然后對(duì)該桶執(zhí)行下標(biāo)或removeKey操作。

94算法與數(shù)據(jù)結(jié)構(gòu)template<classK,classV>V&dictionaryTable<K,V>::operator[](Kkey)

{//尋找正確的字典，然后對(duì)字典進(jìn)行下標(biāo)操作

returnbuckets[hash(key)][key];

}

template<classK,classV>voiddictionaryTable<K,V>::removeKey(Kkey)

{//尋找正確的桶，然后刪除該元素

buckets[hash(key)].removeKey(key);

}

95算法與數(shù)據(jù)結(jié)構(gòu)注意，在dictionaryTable類中，繼承而來(lái)的bucketHashVector類的第二、第三個(gè)模板參數(shù)具有不同類型，這一點(diǎn)與前面使用bucketHashVector類的情況都不同。這里對(duì)關(guān)鍵碼進(jìn)行散列處理，而遍歷器的返回值是對(duì)關(guān)聯(lián)的引用。

96算法與數(shù)據(jù)結(jié)構(gòu)template<classK,classV>classdictionaryTableIterator

:publicbucketHashVectorIterator<dictionaryList<K,V>,K,association<K,V>

>

{

public:

//構(gòu)造函數(shù)

dictionaryTableIterator(dictionaryTable<K,V>&v);

};

類10.9dictionaryTableIterator類

97算法與數(shù)據(jù)結(jié)構(gòu)新類的構(gòu)造函數(shù)非常簡(jiǎn)單，只要將被遍歷字典(函數(shù)參數(shù)d)從原來(lái)的dictionaryTable<