1、2020/9/5,福州大學數學與計算機科學學院,1,第9章 符號表,9.1 實現符號表的簡單方法,9.2 用散列表實現符號表,9.3 符號表的應用,吳英杰,2020/9/5,福州大學數學與計算機科學學院,2,第9章 符號表 學習要點： 理解抽象數據類型符號表的概念。 掌握數組實現符號表的方法。 理解開散列和閉散列的概念。 掌握用開散列表實現符號表的方法。 掌握除余法、數乘法、平方取中法、基數轉換法和隨機數法等散列函數構造方法。 掌握采用線性重新散列技術的閉散列表實現符號表的方法。,返回章目錄,2020/9/5,福州大學數學與計算機科學學院,3,9.1 實現符號表的簡單方法,9.1.1 引言 A

2、DT符號表的概念 以集合為基礎，并支持Member、Insert和Delete三種運算的抽象數據類型叫做符號表。 ADT符號表的應用 公司的客戶符號表 一個地區(qū)的固定/移動電話號碼符號表 軟件開發(fā)中的數據符號表 網上的在線符號表 互聯網/企業(yè)網/局域網網管中的IP地址符號表等等,2020/9/5,福州大學數學與計算機科學學院,4,可以用表示集合的鏈表或位向量來實現符號表。 實現符號表的另一簡單方法是用一個定長數組來存儲集合中的元素。 這種方法的優(yōu)點是結構簡單，易于操作。 它的缺點是所支持的符號表運算的時間復雜度較高。 表示集合大小受數組大小的限制。,2020/9/5,福州大學數學與計算機科學學

3、院,5,9.1 實現符號表的簡單方法,9.1.2 用固定數組實現符號表 數組實現符號表的結構定義如下： typedef struct atab *Table; Typedef struct atab int arraysize; int last; SetItem *data; Atab;,2020/9/5,福州大學數學與計算機科學學院,6,9.1 實現符號表的簡單方法,9.1.2 用固定數組實現符號表 優(yōu)點： 結構簡單，實現操作的邏輯簡單。 缺點： 所表示的集合的大小受到數組大小的限制。 三個基本操作在最壞情況下都需要O(n)。 通常集合元素并不占滿整個數組，空間沒有得到充分利用。,返回章目

4、錄,2020/9/5,福州大學數學與計算機科學學院,7,9.2 用散列表實現符號表,實現符號表的另一個重要技巧是散列（hashing）技術。用散列來實現符號表可以使符號表的每個運算所需的平均時間是一個常值。 在最壞情況下每個運算所需的時間正比于集合的大小。 散列有兩種形式，一種是開散列（外部散列），它將符號表元素存放在一個潛無窮的空間里，能處理任意大小的集合。 另一種是閉散列（內部散列），它使用一個固定大小的存儲空間，所能處理的集合大小不能超過其存儲空間大小。,2020/9/5,福州大學數學與計算機科學學院,8,9.2.1 開散列,開散列的基本思想是將集合的元素（可能有無窮多個）劃分成有限個類

5、。例如，劃分為0，1，B1這B個類。 用散列函數h將集合中的每個元素x映射到0，1，B之一，h(x)的值就是x所屬的類。 函數h(x)的值稱為元素x的散列值。 每一個類稱為一個桶，并且稱x屬于桶h(x)。 期望散列能均勻，使得當桶數組的規(guī)模與符號表的規(guī)模同階時，桶數組的每一個桶中大致有常數個元素，從而對符號表的三個基本操作都只需要常數時間。 這里的問題是如何散列即如何構造散列(映射)函數去達到設想的期望？,2020/9/5,福州大學數學與計算機科學學院,9,例 一組關鍵字為（21， 14， 19，58， 65， 32， 72） H(K)=K % 11,2020/9/5,福州大學數學與計算機科學

6、學院,10,int hash1(char * x) int len,i,j=0; len=strlen(x); for(int i=0;ilen ;i+) j+=xi; return j%101; ,2020/9/5,福州大學數學與計算機科學學院,11,用開散列表實現的符號表結構OpenHashTable定義如下： typedef struct open *OpenHashTable; typedef struct open int size; /*桶數組的大小*/ int (*hf) (SetItem x); /*散列函數*/ List *ht; /*桶數組*/ Open; 由此可以看出，開

7、散列表是將數組和表結合在一起的一種數據結構，并且利用二者的優(yōu)點，克服二者的缺點。,2020/9/5,福州大學數學與計算機科學學院,12,9.2.2 閉散列,閉散列表將表中元素直接存放在桶單元中。 閉散列表中的每個桶都只能存放集合中的一個元素。 當要把元素x存放到桶h(x)中，但發(fā)現這個桶已被其它元素占用時，就發(fā)生了沖突。 為了解決閉散列中的沖突，需要使用重新散列技術，使得發(fā)生沖突時，按重新散列技術可以選取一個桶序列h1(x)，h2(x)。 只要桶單元尚未全部被占用，順序試探這個桶序列中各個桶，一定能找到一個空桶來存放元素x。 最簡單的重新散列技術是線性重新散列技術，即當散列函數為h(x)，桶數

8、為B時，取 hi(x)=(h(x)+i)%B，i=1，2，B-1,2020/9/5,福州大學數學與計算機科學學院,13,例 一組關鍵字為（ 20，30，70，15，8，12，18，63，19 ） H(K)=K % 11,用線性探測法處理沖突！,2020/9/5,福州大學數學與計算機科學學院,14,9.2.2.1 散列需要解決的問題：,1、 構造好的散列函數 （1）所選函數盡可能簡單，以便提高轉換速度。 （2）所選函數對關鍵字計算出的地址，應在散列地址集中大致均勻分布，以減少空間浪費。 2、 制定解決沖突的方案。,3、需要對ht 的每一個桶的狀態(tài)加以標記： statek=0表示htk桶存放著元素

9、。 statek=1表示htk桶一直是空桶。 statek=2表示htk桶現在是空桶但曾經存放過元素,9.2.2 閉散列,2020/9/5,福州大學數學與計算機科學學院,15,檢測一個元素x是否在一個閉散列表中，只要順序查看桶h(x)，h1(x)，h2(x)，。 在某個桶中找到x，則x在這個閉散列表中。 沒有找到x而遇一空桶，是否可以斷定x不在這個閉散列表中？ 如果在這個閉散列表中沒有執(zhí)行過刪除操作，可以斷定x不在閉散列表中。 如果對這個閉散列表執(zhí)行過刪除操作，就無法確定所遇到的空桶在當初存放x時是否曾被占用，因而也就無法確定x是否在閉散列表中。 解決這個問題的一個有效方法是對ht 的每一個桶

10、的狀態(tài)加以標記.,2020/9/5,福州大學數學與計算機科學學院,16,9.2.2.2 對刪除運算的改進,函數HTDelete(x,H)在FindMatch找到元素x所在的桶數組單元i后，將該單元所對應的狀態(tài)statei的值置為2，表明hti中元素x已被刪除。 void HTDelete(SetItem x,HashTable H) int i= FindMatch(x,H); if(isize ,2020/9/5,福州大學數學與計算機科學學院,17,改進HTDelete的基本思想： 刪除元素算法HTDelete的一個明顯不足是在執(zhí)行了大量元素刪除運算后，在散列表中查詢的速度減慢。 其主要原因

11、是在執(zhí)行查詢運算時，其中元素已被刪除的桶單元是當作非空桶單元來處理的。 實現刪除運算的另一種策略是在刪除一個元素后，用當前桶中另一個元素來填充被刪除元素釋放的桶空間。,填充刪除的條件,2020/9/5,福州大學數學與計算機科學學院,18,9.2.2 閉散列,改進HTDelete的基本思想： 動機是希望騰出的空桶(記為hti)不僅僅可供新元素插入，而且能為提高還在桶數組中的元素(比如y= htj)的查找速度作出貢獻：減少查找y的探測次數。 容易理解，如果不作任何改進，查找y的探測次數會等于插入y時的探測次數。如果插入y時x已在桶hti中且與x發(fā)生沖突而增加了插入的探測次數，那么，現在x不存在了，

12、只要將x騰出的桶hti讓y頂替，就可以使得將來查找y時減少探測次數。因此改進HTDelete的途徑是在當前的桶數組中找能頂替x的y。如果找不到，就按HTDelete的原版處理；如果找得到，在用y頂替x之后還可以引起連鎖反應。,2020/9/5,福州大學數學與計算機科學學院,19,9.2.2 閉散列,改進HTDelete的細節(jié)找能頂替x的y 假設被刪除元素x位于桶單元hti?，F考察一個非空單元htj中的元素y，其散列函數值設為h=hf(y)，則按從h出發(fā)的線性探測，只要i比j離h近即可使得在頂替后找y的探測次數減少。 當ij時，若ihj，則不可用元素htj頂替hti；若hij或ijh，則可用元素

13、htj頂替hti。如下圖(a)。 當ji時，若jhI，則可用元素htj頂替hti，如下圖 (b)；否則不可。 這里以線性探測為前題，以頂替后減少探測次數為目標。,2020/9/5,福州大學數學與計算機科學學院,20,9.2.3 散列函數的構造方法,1、直接定址法：取關鍵字的某個線性函數值作為散列地址。較直觀的方法 H(key)=a*key+b; /a、b為常數,2、除留余數法：取關鍵字的某個不大于表長m的數p除后所得的余數作為散列地址。較簡單、常用的方法 H(key)=key%p; /p=m,3、平方取中法：取關鍵字平方后的中間幾位作為散列地址(若超出范圍時，可再取模)。,2020/9/5,福

14、州大學數學與計算機科學學院,21,9.2.3 散列函數的構造方法,4、折疊法：將關鍵字分成幾個部分，再將這幾個部分結合(作某一運算)起來的值作為散列地址。常用于關鍵字的位數較多的情況,5、數值分析法：如果事先知道所有可能的關鍵字的取值時，可通過對這些關鍵字分析，發(fā)現其變化規(guī)律，構造出相應的函數。,2020/9/5,福州大學數學與計算機科學學院,22,9.2.4 處理沖突的方法,1、線性探測法：當由H(k)算出的位置不空時，依次用下面函數以找出一個新的空位置。 Hi(k)=(H(k)+di) mod m,其中 i=1,2,k(km-1) 其中：m為散列表長度，di的取值常用如下形式：di=i，即

15、di為增量序列，依次取值 1，2，m-1,2020/9/5,福州大學數學與計算機科學學院,23,例：已知散列表的地址區(qū)間為011，散列函數為H(k)=k % 11,采用線性探測法處理沖突，試將以下關鍵字序列依次存儲到散列表中，構造出該散列表，并求出在等概論情況下的平均查找長度。 20，30，70，15，8，12，18，63，19,H(20)=9, 可直接存放到A9中(搜索時次數為1)； H(19)=8， 因為下標為811的元素均已被占用，故往后搜索并繞回到A0存放(搜索時次數為5) 。,2020/9/5,福州大學數學與計算機科學學院,24,在等概率情況下，該表成功的平均查找長度如下： （152

16、1314151）/919/9,9.2.2.3 處理沖突的方法,2020/9/5,福州大學數學與計算機科學學院,25,9.2.4 處理沖突的方法 2、二次重新散列技術 它選取的探查桶序列為：h(x),h1(x) ,h2(x) ,h2i(x) ,h2i+1(x) , 其中， 3、隨機重新散列技術 它選取的探查桶序列為： ,i=1，2，B-1。 其中， 是1，2，B-1的一個隨機排列。 4、雙重散列技術 這種方法使用2個散列函數h和h來產生探索序列： 其中 i=1，2，B-1。要求h(x)的值和B互素 。,2020/9/5,福州大學數學與計算機科學學院,26,9.2.5 用散列表實現符號表的效率 若能選擇一個好的散列函數，將集合中的N個元素均勻地散列到B個桶中，那么，每個桶中平均有N/B個元素，使得在開散列表中，HTInsert，HTDelete和HTMember運算都只要O(N/B)的平均時間。進而當N/B為一常數時，符號表的每一個運算都可在常數時間內完成。 因此：對于開散列表，關鍵在于選擇一個好的散列函數,返回章目錄,2020/9/5,福