轉(zhuǎn)載：http://www.cnblogs.com/chengxingliang/archive/2013/04/15/3020428.html

在本文中將從基礎(chǔ)角度講解HashTable、Dictionary的構(gòu)造和通過程序進(jìn)行插入讀取對比。

一：HashTable

1.HashTable是一種散列表，他內(nèi)部維護(hù)很多對Key-Value鍵值對，其還有一個類似索引的值叫做散列值(HashCode)，它是根據(jù)GetHashCode方法對Key通過一定算法獲取得到的，所有的查找操作定位操作都是基于散列值來實現(xiàn)找到對應(yīng)的Key和Value值的。

2.我們需要使用一個算法讓散列值對應(yīng)HashTable的空間地址盡量不重復(fù)，這就是散列函數(shù)(GetHashCode)需要做的事。

3.當(dāng)一個HashTable被占用一大半的時候我們通過計算散列值取得的地址值可能會重復(fù)指向同一地址，這就是哈希沖突。

在.Net中鍵值對在HashTable中的位置Position= (HashCode& 0x7FFFFFFF) % HashTable.Length，.net中是通過探測法解決哈希沖突的，當(dāng)通過散列值取得的位置Postion以及被占用的時候，就會增加一個位移x值判斷下一個位置Postion+x是否被占用，如果仍然被占用就繼續(xù)往下位移x判斷Position+2*x位置是否被占用，如果沒有被占用則將值放入其中。當(dāng)HashTable中的可用空間越來越小時，則獲取得到可用空間的難度越來越大，消耗的時間就越多。

4.當(dāng)前HashTable中的被占用空間達(dá)到一個百分比的時候就將該空間自動擴(kuò)容，在.net中這個百分比是72%,也叫.net中HashTable的填充因子為0.72。例如有一個HashTable的空間大小是100，當(dāng)它需要添加第73個值的時候?qū)U(kuò)容此HashTable.

5.這個自動擴(kuò)容的大小是多少呢？答案是當(dāng)前空間大小的兩倍最接近的素數(shù)，例如當(dāng)前HashTable所占空間為素數(shù)71，如果擴(kuò)容，則擴(kuò)容大小為素數(shù)131.

二：Dictionary

1.Dictionary是一種變種的HashTable,它采用一種分離鏈接散列表的數(shù)據(jù)結(jié)構(gòu)來解決哈希沖突的問題。

2.分離鏈接散列表是當(dāng)散列到同一個地址的值存為一個鏈表中。

3.這個變種HashTable的填充因子是1

三：本文將以代碼的形式探索HashTable和Dictionary的插入和三種讀取方式的效率(for/foreach/GetEnumerator)

public class HashTableTest{static Hashtable _Hashtable;static Dictionary<string, object> _Dictionary;static void Main(){Compare(10);Compare(10000);Compare(5000000);Console.ReadLine();}public static void Compare(int dataCount){Console.WriteLine("-------------------------------------------------\n");_Hashtable = new Hashtable();_Dictionary = new Dictionary<string, object>();Stopwatch stopWatch = new Stopwatch();//HashTable插入dataCount條數(shù)據(jù)需要時間stopWatch.Start();for (int i = 0; i < dataCount; i++){_Hashtable.Add("Str" + i.ToString(), "Value");}stopWatch.Stop();Console.WriteLine(" HashTable插入" + dataCount + "條數(shù)據(jù)需要時間：" + stopWatch.Elapsed);//Dictionary插入dataCount條數(shù)據(jù)需要時間stopWatch.Reset();stopWatch.Start();for (int i = 0; i < dataCount; i++){_Dictionary.Add("Str" + i.ToString(), "Value");}stopWatch.Stop();Console.WriteLine(" Dictionary插入" + dataCount + "條數(shù)據(jù)需要時間：" + stopWatch.Elapsed);//Dictionary插入dataCount條數(shù)據(jù)需要時間stopWatch.Reset();int si = 0;stopWatch.Start();for(int i=0;i<_Hashtable.Count;i++){si++;}stopWatch.Stop();Console.WriteLine(" HashTable遍歷時間：" + stopWatch.Elapsed + " ,遍歷采用for方式");//Dictionary插入dataCount條數(shù)據(jù)需要時間stopWatch.Reset();si = 0;stopWatch.Start();foreach (var s in _Hashtable){si++;}stopWatch.Stop();Console.WriteLine(" HashTable遍歷時間：" + stopWatch.Elapsed + " ,遍歷采用foreach方式");//Dictionary插入dataCount條數(shù)據(jù)需要時間stopWatch.Reset();si = 0;stopWatch.Start();IDictionaryEnumerator _hashEnum = _Hashtable.GetEnumerator();while (_hashEnum.MoveNext()){si++;}stopWatch.Stop();Console.WriteLine(" HashTable遍歷時間：" + stopWatch.Elapsed + " ,遍歷采用HashTable.GetEnumerator()方式");//Dictionary插入dataCount條數(shù)據(jù)需要時間stopWatch.Reset();si = 0;stopWatch.Start();for(int i=0;i<_Dictionary.Count;i++){si++;}stopWatch.Stop();Console.WriteLine(" Dictionary遍歷時間：" + stopWatch.Elapsed + " ,遍歷采用for方式");//Dictionary插入dataCount條數(shù)據(jù)需要時間stopWatch.Reset();si = 0;stopWatch.Start();foreach (var s in _Dictionary){si++;}stopWatch.Stop();Console.WriteLine(" Dictionary遍歷時間：" + stopWatch.Elapsed + " ,遍歷采用foreach方式");//Dictionary插入dataCount條數(shù)據(jù)需要時間stopWatch.Reset();si = 0;stopWatch.Start();_hashEnum = _Dictionary.GetEnumerator();while (_hashEnum.MoveNext()){si++;}stopWatch.Stop();Console.WriteLine(" Dictionary遍歷時間：" + stopWatch.Elapsed + " ,遍歷采用Dictionary.GetEnumerator()方式");Console.WriteLine("\n-------------------------------------------------");}}

四：從上面的結(jié)果可以看出

1.HashTable大數(shù)據(jù)量插入數(shù)據(jù)時需要花費比Dictionary大的多的時間。

2.for方式遍歷HashTable和Dictionary速度最快。

3.在foreach方式遍歷時Dictionary遍歷速度更快。

五：在單線程的時候使用Dictionary更好一些，多線程的時候使用HashTable更好。

因為HashTable可以通過Hashtable tab = Hashtable.Synchronized(new Hashtable());獲得線程安全的對象。

當(dāng)然因為各自電腦的情況不一樣，可能會有部分誤差。如有問題，敬請斧正。

轉(zhuǎn)載于:https://www.cnblogs.com/zhaox583132460/p/3410331.html

總結(jié)

以上是生活随笔為你收集整理的C#中Hashtable、Dictionary详解以及写入和读取对比的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。