一：HashTable
1.HashTable是一種散列表，他內(nèi)部維護(hù)很多對(duì)Key-Value鍵值對(duì)，其還有一個(gè)類(lèi)似索引的值叫做散列值(HashCode)，它是根據(jù)GetHashCode方法對(duì)Key通過(guò)一定算法獲取得到的，所有的查找操作定位操作都是基于散列值來(lái)實(shí)現(xiàn)找到對(duì)應(yīng)的Key和Value值的。
2.我們需要使用一個(gè)算法讓散列值對(duì)應(yīng)HashTable的空間地址盡量不重復(fù)，這就是散列函數(shù)(GetHashCode)需要做的事。
3.當(dāng)一個(gè)HashTable被占用一大半的時(shí)候我們通過(guò)計(jì)算散列值取得的地址值可能會(huì)重復(fù)指向同一地址，這就是哈希沖突。
在.Net中鍵值對(duì)在HashTable中的位置Position= (HashCode& 0x7FFFFFFF) % HashTable.Length，.net中是通過(guò)探測(cè)法解決哈希沖突的，當(dāng)通過(guò)散列值取得的位置Postion以及被占用的時(shí)候，就會(huì)增加一個(gè)位移x值判斷下一個(gè)位置Postion+x是否被占用，如果仍然被占用就繼續(xù)往下位移x判斷Position+2*x位置是否被占用，如果沒(méi)有被占用則將值放入其中。當(dāng)HashTable中的可用空間越來(lái)越小時(shí)，則獲取得到可用空間的難度越來(lái)越大，消耗的時(shí)間就越多。
4.當(dāng)前HashTable中的被占用空間達(dá)到一個(gè)百分比的時(shí)候就將該空間自動(dòng)擴(kuò)容，在.net中這個(gè)百分比是72%,也叫.net中HashTable的填充因子為0.72。例如有一個(gè)HashTable的空間大小是100，當(dāng)它需要添加第73個(gè)值的時(shí)候?qū)?huì)擴(kuò)容此HashTable.
5.這個(gè)自動(dòng)擴(kuò)容的大小是多少呢？答案是當(dāng)前空間大小的兩倍最接近的素?cái)?shù)，例如當(dāng)前HashTable所占空間為素?cái)?shù)71，如果擴(kuò)容，則擴(kuò)容大小為素?cái)?shù)131.
二：Dictionary
1.Dictionary是一種變種的HashTable,它采用一種分離鏈接散列表的數(shù)據(jù)結(jié)構(gòu)來(lái)解決哈希沖突的問(wèn)題。
2.分離鏈接散列表是當(dāng)散列到同一個(gè)地址的值存為一個(gè)鏈表中。
3.這個(gè)變種HashTable的填充因子是1
三：本文將以代碼的形式探索HashTable和Dictionary的插入和三種讀取方式的效率(for/foreach/GetEnumerator)
//Dictionary插入dataCount條數(shù)據(jù)需要時(shí)間
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ù)需要時(shí)間：" + stopWatch.Elapsed);
//Dictionary插入dataCount條數(shù)據(jù)需要時(shí)間
stopWatch.Reset();
int si = 0;
stopWatch.Start();
for(int i=0;i<_Hashtable.Count;i++)
{
si++;
}
stopWatch.Stop();
Console.WriteLine(" HashTable遍歷時(shí)間：" + stopWatch.Elapsed + " ,遍歷采用for方式");
//Dictionary插入dataCount條數(shù)據(jù)需要時(shí)間
stopWatch.Reset();
si = 0;
stopWatch.Start();
foreach (var s in _Hashtable)
{
si++;
}
stopWatch.Stop();
Console.WriteLine(" HashTable遍歷時(shí)間：" + stopWatch.Elapsed + " ,遍歷采用foreach方式");
//Dictionary插入dataCount條數(shù)據(jù)需要時(shí)間
stopWatch.Reset();
si = 0;
stopWatch.Start();
IDictionaryEnumerator _hashEnum = _Hashtable.GetEnumerator();
while (_hashEnum.MoveNext())
{
si++;
}
stopWatch.Stop();
Console.WriteLine(" HashTable遍歷時(shí)間：" + stopWatch.Elapsed + " ,遍歷采用HashTable.GetEnumerator()方式");
//Dictionary插入dataCount條數(shù)據(jù)需要時(shí)間
stopWatch.Reset();
si = 0;
stopWatch.Start();
for(int i=0;i<_Dictionary.Count;i++)
{
si++;
}
stopWatch.Stop();
Console.WriteLine(" Dictionary遍歷時(shí)間：" + stopWatch.Elapsed + " ,遍歷采用for方式");
//Dictionary插入dataCount條數(shù)據(jù)需要時(shí)間
stopWatch.Reset();
si = 0;
stopWatch.Start();
foreach (var s in _Dictionary)
{
si++;
}
stopWatch.Stop();
Console.WriteLine(" Dictionary遍歷時(shí)間：" + stopWatch.Elapsed + " ,遍歷采用foreach方式");
//Dictionary插入dataCount條數(shù)據(jù)需要時(shí)間
stopWatch.Reset();
si = 0;
stopWatch.Start();
_hashEnum = _Dictionary.GetEnumerator();
while (_hashEnum.MoveNext())
{
si++;
}
stopWatch.Stop();
Console.WriteLine(" Dictionary遍歷時(shí)間：" + stopWatch.Elapsed + " ,遍歷采用Dictionary.GetEnumerator()方式");
Console.WriteLine("/n-------------------------------------------------");
}
}
四：從上面的結(jié)果可以看出
1.HashTable大數(shù)據(jù)量插入數(shù)據(jù)時(shí)需要花費(fèi)比Dictionary大的多的時(shí)間。
2.for方式遍歷HashTable和Dictionary速度最快。
3.在foreach方式遍歷時(shí)Dictionary遍歷速度更快。
五：在單線程的時(shí)候使用Dictionary更好一些，多線程的時(shí)候使用HashTable更好。
因?yàn)镠ashTable可以通過(guò)Hashtable tab = Hashtable.Synchronized(new Hashtable());獲得線程安全的對(duì)象。
當(dāng)然因?yàn)楦髯噪娔X的情況不一樣，可能會(huì)有部分誤差。如有問(wèn)題，敬請(qǐng)斧正。
新聞熱點(diǎn)
疑難解答
圖片精選
