摘要：
本章介紹了散清單（hash table）的概念、散列函數的設計及散列沖突的處理。散清單類似與字典的目錄，查找的元素都有一個key與之對應，在實踐當中，散列技術的效率是很高的，合理的設計散函數和沖突處理方法，可以使得在散清單中查找一個元素的期望時間為O(1)。散清單是普通數組概念的推廣，在散清單中，不是直接把關鍵字用作數組下标，而是根據關鍵字通過散列函數計算出來的。書中介紹散清單非常注重推理和證明，看的時候迷迷糊糊的，再次證明了數學真的很重要。在STL中map容器的功能就是散清單的功能，但是map采用的是紅黑樹實作的，後面接着學習，關于map的操作可以參考：http://www.cplusplus.com/reference/map/。
1、直接尋址表
當關鍵字的的全域（範圍）U比較小的時，直接尋址是簡單有效的技術，一般可以采用數組實作直接尋址表，數組下标對應的就是關鍵字的值，即具有關鍵字k的元素被放在直接尋址表的槽k中。直接尋址表的字典操作實作比較簡單，直接操作數組即可以，隻需O(1)的時間。
2、散清單
直接尋址表的不足之處在于當關鍵字的範圍U很大時，在計算機記憶體容量的限制下，構造一個存儲|U|大小的表不太實際。當存儲在字典中的關鍵字集合K比所有可能的關鍵字域U要小的多時，散清單需要的存儲空間要比直接尋址表少的很多。散清單通過散列函數h計算出關鍵字k在槽的位置。散列函數h将關鍵字域U映射到散清單T[0....m-1]的槽位上。即h:U->{0,1...,m-1}。采用散列函數的目的在于縮小需要處理的小标範圍，進而降低了空間的開銷。
散清單存在的問題：兩個關鍵字可能映射到同一個槽上，即碰撞（collision）。需要找到有效的辦法來解決碰撞。
3、散列函數
好的散列函數的特點是每個關鍵字都等可能的散列到m個槽位上的任何一個中去，并與其他的關鍵字已被散列到哪一個槽位無關。多數散列函數都是假定關鍵字域為自然數N={0,1,2,....}，如果給的關鍵字不是自然數，則必須有一種方法将它們解釋為自然數。例如對關鍵字為字元串時，可以通過将字元串中每個字元的ASCII碼相加，轉換為自然數。書中介紹了三種設計方案：除法散列法、乘法散法和全域散列法。
（1）除法散列法
散列函數為：h(k)=k mod m
（2）乘法散列法
這個方法看的時候不是很明白，沒有搞清楚什麼意思，先将基本的思想記錄下來，日後好好消化一下。乘法散列法構造散列函數需要兩個步驟。第一步，用關鍵字k乘上常數A（0<A<1），并抽取kA的小數部分。然後，用m乘以這個值，再取結果的底。散列函數如下：h(k) = m(kA mod 1)。
（3）全域散列
給定一組散列函數H，每次進行散列時候從H中随機的選擇一個散列函數h，使得h獨立于要存儲的關鍵字。全域散列函數類的平均性能是比較好的。
4、碰撞處理
通常有兩類方法處理碰撞：開放尋址(Open Addressing)法和連結(Chaining)法。前者是将所有結點均存放在散清單T[0..m-1]中；後者通常是把散列到同一槽中的所有元素放在一個連結清單中，而将此連結清單的頭指針放在散清單T[0..m-1]中。
(1)開放尋址法
所有的元素都在散清單中，每一個表項或包含動态集合的一個元素，或包含NIL。這種方法中散清單可能被填滿，以緻于不能插入任何新的元素。在開放尋址法中，當要插入一個元素時，可以連續地檢查或探測散清單的各項，直到有一個空槽來放置待插入的關鍵字為止。有三種技術用于開放尋址法：線性探測、二次探測以及雙重探測。
<1>線性探測
給定一個普通的散列函數h'：U —>{0，1，.....，m-1}，線性探測方法采用的散列函數為：h(k,i) = (h'(k)+i)mod m，i=0,1,....,m-1
探測時從i=0開始，首先探查T[h'(k)]，然後依次探測T[h'(k)+1]，…，直到T[h'(k)+m-1]，此後又循環到T[0]，T[1]，…，直到探測到T[h'(k)-1]為止。探測過程終止于三種情況：
(1)若目前探測的單元為空，則表示查找失敗（若是插入則将key寫入其中）；
(2)若目前探測的單元中含有key，則查找成功，但對于插入意味着失敗；
(3)若探測到T[h'(k)-1]時仍未發現空單元也未找到key，則無論是查找還是插入均意味着失敗(此時表滿)。
線性探測方法較容易實作，但是存在一次群集問題，即連續被占用的槽的序列變的越來越長。采用例子進行說明線性探測過程，已知一組關鍵字為(26，36，41，38，44，15，68，12，6，51)，用除餘法構造散列函數，初始情況如下圖所示：
散列過程如下圖所示：
<2>二次探測
二次探測法的探查序列是：h(k,i) =(h'(k)+i*i)％m ,0≤i≤m-1 。初次的探測位置為T[h'(k)]，後序的探測位置在次基礎上加一個偏移量，該偏移量以二次的方式依賴于i。該方法的缺陷是不易探查到整個散列空間。
<3>雙重散列
該方法是開放尋址的最好方法之一，因為其産生的排列具有随機選擇的排列的許多特性。采用的散列函數為：h(k,i)=(h1(k)+ih2(k)) mod m。其中h1和h2為輔助散列函數。初始探測位置為T[h1(k)]，後續的探測位置在此基礎上加上偏移量h2(k)模m。
（2）連結法
将所有關鍵字為同義詞的結點連結在同一個連結清單中。若標明的散清單長度為m，則可将散清單定義為一個由m個頭指針組成的指針數組T[0..m-1]。凡是散列位址為i的結點，均插入到以T[i]為頭指針的單連結清單中。T中各分量的初值均應為空指針。在拉鍊法中，裝填因子α可以大于1，但一般均取α≤1。
舉例說明連結法的執行過程，設有一組關鍵字為(26，36，41，38，44，15，68，12，6，51)，用除餘法構造散列函數，初始情況如下圖所示：
最終結果如下圖所示：
5、字元串散列
通常都是将元素的key轉換為數字進行散列，如果key本身就是整數，那麼散列函數可以采用keymod tablesize（要保證tablesize是質數）。而在實際工作中經常用字元串作為關鍵字，例如身姓名、職位等等。這個時候需要設計一個好的散列函數程序處理關鍵字為字元串的元素。參考《資料結構與算法分析》第5章，有以下幾種處理方法：
方法1：将字元串的所有的字元的ASCII碼值進行相加，将所得和作為元素的關鍵字。設計的散列函數如下所示：
1 int hash(const string& key,int tablesize)
2 {
3 int hashVal = 0;
4 for(int i=0;i<key.length();i++)
5 hashVal += key[i];
6 return hashVal % tableSize;
7 此方法的缺點是不能有效的分布元素，例如假設關鍵字是有8個字母構成的字元串，散清單的長度為10007。字母最大的ASCII碼為127，按照方法1可得到關鍵字對應的最大數值為127×8=1016，也就是說通過散列函數映射時隻能映射到散清單的槽0-1016之間，這樣導緻大部分槽沒有用到，分布不均勻，進而效率低下。
方法2：假設關鍵字至少有三個字母構成，散列函數隻是取前三個字母進行散列。設計的散列函數如下所示：
1 int hash(const string& key,int tablesize)
2 {
3 //27 represents the number of letters plus the blank
4 return (key[0]+27*key[1]+729*key[2])%tablesize;
5 該方法隻是取字元串的前三個字元的ASCII碼進行散列，最大的得到的數值是2851，如果散列的長度為10007，那麼隻有28%的空間被用到，大部分空間沒有用到。是以如果散清單太大，就不太适用。
方法3：借助Horner's 規則，構造一個質數（通常是37）的多項式，（非常的巧妙，不知道為何是37）。計算公式為:key[keysize-i-1]37^i,0<=i<keysize求和。設計的散列函數如下所示：
1 int hash(const string & key,int tablesize)
2 {
3 int hashVal = 0;
4 for(int i =0;i<key.length();i++)
5 hashVal = 37*hashVal + key[i];
6 hashVal %= tableSize;
7 if(hashVal<0) //計算的hashVal溢出
8 hashVal += tableSize;
9 return hashVal;
10 該方法存在的問題是如果字元串關鍵字比較長，散列函數的計算過程就變長，有可能導緻計算的hashVal溢出。針對這種情況可以采取字元串的部分字元進行計算，例如計算偶數或者奇數位的字元。
6、再散列（rehashing）
如果散清單滿了，再往散清單中插入新的元素時候就會失敗。這個時候可以通過建立另外一個散清單，使得新的散清單的長度是目前散清單的2倍多一些，重新計算各個元素的hash值，插入到新的散清單中。再散列的問題是在什麼時候進行最好，有三種情況可以判斷是否該進行再散列：
（1）當散清單将快要滿了，給定一個範圍，例如散列被中已經被用到了80%，這個時候進行再散列。
（2）當插入一個新元素失敗時候，進行再散列。
（3）根據裝載因子（存放n個元素的、具有m個槽位的散清單T，裝載因子α=n/m，即每個鍊子中的平均存儲的元素數目）進行判斷，當裝載因子達到一定的門檻值時候，進行在散列。
在采用連結法處理碰撞問題時，采用第三種方法進行在散列效率最好。
7、執行個體練習
看完書後，有一股想把hash表實作的沖動。在此設計的散清單針對的是關鍵字為字元串的元素，采用字元串散列函數方法3進行設計散列函數，采用連結方法處理碰撞，然後采用根據裝載因子（指定為1，同時将n個元素映射到一個連結清單上，即n==m時候）進行再散列。采用C++，借助vector和list，設計的hash表架構如下：
1 template <class T>
2 class HashTable
3 {
4 public:
5 HashTable(int size = 101);
6 int insert(const T& x);
7 int remove(const T& x);
8 int contains(const T& x);
9 void make_empty();
10 void display()const;
11 private:
12 vector<list<T> > lists;
13 int currentSize;//目前散清單中元素的個數
14 int hash(const string& key);
15 int myhash(const T& x);
16 void rehash();
17 實作的完整程式如下所示：
1 #include <iostream>
2 #include <vector>
3 #include <list>
4 #include <string>
5 #include <cstdlib>
6 #include <cmath>
7 #include <algorithm>
8 using namespace std;
9
10 int nextPrime(const int n);
11
12 template <class T>
13 class HashTable
14 {
15 public:
16 HashTable(int size = 101);
17 int insert(const T& x);
18 int remove(const T& x);
19 int contains(const T& x);
20 void make_empty();
21 void display()const;
22 private:
23 vector<list<T> > lists;
24 int currentSize;
25 int hash(const string& key);
26 int myhash(const T& x);
27 void rehash();
28 };
29
30 template <class T>
31 HashTable<T>::HashTable(int size)
32 {
33 lists = vector<list<T> >(size);
34 currentSize = 0;
35 }
36
37 template <class T>
38 int HashTable<T>::hash(const string& key)
39 {
40 int hashVal = 0;
41 int tableSize = lists.size();
42 for(int i=0;i<key.length();i++)
43 hashVal = 37*hashVal+key[i];
44 hashVal %= tableSize;
45 if(hashVal < 0)
46 hashVal += tableSize;
47 return hashVal;
48 }
49
50 template <class T>
51 int HashTable<T>:: myhash(const T& x)
52 {
53 string key = x.getName();
54 return hash(key);
55 }
56 template <class T>
57 int HashTable<T>::insert(const T& x)
58 {
59 list<T> &whichlist = lists[myhash(x)];
60 if(find(whichlist.begin(),whichlist.end(),x) != whichlist.end())
61 return 0;
62 whichlist.push_back(x);
63 currentSize = currentSize + 1;
64 if(currentSize > lists.size())
65 rehash();
66 return 1;
67 }
68
69 template <class T>
70 int HashTable<T>::remove(const T& x)
71 {
72
73 typename std::list<T>::iterator iter;
74 list<T> &whichlist = lists[myhash(x)];
75 iter = find(whichlist.begin(),whichlist.end(),x);
76 if( iter != whichlist.end())
77 {
78 whichlist.erase(iter);
79 currentSize--;
80 return 1;
81 }
82 return 0;
83 }
84
85 template <class T>
86 int HashTable<T>::contains(const T& x)
87 {
88 list<T> whichlist;
89 typename std::list<T>::iterator iter;
90 whichlist = lists[myhash(x)];
91 iter = find(whichlist.begin(),whichlist.end(),x);
92 if( iter != whichlist.end())
93 return 1;
94 return 0;
95 }
96
97 template <class T>
98 void HashTable<T>::make_empty()
99 {
100 for(int i=0;i<lists.size();i++)
101 lists[i].clear();
102 currentSize = 0;
103 return 0;
104 }
105
106 template <class T>
107 void HashTable<T>::rehash()
108 {
109 vector<list<T> > oldLists = lists;
110 lists.resize(nextPrime(2*lists.size()));
111 for(int i=0;i<lists.size();i++)
112 lists[i].clear();
113 currentSize = 0;
114 for(int i=0;i<oldLists.size();i++)
115 {
116 typename std::list<T>::iterator iter = oldLists[i].begin();
117 while(iter != oldLists[i].end())
118 insert(*iter++);
119 }
120 }
121 template <class T>
122 void HashTable<T>::display()const
123 {
124 for(int i=0;i<lists.size();i++)
125 {
126 cout<<i<<": ";
127 typename std::list<T>::const_iterator iter = lists[i].begin();
128 while(iter != lists[i].end())
129 {
130 cout<<*iter<<" ";
131 ++iter;
132 }
133 cout<<endl;
134 }
135 }
136 int nextPrime(const int n)
137 {
138 int ret,i;
139 ret = n;
140 while(1)
141 {
142 int flag = 1;
143 for(i=2;i<sqrt(ret);i++)
144 if(ret % i == 0)
145 {
146 flag = 0;
147 break;
148 }
149 if(flag == 1)
150 break;
151 else
152 {
153 ret = ret +1;
154 continue;
155 }
156 }
157 return ret;
158 }
159
160 class Employee
161 {
162 public:
163 Employee(){}
164 Employee(const string n,int s=0):name(n),salary(s){ }
165 const string & getName()const { return name; }
166 bool operator == (const Employee &rhs) const
167 {
168 return getName() == rhs.getName();
169 }
170 bool operator != (const Employee &rhs) const
171 {
172 return !(*this == rhs);
173 }
174 friend ostream& operator <<(ostream& out,const Employee& e)
175 {
176 out<<"("<<e.name<<","<<e.salary<<") ";
177 return out;
178 }
179 private:
180 string name;
181 int salary;
182 };
183
184 int main()
185 {
186 Employee e1("Tom",6000);
187 Employee e2("Anker",7000);
188 Employee e3("Jermey",8000);
189 Employee e4("Lucy",7500);
190 HashTable<Employee> emp_table(13);
191
192 emp_table.insert(e1);
193 emp_table.insert(e2);
194 emp_table.insert(e3);
195 emp_table.insert(e4);
196
197 cout<<"Hash table is: "<<endl;
198 emp_table.display();
199 if(emp_table.contains(e4) == 1)
200 cout<<"Tom is exist in hash table"<<endl;
201 if(emp_table.remove(e1) == 1)
202 cout<<"Removing Tom form the hash table successfully"<<endl;
203 if(emp_table.contains(e1) == 1)
204 cout<<"Tom is exist in hash table"<<endl;
205 else
206 cout<<"Tom is not exist in hash table"<<endl;
207 //emp_table.display();
208 exit(0);
209 程式測試結果如下所示：