C#中實現了哈希表數據結構的集合類有：
（1）System.Collections.Hashtable
（2）System.Collections.Generic.Dictionary<TKey,TValue>
前者為一般類型的哈希表，後者是泛型版本的哈希表。Dictionary和Hashtable之間並非只是簡單的泛型和非泛型的區別，兩者使用了完全不同的哈希沖突解決辦法。Dictionary我已經做了動態演示程序，使用的是Window應用程序。雖然Dictionary相對於Hashtable來說，更優美、漂亮，但總覺得如果不給Hashtable也配上動態演示程序，也是一種遺憾。這次使用了Silverlight來制作，原因很簡單，它可以掛在網上讓大家很方便地觀看。
先來看看效果，這裡需要注意，必須安裝Silverlight 2.0 RTW 才能正常運行游戲，下載地址：http://www.microsoft.com/silverlight/resources/install.aspx?v=2.0
程序中的鍵編輯框中只接受整數，因為整數的哈希碼就是整數本身，這可以讓大家更直觀地查看哈希表的變化。如果輸入了非法字符，則會從0至999中隨機抽取一個整數進行添加或刪除操作。
8.3 哈希沖突解決方法
哈希函數的目標是盡量減少沖突，但實際應用中沖突是無法避免的，所以在沖突發生時，必須有相應的解決方案。而發生沖突的可能性又跟以下兩個因素有關：
（1）裝填因子α：所謂裝填因子是指合希表中已存入的記錄數n與哈希地址空間大小m的比值，即 α=n / m ，α越小，沖突發生的可能性就越小；α越大（最大可取1），沖突發生的可能性就越大。這很容易理解，因為α越小，哈希表中空閒單元的比例就越大，所以待插入記錄同已插入的記錄發生沖突的可能性就越小；反之，α越大，哈希表中空閒單元的比例就越小，所以待插入記錄同已插入記錄沖突的可能性就越大；另一方面，α越小，存儲窨的利用率就越低；反之，存儲窨的利用率就越高。為了既兼顧減少沖突的發生，又兼顧提高存儲空間的利用率，通常把α控制在0.6～0.9的范圍之內，C#的HashTable類把α的最大值定為0.72。
（2）與所采用的哈希函數有關。若哈希函數選擇得當，就可使哈希地址盡可能均勻地分布在哈希地址空間上，從而減少沖突的發生；否則，就可能使哈希地址集中於某些區域，從而加大沖突發生的可能性。
沖突解決技術可分為兩大類：開散列法（又稱為鏈地址法）和閉散列法（又稱為開放地址法）。哈希表是用數組實現的一片連續的地址空間，兩種沖突解決技術的區別在於發生沖突的元素是存儲在這片數組的空間之外還是空間之內：
（1）開散列法發生沖突的元素存儲於數組空間之外。可以把“開”字理解為需要另外“開辟”空間存儲發生沖突的元素。
（2）閉散列法發生沖突的元素存儲於數組空間之內。可以把“閉”字理解為所有元素，不管是否有沖突，都“關閉”於數組之中。閉散列法又稱開放地址法，意指數組空間對所有元素，不管是否沖突都是開放的。
8.3.1 閉散列法（開放地址法）
閉散列法是把所有的元素存儲在哈希表數組中。當發生沖突時，在沖突位置的附近尋找可存放記錄的空單元。尋找“下一個”空位的過程稱為探測。上述方法可用如下公式表示：
hi=(h(key)+di)%m i=1，2，…，k (k≤m-1)
其中h(key)為哈希函數；m為哈希表長；di為增量的序列。根據di取值的不同，可以分成幾種探測方法，下面只介紹Hashtable所使用到的雙重散列法。
雙重散列法
雙重散列法又稱二度哈希，是閉散列法中較好的一種方法，它是以關鍵字的另一個散列函數值作為增量。設兩個哈希函數為：h1和h2，則得到的探測序列為：
(h1(key)+h2(key))%m，(h1(key)+2h2(key))%m，(h1(key)+3h2(key))%m，…
其中，m為哈希表長。由此可知，雙重散列法探測下一個開放地址的公式為：
(h1(key) + i * h2(key)) % m (1≤i≤m-1)
定義h2的方法較多，但無采用什麼方法都必須使h2(key)的值和m互素（又稱互質，表示兩數的最大公約數為1，或者說是兩數沒有共同的因子，1除外）才能使發生沖突的同義詞地址均勻地分布在整個哈希表中，否則可能造成同義詞地址的循環計算。若m為素數，則h2取1至m-1之間的任何數均與m互素，因此可以簡單地將h2定義為：
h2(key) = key % (m - 2) + 1
8.4 剖析System.Collections.Hashtable
萬物之母object類中定義了一個GetHashCode()方法，這個方法默認的實現是返回一個唯一的整數值以保證在object的生命期中不被修改。既然每種類型都是直接或間接從object派生的，因此所有對象都可以訪問該方法。自然，字符串或其他類型都能以唯一的數字值來表示。也就是說，GetHashCode()方法使得所有對象的哈希函數構造方法都趨於統一。當然，由於GetHashCode()方法是一個虛方法，你也可以通過重寫這個方法來構造自己的哈希函數。
8.4.1 Hashtable的實現原理
Hashtable使用了閉散列法來解決沖突，它通過一個結構體bucket來表示哈希表中的單個元素，這個結構體中有三個成員：
（1）key ：表示鍵，即哈希表中的關鍵字。
（2）val ：表示值，即跟關鍵字所對應值。
（3）hash_coll ：它是一個int類型，用於表示鍵所對應的哈希碼。
int類型占據32個位的存儲空間，它的最高位是符號位，為“0”時，表示這是一個正整數；為“1”時表示負整數。hash_coll使用最高位表示當前位置是否發生沖突，為“0”時，也就是為正數時，表示未發生沖突；為“1”時，表示當前位置存在沖突。之所以專門使用一個位用於存放哈希碼並標注是否發生沖突，主要是為了提高哈希表的運行效率。關於這一點，稍後會提到。
Hashtable解決沖突使用了雙重散列法，但又跟前面所講的雙重散列法稍有不同。它探測地址的方法如下：
h(key, i) = h1(key) + i * h2(key)
其中哈希函數h1和h2的公式如下：
h1(key) = key.GetHashCode()
h2(key) = 1 + (((h1(key) >> 5) + 1) % (hashsize - 1))
由於使用了二度哈希，最終的h(key, i)的值有可能會大於hashsize，所以需要對h(key, i)進行模運算，最終計算的哈希地址為：
哈希地址 = h(key, i) % hashsize
【注意】：bucket結構體的hash_coll字段所存儲的是h(key, i)的值而不是哈希地址。
哈希表的所有元素存放於一個名稱為buckets（又稱為數據桶）的bucket數組之中，下面演示一個哈希表的數據的插入和刪除過程，其中數據元素使用（鍵，值，哈希碼）來表示。注意，本例假設Hashtable的長度為11，即hashsize = 11，這裡只顯示其中的前5個元素。
（1）插入元素（k1，v1，1）和（k2，v2，2）。
由於插入的兩個元素不存在沖突，所以直接使用h1(key) % hashsize的值做為其哈希碼而忽略了h2(key)。其效果如圖8.6所示。
（2）插入元素（k3，v3，12）
新插入的元素的哈希碼為12，由於哈希表長為11，12 % 11 = 1，所以新元素應該插入到索引1處，但由於索引1處已經被k1占據，所以需要使用h2(key)重新計算哈希碼。
h2(key) = 1 + (((h1(key) >> 5) + 1) % (hashsize - 1))
h2(key) = 1 + ((12 >> 5) + 1) % (11 - 1)) = 2
新的哈希地址為 h1(key) + i * h2(key) = 1 + 1 * 2 = 3，所以k3插入到索引3處。而由於索引1處存在沖突，所以需要置其最高位為“1”。
(10000000000000000000000000000001)2 = (-2147483647)10
最終效果如圖8.7所示。
（3）插入元素（k4，v4，14）
k4的哈希碼為14，14 % 11 = 3，而索引3處已被k3占據，所以使用二度哈希重新計算地址，得到新地址為14。索引3處存在沖突，所以需要置高位為“1”。
(12)10 = (00000000000000000000000000001100)2 高位置“1”後
(10000000000000000000000000001100)2 = (-2147483636)10
最終效果如圖8.8所示。
（4）刪除元素k1和k2
Hashtable在刪除一個存在沖突的元素時（hash_coll為負數），會把這個元素的key指向數組buckets，同時將該元素的hash_coll的低31位全部置“0”而保留最高位，由於原hash_coll為負數，所以最高位為“1”。
(10000000000000000000000000000000)2 = (-2147483648)10
單憑判斷hash_coll的值是否為-2147483648無法判斷某個索引處是否為空，因為當索引0處存在沖突時，它的hash_coll的值同樣也為-2147483648，這也是為什麼要把key指向buckets的原因。這裡把key指向buckets並且hash_coll值為-2147483648的空位稱為“有沖突空位”。如圖8.8所示，當k1被刪除後，索引1處的空位就是有沖突空位。
Hashtable在刪除一個不存在沖突的元素時（hash_coll為正數），會把鍵和值都設為null，hash_coll的值設為0。這種沒有沖突的空位稱為“無沖突空位”，如圖8.9所示，k2被刪除後索引2處就屬於無沖突空位，當一個Hashtable被初始化後，buckets數組中的所有位置都是無沖突空位。
哈希表通過關鍵字查找元素時，首先計算出鍵的哈希地址，然後通過這個哈希地址直接訪問數組的相應位置並對比兩個鍵值，如果相同，則查找成功並返回；如果不同，則根據hash_coll的值來決定下一步操作。當hash_coll為0或正數時，表明沒有沖突，此時查找失敗；如果hash_coll為負數時，表明存在沖突，此時需通過二度哈希繼續計算哈希地址進行查找，如此反復直到找到相應的鍵值表明查找成功，如果在查找過程中遇到hash_coll為正數或計算二度哈希的次數等於哈希表長度則查找失敗。由此可知，將hash_coll的高位設為沖突位主要是為了提高查找速度，避免無意義地多次計算二度哈希的情況。
8.4.2 Hashtable的代碼實現
哈希表的實現較為復雜，為了簡化代碼，本例忽略了部分出錯判斷，在測試時請不要設key值為空。
1 using System;
2 public class Hashtable
3 {
4 private struct bucket
5 {
6 public Object key; //鍵
7 public Object val; //值
8 public int hash_coll; //哈希碼
9 }
10 private bucket[] buckets; //存儲哈希表數據的數組（數據桶）
11 private int count; //元素個數
12 private int loadsize; //當前允許存儲的元素個數
13 private float loadFactor; //填充因子
14 //默認構造方法
15 public Hashtable() : this(0, 1.0f) { }
16 //指定容量的構造方法
17 public Hashtable(int capacity, float loadFactor)
18 {
19 if (!(loadFactor >= 0.1f && loadFactor <= 1.0f))
20 throw new ArgumentOutOfRangeException(
21 "填充因子必須在0.1～1之間");
22 this.loadFactor = loadFactor > 0.72f ? 0.72f : loadFactor;
23 //根據容量計算表長
24 double rawsize = capacity / this.loadFactor;
25 int hashsize = (rawsize > 11) ? //表長為大於11的素數
26 HashHelpers.GetPrime((int)rawsize) : 11;
27 buckets = new bucket[hashsize]; //初始化容器
28 loadsize = (int)(this.loadFactor * hashsize);
29 }
30 public virtual void Add(Object key, Object value) //添加
31 {
32 Insert(key, value, true);
33 }
34 //哈希碼初始化
35 private uint InitHash(Object key,int hashsize,
36 out uint seed,out uint incr)
37 {
38 uint hashcode = (uint)GetHash(key) & 0x7FFFFFFF; //取絕對值
39 seed = (uint)hashcode; //h1
40 incr = (uint)(1 + (((seed >> 5)+1) % ((uint)hashsize-1)));//h2
41 return hashcode; //返回哈希碼
42 }
43 public virtual Object this[Object key] //索引器
44 {
45 get
46 {
47 uint seed; //h1
48 uint incr; //h2
49 uint hashcode = InitHash(key, buckets.Length,
50 out seed, out incr);
51 int ntry = 0; //用於表示h(key,i)中的i值
52 bucket b;
53 int bn = (int)(seed % (uint)buckets.Length); //h(key,0)
54 do
55 {
56 b = buckets[bn];
57 if (b.key == null) //b為無沖突空位時
58 { //找不到相應的鍵，返回空
59 return null;
60 }
61 if (((b.hash_coll & 0x7FFFFFFF) == hashcode) &&
62 KeyEquals(b.key, key))
63 { //查找成功
64 return b.val;
65 }
66 bn = (int)(((long)bn + incr) %
67 (uint)buckets.Length); //h(key+i)
68 } while (b.hash_coll < 0 && ++ntry < buckets.Length);
69 return null;
70 }
71 set
72 {
73 Insert(key, value, false);
74 }
75 }
76 private void expand() //擴容
77 { //使新的容量為舊容量的近似兩倍
78 int rawsize = HashHelpers.GetPrime(buckets.Length * 2);
79 rehash(rawsize);
80 }
81 private void rehash(int newsize) //按新容量擴容
82 {
83 bucket[] newBuckets = new bucket[newsize];
84 for (int nb = 0; nb < buckets.Length; nb++)
85 {
86 bucket oldb = buckets[nb];
87 if ((oldb.key != null) && (oldb.key != buckets))
88 {
89 putEntry(newBuckets, oldb.key, oldb.val,
90 oldb.hash_coll & 0x7FFFFFFF);
91 }
92 }
93 buckets = newBuckets;
94 loadsize = (int)(loadFactor * newsize);
95 return;
96 }
97 //在新數組內添加舊數組的一個元素
98 private void putEntry(bucket[] newBuckets, Object key,
99 Object nvalue, int hashcode)
100 {
101 uint seed = (uint)hashcode; //h1
102 uint incr = (uint)(1 + (((seed >> 5) + 1) %
103 ((uint)newBuckets.Length - 1))); //h2
104 int bn = (int)(seed % (uint)newBuckets.Length);//哈希地址
105 do
106 { //當前位置為有沖突空位或無沖突空位時都可添加新元素
107 if ((newBuckets[bn].key == null) ||
108 (newBuckets[bn].key == buckets))
109 { //賦值
110 newBuckets[bn].val = nvalue;
111 newBuckets[bn].key = key;
112 newBuckets[bn].hash_coll |= hashcode;
113 return;
114 }
115 //當前位置已存在其他元素時
116 if (newBuckets[bn].hash_coll >= 0)
117 { //置hash_coll的高位為1
118 newBuckets[bn].hash_coll |=
119 unchecked((int)0x80000000);
120 }
121 //二度哈希h1(key)+h2(key)
122 bn = (int)(((long)bn + incr) % (uint)newBuckets.Length);
123 } while (true);
124 }
125 protected virtual int GetHash(Object key)
126 { //獲取哈希碼
127 return key.GetHashCode();
128 }
129 protected virtual bool KeyEquals(Object item, Object key)
130 { //用於判斷兩key是否相等
131 return item == null ? false : item.Equals(key);
132 }
133 //當add為true時用作添加元素，當add為false時用作修改元素值
134 private void Insert(Object key, Object nvalue, bool add)
135 { //如果超過允許存放元素個數的上限則擴容
136 if (count >= loadsize)
137 {
138 expand();
139 }
140 uint seed; //h1
141 uint incr; //h2
142 uint hashcode = InitHash(key, buckets.Length,out seed, out incr);
143 int ntry = 0; //用於表示h(key,i)中的i值
144 int emptySlotNumber = -1; //用於記錄空位
145 int bn = (int)(seed % (uint)buckets.Length); //索引號
146 do
147 { //如果是有沖突空位，需繼續向後查找以確定是否存在相同的鍵
148 if (emptySlotNumber == -1 && (buckets[bn].key == buckets) &&
149 (buckets[bn].hash_coll < 0))
150 {
151 emptySlotNumber = bn;
152 }
153 if (buckets[bn].key == null) //確定沒有重復鍵才添加
154 {
155 if (emptySlotNumber != -1) //使用之前的空位
156 bn = emptySlotNumber;
157 buckets[bn].val = nvalue;
158 buckets[bn].key = key;
159 buckets[bn].hash_coll |= (int)hashcode;
160 count++;
161 return;
162 }
163 //找到重復鍵
164 if (((buckets[bn].hash_coll & 0x7FFFFFFF)==hashcode) &&
165 KeyEquals(buckets[bn].key, key))
166 { //如果處於添加元素狀態，則由於出現重復鍵而報錯
167 if (add)
168 {
169 throw new ArgumentException("添加了重復的鍵值！");
170 }
171 buckets[bn].val = nvalue; //修改批定鍵的元素
172 return;
173 }
174 //存在沖突則置hash_coll的最高位為1
175 if (emptySlotNumber == -1)
176 {
177 if (buckets[bn].hash_coll >= 0)
178 {
179 buckets[bn].hash_coll |= unchecked((int)0x80000000);
180 }
181 }
182 bn = (int)(((long)bn + incr) % (uint)buckets.Length);//二度哈希
183 } while (++ntry < buckets.Length);
184 throw new InvalidOperationException("添加失敗！");
185 }
186 public virtual void Remove(Object key) //移除一個元素
187 {
188 uint seed; //h1
189 uint incr; //h2
190 uint hashcode = InitHash(key, buckets.Length,out seed, out incr);
191 int ntry = 0; //h(key,i)中的i
192 bucket b;
193 int bn = (int)(seed % (uint)buckets.Length); //哈希地址
194 do
195 {
196 b = buckets[bn];
197 if (((b.hash_coll & 0x7FFFFFFF) == hashcode) &&
198 KeyEquals(b.key, key)) //如果找到相應的鍵值
199 { //保留最高位，其余清0
200 buckets[bn].hash_coll &= unchecked((int)0x80000000);
201 if (buckets[bn].hash_coll != 0) //如果原來存在沖突
202 { //使key指向buckets
203 buckets[bn].key = buckets;
204 }
205 else //原來不存在沖突
206 { //置key為空
207 buckets[bn].key = null;
208 }
209 buckets[bn].val = null; //釋放相應的“值”。
210 count--;
211 return;
212 } //二度哈希
213 bn = (int)(((long)bn + incr) % (uint)buckets.Length);
214 } while (b.hash_coll < 0 && ++ntry < buckets.Length);
215 }
216 public override string ToString()
217 {
218 string s = string.Empty;
219 for (int i = 0; i < buckets.Length; i++)
220 {
221 if (buckets[i].key != null && buckets[i].key != buckets)
222 { //不為空位時打印索引、鍵、值、hash_coll
223 s += string.Format("{0,-5}{1,-8}{2,-8}{3,-8}\r\n",
224 i.ToString(), buckets[i].key.ToString(),
225 buckets[i].val.ToString(),
226 buckets[i].hash_coll.ToString());
227 }
228 else
229 { //是空位時則打印索引和hash_coll
230 s += string.Format("{0,-21}{1,-8}\r\n", i.ToString(),
231 buckets[i].hash_coll.ToString());
232 }
233 }
234 return s;
235 }
236 public virtual int Count //屬性
237 { //獲取元素個數
238 get { return count; }
239 }
240 }
Hashtable和ArrayList的實現有似的地方，比如兩者都是以數組為基礎做進一步地抽象而來，兩者都可以成倍地自動擴展容量。
