這篇文章主要介紹C#中實現(xiàn)了哈希表數(shù)據(jù)結(jié)構(gòu)的集合類有哪些，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！
創(chuàng)新互聯(lián)公司主要從事網(wǎng)站設(shè)計、成都網(wǎng)站設(shè)計、網(wǎng)頁設(shè)計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)吉安,10余年網(wǎng)站建設(shè)經(jīng)驗,價格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):028-86922220
C#中實現(xiàn)了哈希表數(shù)據(jù)結(jié)構(gòu)的集合類有：
（1） System.Collections.Hashtable
（2） System.Collections.Generic.Dictionary
前者為一般類型的哈希表，后者是泛型版本的哈希表。Dictionary和Hashtable之間并非只是簡單的泛型和非泛型的區(qū)別，兩者使用了完全不同的哈希沖突解決辦法。Dictionary我已經(jīng)做了動態(tài)演示程序，使用的是Window應(yīng)用程序。雖然Dictionary相對于Hashtable來說，更優(yōu)美、漂亮，但總覺得如果不給Hashtable也配上動態(tài)演示程序，也是一種遺憾。這次使用了Silverlight來制作，原因很簡單，它可以掛在網(wǎng)上讓大家很方便地觀看。
先來看看效果，這里需要注意，必須安裝Silverlight 2.0 RTW 才能正常運行游戲，下載地址：http://www.microsoft.com/silverlight/resources/install.aspx?v=2.0
程序中的鍵編輯框中只接受整數(shù)，因為整數(shù)的哈希碼就是整數(shù)本身，這可以讓大家更直觀地查看哈希表的變化。如果輸入了非法字符，則會從0至999中隨機抽取一個整數(shù)進行添加或刪除操作。
哈希沖突解決方法
哈希函數(shù)的目標(biāo)是盡量減少沖突，但實際應(yīng)用中沖突是無法避免的，所以在沖突發(fā)生時，必須有相應(yīng)的解決方案。而發(fā)生沖突的可能性又跟以下兩個因素有關(guān)：
（1） 裝填因子α：所謂裝填因子是指合希表中已存入的記錄數(shù)n與哈希地址空間大小m的比值，即 α=n / m，α越小，沖突發(fā)生的可能性就越?。沪猎酱螅?**可取1），沖突發(fā)生的可能性就越大。這很容易理解，因為α越小，哈希表中空閑單元的比例就越大，所以待插入記錄同已插入的記錄發(fā)生沖突的可能性就越??；反之，α越大，哈希表中空閑單元的比例就越小，所以待插入記錄同已插入記錄沖突的可能性就越大；另一方面，α越小，存儲窨的利用率就越低；反之，存儲窨的利用率就越高。為了既兼顧減少沖突的發(fā)生，又兼顧提高存儲空間的利用率，通常把α控制在0.6～0.9的范圍之內(nèi)，C#的HashTable類把α的***值定為0.72。
（2） 與所采用的哈希函數(shù)有關(guān)。若哈希函數(shù)選擇得當(dāng)，就可使哈希地址盡可能均勻地分布在哈希地址空間上，從而減少沖突的發(fā)生；否則，就可能使哈希地址集中于某些區(qū)域，從而加大沖突發(fā)生的可能性。
沖突解決技術(shù)可分為兩大類：開散列法（又稱為鏈地址法）和閉散列法（又稱為開放地址法）。哈希表是用數(shù)組實現(xiàn)的一片連續(xù)的地址空間，兩種沖突解決技術(shù)的區(qū)別在于發(fā)生沖突的元素是存儲在這片數(shù)組的空間之外還是空間之內(nèi)：
（1） 開散列法發(fā)生沖突的元素存儲于數(shù)組空間之外。可以把“開”字理解為需要另外“開辟”空間存儲發(fā)生沖突的元素。
（2） 閉散列法發(fā)生沖突的元素存儲于數(shù)組空間之內(nèi)?？梢园选伴]”字理解為所有元素，不管是否有沖突，都“關(guān)閉”于數(shù)組之中。閉散列法又稱開放地址法，意指數(shù)組空間對所有元素，不管是否沖突都是開放的。
閉散列法（開放地址法）
閉散列法是把所有的元素存儲在哈希表數(shù)組中。當(dāng)發(fā)生沖突時，在沖突位置的附近尋找可存放記錄的空單元。尋找“下一個”空位的過程稱為探測。上述方法可用如下公式表示：
hi=(h(key)+di)%m i=1，2，…，k (k≤m-1)
其中h(key)為哈希函數(shù)；m為哈希表長；di為增量的序列。根據(jù)di取值的不同，可以分成幾種探測方法，下面只介紹Hashtable所使用到的雙重散列法。
雙重散列法
雙重散列法又稱二度哈希，是閉散列法中較好的一種方法，它是以關(guān)鍵字的另一個散列函數(shù)值作為增量。設(shè)兩個哈希函數(shù)為：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互素（又稱互質(zhì)，表示兩數(shù)的***公約數(shù)為1，或者說是兩數(shù)沒有共同的因子，1除外）才能使發(fā)生沖突的同義詞地址均勻地分布在整個哈希表中，否則可能造成同義詞地址的循環(huán)計算。若m為素數(shù)，則h2取1至m-1之間的任何數(shù)均與m互素，因此可以簡單地將h2定義為：
h2(key) = key % (m - 2) + 1
Hashtable的實現(xiàn)原理
Hashtable使用了閉散列法來解決沖突，它通過一個結(jié)構(gòu)體bucket來表示哈希表中的單個元素，這個結(jié)構(gòu)體中有三個成員：
（1） key：表示鍵，即哈希表中的關(guān)鍵字。
（2） val：表示值，即跟關(guān)鍵字所對應(yīng)值。
（3） hash_coll：它是一個int類型，用于表示鍵所對應(yīng)的哈希碼。
int類型占據(jù)32個位的存儲空間，它的***位是符號位，為“0”時，表示這是一個正整數(shù)；為“1”時表示負整數(shù)。hash_coll使用***位表示當(dāng)前位置是否發(fā)生沖突，為“0”時，也就是為正數(shù)時，表示未發(fā)生沖突；為“1”時，表示當(dāng)前位置存在沖突。之所以專門使用一個位用于存放哈希碼并標(biāo)注是否發(fā)生沖突，主要是為了提高哈希表的運行效率。關(guān)于這一點，稍后會提到。
Hashtable解決沖突使用了雙重散列法，但又跟前面所講的雙重散列法稍有不同。它探測地址的方法如下：
h(key, i) = h1(key) + i * h2(key)
其中哈希函數(shù)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結(jié)構(gòu)體的hash_coll字段所存儲的是h(key, i)的值而不是哈希地址。
哈希表的所有元素存放于一個名稱為buckets（又稱為數(shù)據(jù)桶） 的bucket數(shù)組之中，下面演示一個哈希表的數(shù)據(jù)的插入和刪除過程，其中數(shù)據(jù)元素使用（鍵，值，哈希碼）來表示。注意，本例假設(shè)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，所以新元素應(yīng)該插入到索引1處，但由于索引1處已經(jīng)被k1占據(jù)，所以需要使用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占據(jù)，所以使用二度哈希重新計算地址，得到新地址為14。索引3處存在沖突，所以需要置高位為“1”。
(12)10= (00000000000000000000000000001100)2 高位置“1”后
(10000000000000000000000000001100)2 = (-2147483636)10
最終效果如圖8.8所示。
（4） 刪除元素k1和k2
Hashtable在刪除一個存在沖突的元素時（hash_coll為負數(shù)），會把這個元素的key指向數(shù)組buckets，同時將該元素的hash_coll的低31位全部置“0”而保留***位，由于原h(huán)ash_coll為負數(shù)，所以***位為“1”。
(10000000000000000000000000000000)2 = (-2147483648)10
單憑判斷hash_coll的值是否為-2147483648無法判斷某個索引處是否為空，因為當(dāng)索引0處存在沖突時，它的hash_coll的值同樣也為-2147483648，這也是為什么要把key指向buckets的原因。這里把key指向buckets并且hash_coll值為-2147483648的空位稱為“有沖突空位”。如圖8.8所示，當(dāng)k1被刪除后，索引1處的空位就是有沖突空位。
Hashtable在刪除一個不存在沖突的元素時（hash_coll為正數(shù)），會把鍵和值都設(shè)為null，hash_coll的值設(shè)為0。這種沒有沖突的空位稱為“無沖突空位”，如圖8.9所示，k2被刪除后索引2處就屬于無沖突空位，當(dāng)一個Hashtable被初始化后，buckets數(shù)組中的所有位置都是無沖突空位。
哈希表通過關(guān)鍵字查找元素時，首先計算出鍵的哈希地址，然后通過這個哈希地址直接訪問數(shù)組的相應(yīng)位置并對比兩個鍵值，如果相同，則查找成功并返回；如果不同，則根據(jù)hash_coll的值來決定下一步操作。當(dāng)hash_coll為0或正數(shù)時，表明沒有沖突，此時查找失敗；如果hash_coll為負數(shù)時，表明存在沖突，此時需通過二度哈希繼續(xù)計算哈希地址進行查找，如此反復(fù)直到找到相應(yīng)的鍵值表明查找成功，如果在查找過程中遇到hash_coll為正數(shù)或計算二度哈希的次數(shù)等于哈希表長度則查找失敗。由此可知，將hash_coll的高位設(shè)為沖突位主要是為了提高查找速度，避免無意義地多次計算二度哈希的情況。
Hashtable的代碼實現(xiàn)
哈希表的實現(xiàn)較為復(fù)雜，為了簡化代碼，本例忽略了部分出錯判斷，在測試時請不要設(shè)key值為空
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; //存儲哈希表數(shù)據(jù)的數(shù)組（數(shù)據(jù)桶）
11 private int count; //元素個數(shù)
12 private int loadsize; //當(dāng)前允許存儲的元素個數(shù)
13 private float loadFactor; //填充因子
14 //默認構(gòu)造方法
15 public Hashtable() : this(0, 1.0f) { }
16 //指定容量的構(gòu)造方法
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 //根據(jù)容量計算表長
24 double rawsize = capacity / this.loadFactor;
25 int hashsize = (rawsize > 11) ? //表長為大于11的素數(shù)
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; //h2
40 incr = (uint)(1 + (((seed >> 5)+1) % ((uint)hashsize-1)));//h3
41 return hashcode; //返回哈希碼
42 }
43 public virtual Object this[Object key] //索引器
44 {
45 get
46 {
47 uint seed; //h2
48 uint incr; //h3
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 { //找不到相應(yīng)的鍵，返回空
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 //在新數(shù)組內(nèi)添加舊數(shù)組的一個元素
98 private void putEntry(bucket[] newBuckets, Object key,
99 Object nvalue, int hashcode)
100 {
101 uint seed = (uint)hashcode; //h2
102 uint incr = (uint)(1 + (((seed >> 5) + 1) %
103 ((uint)newBuckets.Length - 1))); //h3
104 int bn = (int)(seed % (uint)newBuckets.Length);//哈希地址
105 do
106 { //當(dāng)前位置為有沖突空位或無沖突空位時都可添加新元素
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 //當(dāng)前位置已存在其他元素時
116 if (newBuckets[bn].hash_coll >= 0)
117 { //置hash_coll的高位為1
118 newBuckets[bn].hash_coll |=
119 unchecked((int)0x80000000);
120 }
121 //二度哈希h2(key)+h3(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 //當(dāng)add為true時用作添加元素，當(dāng)add為false時用作修改元素值
134 private void Insert(Object key, Object nvalue, bool add)
135 { //如果超過允許存放元素個數(shù)的上限則擴容
136 if (count >= loadsize)
137 {
138 expand();
139 }
140 uint seed; //h2
141 uint incr; //h3
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 { //如果是有沖突空位，需繼續(xù)向后查找以確定是否存在相同的鍵
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) //確定沒有重復(fù)鍵才添加
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 //找到重復(fù)鍵
164 if (((buckets[bn].hash_coll & 0x7FFFFFFF)==hashcode) &&
165 KeyEquals(buckets[bn].key, key))
166 { //如果處于添加元素狀態(tài)，則由于出現(xiàn)重復(fù)鍵而報錯
167 if (add)
168 {
169 throw new ArgumentException("添加了重復(fù)的鍵值！");
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; //h2
189 uint incr; //h3
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)) //如果找到相應(yīng)的鍵值
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; //釋放相應(yīng)的“值”。
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 { //獲取元素個數(shù)
238 get { return count; }
239 }
240 }
以上是“C#中實現(xiàn)了哈希表數(shù)據(jù)結(jié)構(gòu)的集合類有哪些”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對大家有幫助，更多相關(guān)知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！
重慶分公司
重慶分公司
