# 一、概念 ### 1.綜述 散表表僅支持INSERT、SEARCH、DELETE操作。 把關鍵字k映射到槽h(k)上的過程稱為散列。 多個關鍵字映射到同一個數組下標位置稱為碰撞。 好的散列函數應使每個關鍵字都等可能地散列到m個槽位中 ### 2.散表函數 （1）若函數為h(k)=k，就是直接尋址表  （2）除法散列法：h(k) = k mod m （3）乘法散列法：h(k) = m * (k * A mod 1) (0<A<1) （4）全域散列：從一組仔細設計的散列函數中隨機地選擇一個。（即使對同一個輸入，每次也都不一樣，平均性態較好） 3.沖突解決策略 （1）鏈接法 （2）開放尋址法 a.線性探測：h(k, i) = (h'(k) + i) mod m b.二次探測：h(k, i) = (h'(k) + c1*i + c2 *i^2) mod m c.雙重散列：h(k, i) = (h1(k) + i * h2(k)) mod m （3）完全散列：設計一個較小的二次散列表 # 二、代碼 代碼中用到了函數指針，函數指針的用法參考[函數指針總結](http://blog.csdn.net/mishifangxiangdefeng/article/details/7209060) ~~~ //Hash.h #include <iostream> using namespace std; int m, NIL = 0; //11.4 開放尋址法 typedef int (*Probing)(int k, int i); int h(int k) { return k % m; } int h2(int k) { return 1 + k % (m-1); } //線性探測 int Linear_Probing(int k, int i) { return (h(k) + i) % m; } //二次探測 int Quadratic_Probint(int k, int i) { int c1 = 1, c2 = 3; return (h(k) + c1 * i + c2 * i * i) % m; } //雙重探測 int Double_Probint(int k, int i) { return (h(k) + i * h2(k)) % m; } int Hash_Insert(int *T, int k, Probing p) { int i = 0, j; do{ j = p(k, i); if(T[j] == NIL) { T[j] = k; return j; } i++; } while(i != m); cout<<"error:hash table overflow"<<endl; } int Hash_Search(int *T, int k, Probing p) { int i = 0, j; while(1) { j = p(k, i); if(T[j] == NIL || i == m) break; if(T[j] == k) return j; i++; } } ~~~ # 三、習題 ### 11.1 直接尋址表 ~~~ 11.1-1 O(m)，最壞情況時，集合中只有一個最小關鍵字 11.1-2 如果插入x，就把向量的第x位置為1 如果刪除x，就把向量的第x位置為0 11.1-3 當存在關鍵字為key的衛星數據時，T[key]指向其中一個關鍵字為key的衛星數據。若不存在，T[key]指向空。 每一個衛星數據用一個結點表示，結點中有三個域，分別是：關鍵字key，衛星數據data，指向下一個所有相同關鍵字的衛星數據的指針next DIRECT-ADDRESS-SEARCH(T, k) return T[k]; DIRECT-ADDRESS-INSERT(T, x) if T[key[x]] = NULL then T[key[x]] <- x else next[x] <- next[T[key[x]]] next[T[key[x]]] <- x ~~~ 11.1-4 見[算法導論-11.1-4](http://blog.csdn.net/mishifangxiangdefeng/article/details/7709567) 用一個棧來存儲實際插入的數據，插入時棧向上擴展一個空間，刪除時，用棧頂元素補充被刪除元素的位置，棧向下回收一個空間，方法類似于P127-11.3-4. 這個非常大的數組中不直接存放數據，而是存放數據在Stack中的位置。 對于一個元素p，如果H[p] < 棧中總元素的個數 && p = Stack[H[p]]，就是存入，否則就是不存在 ### 11.2 散列表 11.2-3 所有操作的時間都是O(n/2)，n是一個鏈表的長度 11.2-4 見[算法導論-11.2-4](http://blog.csdn.net/mishifangxiangdefeng/article/details/7712094) 插入操作時，從自由鏈表中取出一個空閑slot，填入關鍵字x，修改指針，鏈表相應的隊列中，具體可以分為以下幾種情況： （1）x所屬的slot未被占用，則 step1：把這個slot從自由鏈表中移出 step2：填入關鍵字x step3：修改指針，在這種情況下其next和pre都置為-1 （2）x所屬的slot已經被占用，令占用這個slot的關鍵是y，y也屬于這個slot，則 step1：從自由鏈表中取出一個空閑的slot，這個slot肯定不是x所屬的slot，只是拿過來用 step2：填入關鍵字x step3：修改指針，把slot鏈表入到“以x所屬的slot為頭結點的隊列”中 （3）x所屬的slot已經被占用，令占用這個slot的關鍵是y，y不屬于這個slot，通過（2）可知，這個情況是有可能的 step1：從自由鏈表中取出一個空閑的slot，這個slot肯定不是x所屬的slot，也不是y所屬的slot，只是拿過來用 step2：在新slot中填入關鍵字y，修改指針，讓y使用這個新slot，而把原來的slot空出來還給x step3：在x所屬的slot中填入關鍵字x step4：修改“x所屬的slot”指針，類似(1)-step3 刪除操作時，令待刪除的關鍵字是x，釋放x所占用的slot，具體可以分為以下幾種情況 （1）x所占用的slot正是x所屬的slot，且slot->next=-1，即所有關鍵字中只有x屬于這個slot，x被刪除后，slot就空閑了 step1：釋放slot到自由鏈表中 （2）x所占用的slot正是x所屬的slot，但還有別的關鍵字中只有x屬于這個slot，應該優先使用關鍵所屬于的slot，而釋放“不自己關鍵字的、臨時拿過來用的”slat step1：從以slot為頭結點的隊列中另選一個slot2，slot2的關鍵字屬于slot而不屬于slot2，只是因為slot被占用，所以才用slot2 step2：把slot2的內容填入slot step3：修改指針，讓slot代替slot2存在于隊列中，不同的是slot還是隊列頭 step4：釋放slot2到自由鏈表中 （3）x所占用的slot不是x所屬的slot，這個種情況下，這個slot一定不是隊列頭，還有別的關鍵字存在于隊列中，并且占用了x所屬的slot step1：把x所占用的slot從“以x所屬的slot為頭的隊列”中移出 step2：釋放slot到自由鏈表中 查找操作，如果理解了插入和刪除，查找操作就比較簡單了，令待查找的關鍵字是x，也可分為幾種情況 （1）x所屬的slot未被占用，即不存在與x相同slot的關鍵字，當然也不存在x了 （2）x所屬的slot被占用了，但它所存的關鍵不屬于這個slot，與（1）相同，不存在與x相同slot的關鍵字 （3）x所屬的slot被占用了，且它所存的關鍵屬于這個slot，即存在與x相同slot的關鍵字，只是不知這個關鍵字是不是x，需要進一步查找 ### 11.3 散列函數 11.3-1 從散列表中的第h(k)個表中搜索關鍵字為k的一項 11.3-2 每處理字符串中的一個字符，就取一次模 11.3-4 ~~~ #include <cmath> int main() { int n; while(cin>>n) { double A = (sqrt(5.0)-1) / 2; double t1 = A * n; int t2 = (int)t1; double t3 = t1 - t2; int t4 = t3 * 1000; cout<<t4<<endl; } } ~~~ h(61) =?700 h(62) =?318 h(63) =?936 h(64) =?554 h(65) =?172 ### 11.4 開放尋址法 11.4-1 線性探測：22 88 0 0 4 15 28 17 59 31 10 二次探測：22 0 88 17 4 0 28 59 15 31 10 雙重探測：22 0 59 17 4 15 28 88 0 31 10 代碼如下：代碼中用到了函數指針，函數指針的用法參考[函數指針總結](http://blog.csdn.net/mishifangxiangdefeng/article/details/7209060) ~~~ #include <iostream> #include <string> #include "Hash.h" using namespace std; void Print(int *T) { int i; for(i = 0; i < m; i++) cout<<T[i]<<' '; cout<<endl; } int main() { string str; int i, j; m = 11; int T[11], A[9] = {10, 22, 31, 4, 15, 28, 17, 88, 59}; Probing P[3] = {Linear_Probing, Quadratic_Probint, Double_Probint}; for(i = 0; i < 3; i++) { memset(T, 0, sizeof(T)); for(j = 0; j < 9; j++) Hash_Insert(T, A[j], P[i]); Print(T); } return 0; } ~~~ 11.4-2 刪除一個元素后，將這個位置置為DELETED，在插入操作中，L3改為if T[j] = NIL or T[j] = DELETED ~~~ #define DELETED -1 int Hash_Insert(int *T, int k, Probing p) { int i = 0, j; do{ j = p(k, i); if(T[j] == NIL || T[j] == DELETED) { T[j] = k; return j; } i++; } while(i != m); cout<<"error:hash table overflow"<<endl; } void Hash_Delete(int *T, int k, Probing p) { int j = Hash_Search(T, k, p); if(j != NIL) T[j] = DELETED; } ~~~