【正文】 即 :探查時從地址 d開始，首先探查 T[d]，然后依次探查 T[d+1]， … ，直到 T[m1]，此后又循環(huán)到T[0]， T[1]， … ，直到探查到 T[d1]為止。 形成探測序列的方法 開放地址法解決沖突 第 八 章 查 找 ② 雙重散列法 (Double Hashing) 該方法是開放定址法中最好的方法之一，它的探查序列是： hi=(h(key)+i*h1(key))％ m 0≤i≤m 1 即 di=i*h1(key) 即 探查序列為： d=h(key),(d+h1(key))％ m ,(d+2h1(key))％ m， … ，等。 開放地址法解決沖突 第 八 章 查 找 若選定的散列表長度為 m，則可將散列表定義為一個由 m個頭指針組成的指針數(shù)組T[0..m1]。凡是散列地址為 i的結點，均插入到以 T[i]為頭指針的單鏈表中。 T中各分量的初值均應為空指針。 二、拉鏈法解決沖突 是 將所有關鍵字為同義詞的結點鏈接在同一個單鏈表中 。 第 八 章 查 找 例： 已知一組關鍵字為（ 26，36， 41， 38， 44，15， 68， 12， 06，51），取表長為13，用拉鏈法解決沖突構造這組關鍵字的散列表如右圖 0 1 2 3 4 5 8 6 9 7 10 11 12 ∧ ∧ ∧ ∧ ∧ ∧ 26 ∧ 15 41 ∧ 12 36 ∧ 68 ∧ 06 ∧ 38 44 ∧ 51 ∧ H（ key） =key%13 拉鏈法解決沖突 第 八 章 查 找 0 1 2 3 4 5 8 6 9 7 10 11 12 26 ∧ ∧ 15 ∧ 68 ∧ 44 ∧ 06 ∧ ∧ ∧ ∧ 36 ∧ 12 41 ∧ 36 ∧ 38 51 ∧ 上題也可以如下做： m個頭指針組成的指針數(shù)組 T的每個元素改造成兩個域，一個存儲基本哈希表內(nèi)容；另一個為指針域，指向同義詞的鏈表。 拉鏈法解決沖突 第 八 章 查 找 拉鏈法解決沖突 拉鏈法的優(yōu)點 (2)由于拉鏈法中各鏈表上的結點空間是動態(tài)申請的，故它更適合于造表前無法確定表長的情況； (1)拉鏈法處理沖突簡單，且無堆積現(xiàn)象，即非同義詞決不會發(fā)生沖突，因此平均查找長度較短； 第 八 章 查 找 (3)開放定址法為減少沖突，要求裝填因子 α較小，故當結點規(guī)模較大時會浪費很多空間。而拉鏈法中可取 α≥1，且結點較大時，拉鏈法中增加的指針域可忽略不計，因此節(jié)省空間； (4)在用拉鏈法構造的散列表中，刪除結點的操作易于實現(xiàn)。只要簡單地刪去鏈表上相應的結點即可。 第 八 章 查 找 拉鏈法的 缺點 是：指針需要額外的空間，故當結點規(guī)模較小時，開放定址法較為節(jié)省空間，而若將節(jié)省的指針空間用來擴大散列表的規(guī)模，可使裝填因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度 。 拉鏈法解決沖突 拉鏈法的缺點 第 八 章 查 找 散列表類型說明： define NIL 1 define M 997 typedef struct{ KeyType key； InfoType otherinfo； }NodeType； Typedef NodeType HashTable[m]； 第 八 章 查 找 散列表的查找過程和建表過程相似。假設給定的值為 K， 根據(jù)建表時設定的 散列函數(shù) h，計算出散列地址 h(K)，若表中該地址單元為空 (是開放的 )，則查找失??；否則將該地址中的結點與給定值 K比較。若相等則查找成功，否則按建表時設定的處理沖突的方法找下一個地址。如此反復下去 基于開放地址法的查找算法 第 八 章 查 找 開放地址法一般形式的函數(shù)表示 int Hash(Keytype k， int i) { return(h(K)+increment(i))％ m； } 若散列函數(shù)用除余法構造，并假設使用線性探查的開放定址法處理沖突，則上述函數(shù)中的 h(K)和increment(i)可定義為： int h(Keytype K) { return K％ m； } int increment(int i) { return i。 } 求哈希函數(shù)值的算法 第 八 章 查 找 int HashSearch(HashTable T， Keytype K， int *pos) { int i=0； do{ *pos=Hash(K， i)； /*求探查地址 hi*/ if(T[*pos].key==K) return l； /*查找成功返回 */ if(T[*pos].key==NIL) return 0； /*查找到空結點返回 */ }while(++im) /*最多做 m次探查， m是表長 */ return 1； /*表滿且未找到時，查找失敗 */ } 通用的開放定址法的散列表 查找算法 ： 第 八 章 查 找 基于開放地址法的插入及建表 void Hashlnsert(HashTable T， NodeTypene w) {/*將新結點 new插入散列表 T[0..m1]中 */ int pos， sign； sign=HashSearch(T， ， amp。pos)； /*在表 T中查找 new的插入位置 if(!sign) /*找到一個開放的地址 pos*/ T[*pos]=new； /*插入新結點 new，插入成功 */ else /*插入失敗 */ if(sign0) printf(“duplicate key!”)； /* 有 重復的關鍵字 */ else Error(hashtableoverflow!)； /*表滿錯誤，終止程序執(zhí)行 */ } 第 八 章 查 找 void CrHTable(HashTable T， NodeType A[ ]， int n) { /*根據(jù) A[0..n1]中結點建立散列表 T[0..m1] */ int i； if(nm) /*用開放定址法處理沖突，裝填因子 (α=n/m)1*/ Error(Load factor1)； for(i=0。im； i++) T[i].key=NULL； /*將各關鍵字清空，使地址 i為開放地址 */ for(i=0。in； i++) /*依次將 A[0..n1]插入到散列表 T[0..m1]中 */ Hashlnsert(T， A[i])； /*調(diào)用插入算法，將 A[i]插入哈希表Ｔ中＊／ } 建哈希表 第 八 章 查 找 基于開放定址法的散列表不宜執(zhí)行散列表的刪除操作。若必須在散列表中刪除結點，則不能將被刪結點的關鍵字置為 UNLL，而應該將其置為特定的標記 DELETED。 刪除 第 八 章 查 找 插入 和 刪除 的時間均取決于查找，故下面只分析查找操作的時間性能。 雖然散列表在關鍵字和存儲位置之間建立了對應關系，理想情況是無須關鍵字的比較就可找到待查關鍵字的記錄。但是由于沖突的存在，散列表的查找過程仍是一個和關鍵字比較的過程，不過散列表的平均查找長度比順序查找、二分查找等完全依賴于關鍵字比較的查找要小得多。 性能分析