查找 - 散列技術 - 散列表上的運算

　　散列表上的運算

　　散列表上的運算有查找插入和刪除其中主要是查找這是因為散列表的目的主要是用於快速查找且插入和刪除均要用到查

　　找操作

　　散列表類型說明

　　#define NIL //空結點標記依賴於關鍵字類型本節假定關鍵字均為非負整數

　　#define M //表長度依賴於應用但一般應根據確定m為一素數

　　typedef struct{ //散列表結點類型

　　KeyType key;

　　InfoType otherinfo; //此類依賴於應用

　　}NodeType;

　　typedef NodeType HashTable[m]; //散列表類型

　　基於開放地址法的查找算法

　　散列表的查找過程和建表過程相似假設給定的值為K根據建表時設定的散列函數h計算出散列地址h(K)若表中該地址單元

　　為空則查找失敗;否則將該地址中的結點與給定值K比較若相等則查找成功否則按建表時設定的處理沖突的方法找下一個地址

　　如此反復下去直到某個地址單元為空(查找失敗)或者關鍵字比較相等(查找成功)為止

　　()開放地址法一般形式的函數表示

　　int Hash(KeyType kint i)

　　{ //求在散列表T[m]中第i次探查的散列地址hi≤i≤m

　　//下面的h是散列函數Increment是求增量序列的函數它依賴於解決沖突的方法

　　return(h(K)+Increment(i))%m; //Increment(i)相當於是d i

　　}

　　若散列函數用除余法構造並假設使用線性探查的開放定址法處理沖突則上述函數中的h(K)和Increment(i)可定義為

　　int h(KeyType K){ //用除余法求K的散列地址

　　return K%m;

　　}

　　int Increment(int i){//用線性探查法求第i個增量d i

　　return i; //若用二次探查法則返回i*i

　　}

　　()通用的開放定址法的散列表查找算法

　　int HashSearch(HashTable TKeyType Kint *pos)

　　{ //在散列表T[m]中查找K成功時返回失敗有兩種情況找到一個開放地址

　　//時返回表滿未找到時返回 *pos記錄找到K或找到空結點時表中的位置

　　int i=; //記錄探查次數

　　do{

　　*pos=Hash(Ki); //求探查地址hi

　　if(T[*pos]key==K) return l; //查找成功返回

　　if(T[*pos]key==NIL) return ;//查找到空結點返回

　　}while(++i

　　return -1; //表滿且未找到時，查找失敗

　　} //HashSearch

　　注意：

　　上述算法適用於任何開放定址法，只要給出函數Hash中的散列函數h(K)和增量函數Increment(i)即可。Tw.WINgwiT.cOm但要提高查找效率時，

　　可將確定的散列函數和求增量的方法直接寫入算法HashSearch中，相應的算法【參見習題】。

　　3、基於開放地址法的插入及建表

　　建表時首先要將表中各結點的關鍵字清空，使其地址為開放的;然後調用插入算法將給定的關鍵字序列依次插入表中。

　　插入算法首先調用查找算法，若在表中找到待插入的關鍵字或表已滿，則插入失敗;若在表中找到一個開放地址，則將待插入的

　　結點插入其中，即插入成功。

　　void Hashlnsert(HashTable T，NodeTypene w)

　　{ //將新結點new插入散列表T[0..m-1]中

　　int pos，sign;

　　sign=HashSearch(T，new.key，&pos); //在表T中查找new的插入位置

　　if(!sign) //找到一個開放的地址pos

　　T[pos]=new; //插入新結點new，插入成功

　　else //插人失敗

　　if(sign>0)

　　printf("duplicate key!"); //重復的關鍵字

　　else //sign<0

　　Error("hashtableoverflow!"); //表滿錯誤，終止程序執行

　　} //Hashlnsert

　　void CreateHashTable(HashTable T，NodeType A[]，int n)

　　{ //根據A[0..n-1]中結點建立散列表T[0..m-1]

　　int i

　　if(n>m) //用開放定址法處理沖突時，裝填因子α須不大於1

　　Error("Load factor>1");

　　for(i=0;i

　　T[i].key=NIL; //將各關鍵字清空，使地址i為開放地址

　　for(i=0;i

　　Hashlnsert(T，A[i]);

　　} //CreateHashTable

　　4、刪除

　　基於開放定址法的散列表不宜執行散列表的刪除操作。若必須在散列表中刪除結點，則不能將被刪結點的關鍵字置為NIL，而應該

　　將其置為特定的標記DELETED。

　　因此須對查找操作做相應的修改，使之探查到此標記時繼續探查下去。同時也要修改插人操作，使其探查到DELETED標記時，將

　　相應的表單元視為一個空單元，將新結點插入其中。這樣做無疑增加了時間開銷，並且查找時間不再依賴於裝填因子。

　　因此，當必須對散列表做刪除結點的操作時，一般是用拉鏈法來解決沖突。

　　注意：

　　用拉鏈法處理沖突時的有關散列表上的算法【參見練習】。

　　5、性能分析

　　插入和刪除的時間均取決於查找，故下面只分析查找操作的時間性能。

　　雖然散列表在關鍵字和存儲位置之間建立了對應關系，理想情況是無須關鍵字的比較就可找到待查關鍵字。但是由於沖突的存在

　　，散列表的查找過程仍是一個和關鍵字比較的過程，不過散列表的平均查找長度比順序查找、二分查找等完全依賴於關鍵字比較的查

　　找要小得多。

　　(1)查找成功的ASL

　　散列表上的查找優於順序查找和二分查找。

　　【例】在例9.1和例9.2的散列表中，在結點的查找概率相等的假設下，線性探查法和拉鏈法查找成功的平均查找長度分別為：

　　ASL=(1×6+2×2+3×l+9×1)/10=2.2 //線性探查法

　　ASL=(1×7+2×2+3×1)/10=1.4 //拉鏈法

　　而當n=10時，順序查找和二分查找的平均查找長度(成功時)分別為：

　　ASL=(10+1)/2=5.5 //順序查找

　　ASL=(1×l+2×2+3×4+4×3)/10=2.9 //二分查找，可由判定樹求出該值

　　(2) 查找不成功的ASL

　　對於不成功的查找，順序查找和二分查找所需進行的關鍵字比較次數僅取決於表長，而散列查找所需進行的關鍵字比較次數和待

　　查結點有關。因此，在等概率情況下，也可將散列表在查找不成功時的平均查找長度，定義為查找不成功時對關鍵字需要執行的平均

　　比較次數。

　　【例】例9.1和例9.2的散列表中，在等概率情況下，查找不成功時的線性探查法和拉鏈法的平均查找長度分別為：

　　ASL unsucc =(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=59/13≈4.54

　　ASL unsucc =(1+0+2+1+0+1+1+0+0+0+1+0+3)/13≈10/13≈0.77

　　注意：

　　①由同一個散列函數、不同的解決沖突方法構造的散列表，其平均查找長度是不相同的。

　　②散列表的平均查找長度不是結點個數n的函數，而是裝填因子α的函數。因此在設計散列表時可選擇α以控制散列表的平均查找

　　長度。

　　③ α的取值

　　α越小，產生沖突的機會就小，但α過小，空間的浪費就過多。只要α選擇合適，散列表上的平均查找長度就是一個常數，即散

　　列表上查找的平均時間為O(1)。

　　④ 散列法與其他查找方法的區別

　　除散列法外，其他查找方法有共同特征為：均是建立在比較關鍵字的基礎上。其中順序查找是對無序集合的查找，每次關鍵字的比較

　　結果為"="或"!="兩種可能，其平均時間為O(n);其余的查找均是對有序集合的查找，每次關鍵字的比較有"="、"<"和">"三種可能

　　，且每次比較後均能縮小下次的查找范圍，故查找速度更快，其平均時間為O(lgn)。而散列法是根據關鍵字直接求出地址的查找方法

　　，其查找的期望時間為O(1)。

From:http://tw.wingwit.com/Article/program/sjjg/201311/23675.html