1、第9章 符號表實現符號表的簡單方法用散列表實現符號表開散列閉散列散列函數及其效率閉散列的重新散列技術應用舉例12011/11/15第9章 符號表在算法設計中用到的集合，往往不做集合的并、交、差運算，而常要判定某個元素是否在給定的集合中，并且要不斷地對這個集合進行元素的和刪除操作。以集合為基礎，并支持SetMember、SetInsert和SetDelete三種運算的抽象數據類型叫做符號表。ADT符號表的應用公司的客戶字典一個地區的固定/移動號碼字典開發中的數據字典網上的字典互聯網/企業網/局域網中的IP地址字典等等22011/11/159.1 實現符號表的簡單方法用固定數組用數組實現符號表的結

2、構定義如下：typedef structypedef strucab *Table;abarraysize; last;SetItem*data;Atab;32011/11/15創建一個定長數組大小為size的空符號表Table TableInit(size)Table T=malloc(sizeof *T); T-arraysize=size;T-last=0;T-data=malloc(size*sizeof(SetItem); return T;42011/11/15符號表的成員查詢運算TableMember(SetItem x,Table T)I;for(i=0;ilast;i+)if

3、(T-datai=x) return 1;return 0;52011/11/15符號表的元素運算void TableInsert(SetItem x,Table T)if(! TableMember(x,T) & T-lastarraysize)T-da-last+=x;62011/11/15符號表的元素刪除運算void TableDelete(SetItem x,Table T)i=0;if (T-last0)while(T-datai!=x & ilast) if(ilast & T-datai=x)T-datai=T-data-T-last;i+;72011/11/159.1 實現符號

4、表的簡單方法用固定數組優點：結構簡單，實現操作的邏輯簡單。缺點：所表示的集合的大小受到數組大小的限制。情況下都需要O(n)。三個基本操作在通常集合元素并不占滿整個數組，因此，空間沒有得到充分利用。82011/11/159.2 用散列表實現符號表實現符號表的另一個重要技巧是散列技術。用散列來實現符號表可以使符號表的每個運算所需的平均時間是一個常數值，在正比于集合的大小。散列有兩種形式：情況下每個運算所需的時間開散列：它將符號表元素放在一個潛無窮的空間里，能處理任意大小的集合。閉散列：它使用一個固定大小的空間，所能處理的集合大小過其空間大小。92011/11/15 9.2.1 開散列基本：把符號表

5、中的所有元素散列(hashing)，即到一個桶數組(散列表)的桶中。當有多個不同元素被散列到同一個桶時，這些元素用鏈在一個表里。期望散列能均勻，使得當桶數組的規模與符號表的規模同階時，桶數組的每一個桶中大致有常數個元素，從而對符號表的三個基本操作都只需要常數時間。是如何散列即如何構造散列()函數去達這里到設想的期望？102011/11/15 9.2.1 開散列開散列的數據要素按照設想，開散列首先需要擁有一個桶數組，桶數組的規模與符號表的規模同階，桶數組中的每一個桶有一個指針各指向一個鏈表。其次需要擁有一個散列()函數，它把符號表中的元素分別散列(的鏈表中。，分散)到各桶所對應112011/11

6、/15 9.2.1 開散列散列函數的例子假設符號表的元素是字符串x，桶數組的規模為101，那么，下面是散列函數的一個具體例子：hash1(char* x)len=strlen(x), hashval = 0;for(i=0;isize=nbuckets;H-hf=hashf;H-ht=malloc(H-size*sizeof(List); for(i=0;isize;i+)H-hti=ListInit()return H;142011/11/15開散列表的成員查詢函數HTMember(x,H)，根據元素x的散列函數值確定該元素的桶號，然后調用相應的表定位函數返回查詢結果。HTMember(Se

7、tItem x,OpenHashTable H)i=(*H-hf)(x) % H-size;return (ListLocate(x,H-hti)0);152011/11/15運算HTInsert(x,H)，根據元素x的該元素的桶號，然后在該桶的表首開散列表的元素散列函數值確定元素x。void HTInsert(SetItem x,OpenHashTable H)i;if (HTMember(x,H) Error(“Bad Input”); i=(*H-hf)(x) % H-size;ListInsert(0,x,H-hti);162011/11/15開散列表的元素刪除運算HTDelete(x

8、,H)，根據元素x的散列函數值確定該元素的桶號，然后調用相應的表元素刪除函數刪除元素x。void HTDelete(SetItem x,OpenHashTable H)i;i=(*H-hf)(x) % H-size;if (k=ListLocate(x,H-hti) ListDelete(k,H-hti);172011/11/15 9.2.2 閉散列與開散列的相同點和區別相同點：把符號表中的所有元素散列(hashing)即到一個桶數組(散列表)的桶中。區別：桶數組(散列表)的桶直接用來存放符號表元素，而且一個桶只存放一個元素。出現多個元素散列到同一個桶時(這叫)，需要按照確定的規則在桶數組中進

9、行探測，找還沒有存放元素的桶(這叫空桶)，然后將發生沖突的后到元素放入空桶，解決，實現散列。182011/11/15 9.2.2 閉散列閉散列(1) 需要一個探測函數c(i)，i=0,1,2,size-1： c(0)=0,而且對于任意的0jsize-1，(j+c(0)% size, (j+c(1)% size, ,(j+c(size-1)% size是0,1,2,size-1 的重排,保證不會漏測。(2) 需要對ht 的每一個桶的狀態加以標記：sssek=0表示htk桶存放著元素。ek=1表示htk桶一直是空桶。ek=2表示htk桶現在是空桶但曾經存放過元素192011/11/15用閉散列實現

10、的符號表結構HashTable的定義typedef structypedef strucshtable *HashTable;shtablesize;/桶數組大小(*hf)(SetItem x);/散列函數SetItem *ht;/桶數組*se;/占用狀態數組Hashtable;202011/11/15初始化桶數組ht和s創建一個空的散列表HashTable HTInit(i;e，將每個桶都設置為空桶。divisor,(*hashf)(SetItem x)HashTable H=malloc(sizeof *H); H-size=divisor;H-hf = hashf;H-ht=malloc

11、(H-size*sizeof(SetItem);H-se=malloc(H-size*sizeof();for (i=0;isize;i+)H-sreturn H;ei=1;212011/11/15FindMatch(SetItem x,HashTable H)在散列表H的桶數組中查找元素x，并返回它在桶數組中的位置。I,j,k;j=(*H-hf)(x);for (i=0;isize;i+) k=(j+HashProb(i)%H-size;if (H-s if(!H-sek=1) break;ek & H-htk=x) return k;return H-size;HashProb(i)ret

12、urn i;222011/11/15返回散列表H的桶數組中可位置k。元素x的未占用桶單元Unoccupied(SetItem x,HashTable H)I,j,k;j=(*H-hf)(x);for (i=0;isize;i+) k=(j+HashProb(i) % H-size;if (H-sek)return k;return H-size;232011/11/15閉散列表通過調用函數FindMatch實現成員查詢HTMember(SetItem x,HashTable H)i=FindMatch(x,H);if (isize & H-hti=x) return 1; return 0;2

13、42011/11/15閉散列表的元素運算HTInsert(SetItem x,HashTable H)i; if(HTMember(x,H) i=Unoccupied(x,H);if(isize)Error(“Bad Input”);H-sei=0;H-hti=x;else Error(“table full”);252011/11/15閉散列表的元素刪除運算HTDelete(SetItem x,HashTable H)i=FindMatch(x,H);if (isize & H-hti=x)H-sei=2;262011/11/15上述刪除算法HTDelete的缺點：在執行了大量元素刪除運算后

14、，大量的桶的狀態標記為 2，即大量的桶的狀態標記既非 1 也非 0，使得運算 FindMatch 中的循環次數大大增加，從而導致運算 FindMatch的速度大大減慢。因此人們提出HTDelete的一種改進版本HTDelete1。272011/11/15改進HTDelete的基本：是希望騰出的空桶(記為hti)不僅僅可供新元素，而且能為提高還在桶數組中的元素(比如y= htj)的查找速度作出貢獻：減少查找y的探測次數。容易理解，如果不作任何改進，查找y的探測次數會等于y時的探測次數。如果y時x已在桶hti中且與x發的探測次數，那么，現在x不存在了，生而增加了只要將x騰出的桶hti讓y頂替，就可

15、以使得將來查找y時減少探測次數。因此，改進HTDelete的途徑是在當前的桶數組中找能頂替x的y。如果找不到，就按HTDelete的原版處理；如果找得到，在用y頂替x之后還可以引起。282011/11/15改進HTDelete的細節找能頂替x的y假設被刪除元素x位于桶單元hti。現一個非空單元htj中的元素y，其散列函數值設為h=hf(y)，則按從h出發的線性探測，只要i比j離h近即可使得在頂替后找y的探測次數減少。當ij時，若ihj，則不可用元素htj頂替hti；若hij或ijh，則可用元素htj頂替hti。如下圖(a)。當ji時，若jhI，則可用元素htj頂替hti，如下圖 (b)；否則不

16、可。這里以線性探測為前題，以頂替后減少探測次數為目標。292011/11/15Void HTDelete1SetItem x,HashTable H)改進HTDelete的函數HTDelete1i=FindMatch(x);if (isize)for (;) / &H-hti=x可以去掉/找hti的頂替元素H-sj;ei=2;/先按無頂替元素處理/從(i+1)%size開始線性搜索可頂替元素for (j=(i+1)%H-size; !sej; j=(j+1)%H-size)h=(*H-hf) (H-htj);if (h=i&ij)|(ij&jh)|(jh&hsej)break;/跳出外for循

17、環H- hti=htj; H-sei=sej;/做頂替工作i=j;/為循環找htj的頂替元素302011/11/15 9.2.3 散列函數及其效率若能選擇一個好的散列函數，將集合中的n個元素均勻地散列到B個桶中，那么每個桶中平均有n/B個元素。使得在開散列表中，HTInsert，HTDelete和 HTMember運算都只要O(n/B)的平均時間。當n/B為一常數時，每一個符號表運算都可在常數時間內完成。因此：對于開散列表，關鍵在于選擇一個好的散列函數。312011/11/15 9.2.3 散列函數及其效率幾種計算簡單且效果較好的散列函數構造方法：(1)除余法：h(k)=k%m(2)數乘法：h(k)= Bkaka(3)平方取中法：h(k)= k 2 / c %B(4)基數轉換法(5)隨機數法 ：h(k)=random(k)322011/11/15 9.2.4 閉散列的重新散列技術(1) 二次重新散列技術它選取的探查桶序列為：h(x),h1(x) ,h2(x) ,h2i(x) ,h2i+1(x) ,其中，h (x) h(x) i2 %Bh(x) h(x) i2 %B2i1