11.1?直接尋址表
當關鍵字的全域U很小，可采用直接尋址的方式。假設動態集合S的元素都取自全域U={0, 1, ..., m-1}的一個關鍵字，并且沒有兩個元素具有相同的關鍵字。
為表示動態集合，使用直接尋址表（diret-address table），記為T[0...m-1]，其中的每個位置稱為槽(slot)。直接尋找表就是按照數組索引，缺點明顯。基本操作如下：

1 DIRECT-ADDRESS-SEARCH(T, k) 2 return T[k] 3 4 DIRECT-ADDRESS-INSERT(T, x) 5 T[x.key] = x 6 7 DIRECT-ADDRESS-DELETE(T, x) 8 T[x.key] = NULL

11.1-4?在大數組上以直接尋址的方式實現字典，并保證每個存儲對象占用O(1)的空間，SEARCH、DELETE、INSERT的操作時間均為O(1)；并且數據結構初始化的時間為O(1)。
思路：不妨設動態幾何包含n個關鍵字，覆蓋{0,1...m-1}的全域范圍。則輔助數組的大小被限定為n，而大數組則>>m。不難想到可以利用棧來存入關鍵字，但是這樣SEARCH、INSERT、DELETE操作無法達到O(1)。
因此，換個思路，將關鍵字存儲在棧里面，而大數組則保存棧的位置。通過關鍵字匹配以及棧頂與數組中位置的大小可以確定唯一的元素。
代碼實現如下：

1 int T[MAXN]; 2 int stack[MAXM], top=0; 3 4 int Direct_Address_Search(int T[], int k) { 5 if (T[k]>=0 && T[k]<top && stack[T[k]]==k) 6 return T[k]; 7 return -1; 8 } 9 10 void Direct_Address_Insert(int T[], int k) { 11 T[k] = top; 12 stack[top++] = k; 13 } 14 15 void Direct_Address_Delete(int T[], int x) { 16 if (x < 0) 17 return ; 18 --top; 19 T[stack[top]] = x; 20 stack[x] = stack[top]; 21 }

11.2?散列表
散列表即哈希，利用散列函數(hash function)h，由關鍵字k計算出槽的位置。函數h將關鍵字的全域U映射到散列表T[0...m-1]的槽位上：
　　h: U -> {0,1,...,m-1}
這里的散列表的大小m一般要比|U|小得多。當然，這就會引發一個問題：兩個關鍵字可能會映射到一個槽中。我們稱這種情形為沖突(collision)。

通過鏈接法解決沖突
鏈接法，即把散列到同一槽中的所有元素都放在一個鏈表中。給定一個能存放n個元素的、具有m個槽位的散列表T，定義T的裝載因子(load factor)α為n/m，即一個鏈的平均存儲元素數。
散列方法的平均性能依賴于所選取的散列函數h，將所有的關鍵字集合等可能地散列到m個槽中的任何一個，且與其他元素被散列到什么位置上無關。我們稱這個散列為簡單均勻散列(simple uniform hashing)。
對于j=0,1,...,m-1，列表T[j]的長度用n_j表示，于是有n =?n_0 + n_1 + ... + n_(m-1)，并且n_j的期望值為E[n_j] = α =?n/m。
定理11.1?在簡單均勻散列的假設下，對于用鏈接法解決沖突的散列表，一次不成功查找的平均時間為Θ(1+α)。
定理11.2?在簡單均勻散列的假設下，對于用鏈接法解決沖突的散列表，一次不成功查找的平均時間為Θ(1+α)。
這也意味著如果散列表中槽數至少與表中的元素數成正比，則有n=O(m)，從而α =?n/m = O(m)/m = O(1)。所以，查找操作平均需要O(1)的時間，當鏈表采用雙向鏈表時，插入操作在最壞情況下需要O(1)的時間，刪除操作在最壞情況下也需要O(1)的時間。因而，全部的字典操作可以再O(1)的時間內完成。

11.2-1?n個關鍵字散列到長度為m的數組T中，假設采用均勻散列，期望的沖突數是多少？
解 E[h(k)=h(l), k!=l] = n*(n-1)/2 * 1/m = n(n-1)/2m。
11.2-3 O(1+α/2)
11.2-4
偽代碼如下：

1 #define MAXN 1005 2 #define MAXM 105 3 4 typedef struct Slot_t { 5 bool free; 6 int val; 7 Slot_t *prev, *next; 8 } Slot_t; 9 10 Slot_t T[MAXN]; 11 Slot_t *free; 12 13 int hash(int val) { 14 return (val+1)%MAXM; 15 } 16 17 void init_Slot() { 18 for (int i=0; i<MAXN-1; ++i) { 19 T[i].free = true; 20 if (i) 21 T[i].prev = &T[i-1]; 22 T[i].next = &T[i+1]; 23 } 24 T[0].prev = NULL; 25 T[MAXN-1].free = true; 26 T[MAXN-1].prev = &T[MAXN-2]; 27 T[MAXN-1].next = NULL; 28 free = T[0]; 29 } 30 31 Slot_t *Direct_Address_Search(Slot_t T[], int val) { 32 int key = hash(val); 33 Slot_t *p = &T[key]; 34 35 while ( p!=NULL && !p->free ) { 36 if (p->val == val) 37 return p; 38 p = p->next; 39 } 40 return NULL; 41 } 42 43 void Direct_Address_Insert(Slot_t T[], int val) { 44 if (free == NULL) 45 return ; 46 int key = hash(val); 47 Slot_t *p; 48 49 if (T[key].free) { 50 T[key].val = val; 51 T[key].free = false; 52 // cut the T[key] from the free list 53 if (T[key].prev != NULL) 54 T[key].prev->next = T[key].next; 55 if (T[key].next != NULL) 56 T[key].next->prev = T[key].prev; 57 T[key].prev = T[key].next = NULL; 58 } else { 59 if (hash(T[key].val) != key) { 60 memcpy(free, T[key], sizeof(Slot_t)); 61 T[key].val = val; 62 T[key].prev = T[key].next = NULL; 63 } else { 64 T[free].free = false; 65 T[free].val = val; 66 T[free].prev = &T[key]; 67 T[free].next = T[key].next; 68 if (T[key].next != NULL) 69 T[key].next->prev = &T[free]; 70 T[key].next = &T[free]; 71 } 72 free = free->next; 73 } 74 } 75 76 void Direct_Address_Delete(Slot_t T[], int val) { 77 int key = hash(val); 78 Slot_t *p = Direct_Address_Search(val), *q; 79 80 if (p == NULL) 81 return ; 82 if (p == &T[key]) { 83 if (p->next == NULL) { 84 p->free = true; 85 p->next = free; 86 free = p; 87 } else { 88 // copy p->next to p 89 q = p->next; 90 memcpy(p, p->next, sizeof(Slot_t)); 91 p->prev = NULL; 92 // delete p->next 93 if (p->next != NULL) 94 p->next->prev = p; 95 q->free = true; 96 q->next = free; 97 free = q; 98 } 99 } else { 100 p->free = true; 101 p->prev->next = p->next; 102 if (p->next != NULL) 103 p->next->prev = p->prev; 104 p->next = free; 105 free = p->next; 106 } 107 }

?11.2-6
解：已知n = L_0 + L_1 + ... + L_(m-1), max{L_0, L_1, L_(m-1)} = L。求均勻隨機選擇某一元素的期望。
E[1/n * Sigma(1..n, (L_hash(xi)+1)/2)] = 1/2n * [ Sigma(i=0..(m-1), L_i*L_i) + n] < 1/n * [Sigma(i=0..(m-1), L_i*L_i) + mL] < L/n * [Sigma(i=0..(m-1), L_i) + m] = L/n * (n+m) = L*(1+m/n) = L*(1+1/α) = O(L*(1+1/α))

11.3?散列函數
除法散列與乘法散列本質上屬于啟發式方法，而全域散列則利用了隨機技術來提供可證明的良好性能。
好的散列函數的特點
好的散列函數應（近似地）滿足簡單均勻散列假設：每個關鍵字都被等可能地散列到m個槽位中的任何一個，并與其他關鍵字已散列到哪個槽位無關。
除法散列法
在用來設計散列函數的除法散列法中，通過取k除以m個余數，將關鍵字k映射到m個槽位中的某一個上，即散列函數為：
h(k) = k mod m
一個不太接近2的整數冪的素數，常常是m個一個較好的選擇。
乘法散列法
構造散列函數的乘法散列法包含兩個步驟：第一步，用關鍵字k乘上常數A(0<A<1)，并提取kA的小數部分。第二步，用m乘以這個值，再向下取整。總之，散列函數為：
h(k) = floor(m(kA mod 1))
這里kA mod 1是取kA的小數部分，即kA - ceil(kA)。

11.3-1
由于需要在長度為n的鏈表中搜索，因此先計算源串的hash(key)，再用這個值不斷與鏈表中元素的hash(key)值進行比較，若相等則返回該節點指針。

11.3-2


11.3-3

11.3-4

1 int hash(int key) { 2 double A = (sqrt(5.0)-1)/2; 3 double tmp = key*A; 4 return (int) ( m*(tmp - (int)tmp) ); 5 }

11.4?開放尋址法
在開放尋址法（open addressing）中，所有的元素存放在散列表里。也就是說，每個表象或包含動態集合的一個元素，或包含NIL。當查找某個元素時，要系統地檢查所有的表項，直到找到所需的元素，或者最終查明該元素不在表中。不像鏈接法，這里既沒有鏈表，也沒有元素存在散列表外。因此在開放尋址法中，散列表可能被填滿。為了使用開放尋址法插入一個元素，需要連續地檢查散列表，或稱為探查（probe）。有三種主要的探查方法：
線性探查
給定一個普通的散列函數h'：U -> {0, 1, ..., m-1},?稱之為輔助散列函數（auxiliary?hash），線性探查（linear?probing）方法采用的散列函數為：
h(k, i) = (h'(k) + i) mod m, i = 0, 1, ..., m-1
給定一個關鍵字k，首先探查T[h'(k)]，即由輔助散列函數所給出的槽位。再探查槽T[h'(k)+1]，以此類推，直至槽T[m-1].然后，又繞到T[0], T[1], T[0], ...,?直到最后探查到T[h'(k)-1]。在線性探查方法中，初始探查位置決定了整個序列，故只有m種不同的探查序列。
線性探查方法比較容易實現，但它存在一個問題，稱為一次群集（primary cluster）。隨著連續被占用的槽不斷增加，平均查找時間也隨之不斷增加。群集現象很容易出現，這是因為當一個空槽前有i個滿的槽時，該空槽為下一個將被占用的概率是(i+1)/m。連續被占用的槽就會越來越長，因而平均查找時間也會越來越大。
二次探查
二次探查（quadratic?probing）采用如下形式的散列函數：

其中h’是一個輔助散列函數，c1和c2為正的輔助常數。初始的探查位置為T[h'(k)],后續的探查位置要加上一個偏移量，該偏移量以二次的方式依賴于探查序號i。這種探查方法的效果要比線性探查好得多。此外，如果兩個關鍵字的初始探查位置相同，那么它們的探查序列也是相同的，這是因為h(k1, 0) = h(k2, 0)蘊含著h(k1,?i) = h(k2, i)。這一性質可能導致一種輕度的群集，稱為二次群集（secondary?cluster）。像在線性探查中一樣，初始探查位置決定了整個序列，這樣也僅有m個不同的探查序列被用到。
雙重散列
雙重散列（double?hashing）是用于開放尋址法的最好方法之一，因為它所產生的排列具有隨機選擇排列的許多特性。雙重散列采用如下形式的散列函數：

其中h1和h2均為輔助散列函數。初始探查位置為T[h1(k)]，后續的探查位置是前一個位置加上偏移量h2(k)摸m。
定理11.6? 給定一個裝載因子為α=n/m<1的開放尋址散列表，并假設是均勻散列的，則對于一次不成功的查找，其期望的探查次數最多為1/(1-α)。
推論11.7??假設采用的是均勻散列，平均情況下，向一個裝載因子為α的開放尋址散列表中插入一個元素至多需要做1/(1-α)次探查。
定理11.8?對于一個裝載因子為α<1的開放尋址散列表，一次成功查找中的探查期望數至多為(1/α)ln(1/(1-α))

11.4-1
線性探查? 32 88? -? -?? 4 15 28 17 59 31 10
二次探查? 22 -? 88 17 4? -?? 28 59 15 31 10
雙重散列? 22 -? 59 17 4? 15 28 88? -? 31 10

11.4-2

1 HASH-INSERT(T, k) 2 i = 0 3 repeat 4 j = h(k, i) 5 if T[j]==NIL or T[j]==DELETED 6 T[j] = k; 7 return j 8 else i = i + 1 9 until i==m 10 error "hash table overflow" 11 12 HASH_DELETE(T, k) 13 i = HASH_SEARCH(T, k) 14 if i!=NIL 15 T[i] = DELETED

?

轉載于:https://www.cnblogs.com/bombe1013/p/4008722.html

總結

以上是生活随笔為你收集整理的【算法导论】学习笔记——第11章 散列表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。