C#中HashTable、Dictionary、ConcurrentDictionary區別

語言: CN / TW / HK

一、HashTable

HashTable表示鍵/值對的集合。在.NET Framework中,Hashtable是System.Collections名稱空間提供的一個容器,用於處理和表現類似key-value的鍵值對,其中key通常可用來快速查詢,同時key是區分大小寫;value用於儲存對應於key的值。Hashtable中key-value鍵值對均為object型別,所以Hashtable可以支援任何型別的keyvalue鍵值對,任何非 null 物件都可以用作鍵或值。

HashTable是一種散列表,他內部維護很多對Key-Value鍵值對,其還有一個類似索引的值叫做雜湊值(HashCode),它是根據GetHashCode方法對Key通過一定演算法獲取得到的,所有的查詢操作定位操作都是基於雜湊值來實現找到對應的Key和Value值的。

雜湊函式(GetHashCode)讓雜湊值對應HashTable的空間地址儘量不重複。

當一個HashTable被佔用一大半的時候我們通過計算雜湊值取得的地址值可能會重複指向同一地址,這就造成雜湊衝突。

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

使用方法如下:

using System;
using System.Collections;


namespace WebApp
{
class Program
{
static void Main(string[] args)
{
Hashtable myHash=new Hashtable();

//插入
myHash.Add("1","joye.net");
myHash.Add("2", "joye.net2");
myHash.Add("3", "joye.net3");


//key 存在
try
{
myHash.Add("1", "1joye.net");
}
catch
{
Console.WriteLine("Key = \"1\" already exists.");
}
//取值
Console.WriteLine("key = \"2\", value = {0}.", myHash["2"]);


//修改
myHash["2"] = "http://www.cnblogs.com/yinrq/";
myHash["4"] = "joye.net4"; //修改的key不存在則新增
Console.WriteLine("key = \"2\", value = {0}.", myHash["2"]);
Console.WriteLine("key = \"4\", value = {0}.", myHash["4"]);


//判斷key是否存在
if (!myHash.ContainsKey("5"))
{
myHash.Add("5", "joye.net5");
Console.WriteLine("key = \"5\": {0}", myHash["5"]);
}
//移除
myHash.Remove("1");


if (!myHash.ContainsKey("1"))
{
Console.WriteLine("Key \"1\" is not found.");
}
//foreach 取值
foreach (DictionaryEntry item in myHash)
{
Console.WriteLine("Key = {0}, Value = {1}", item.Key, item.Value);
}
//所有的值
foreach (var item in myHash.Values)
{
Console.WriteLine("Value = {0}",item);
}


//所有的key
foreach (var item in myHash.Keys)
{
Console.WriteLine("Key = {0}", item);
}
Console.ReadKey();
}
}
}

更多參考微軟官方文件:Hashtable 類

二、Dictionary

Dictionary<TKey, TValue> 泛型類提供了從一組鍵到一組值的對映。通過鍵來檢索值的速度是非常快的,接近於 O(1),這是因為 Dictionary<TKey, TValue> 類是作為一個雜湊表來實現的。檢索速度取決於為 TKey 指定的型別的雜湊演算法的質量。TValue可以是值型別,陣列,類或其他。

Dictionary是一種變種的HashTable,它採用一種分離連結散列表的資料結構來解決雜湊衝突的問題。

簡單使用程式碼:

using System;
using System.Collections;
using System.Collections.Generic;


namespace WebApp
{
class Program
{
static void Main(string[] args)
{
Dictionary<string, string> myDic = new Dictionary<string, string>();

//插入
myDic.Add("1", "joye.net");
myDic.Add("2", "joye.net2");
myDic.Add("3", "joye.net3");


//key 存在
try
{
myDic.Add("1", "1joye.net");
}
catch
{
Console.WriteLine("Key = \"1\" already exists.");
}
//取值
Console.WriteLine("key = \"2\", value = {0}.", myDic["2"]);


//修改
myDic["2"] = "http://www.cnblogs.com/yinrq/";
myDic["4"] = "joye.net4"; //修改的key不存在則新增
Console.WriteLine("key = \"2\", value = {0}.", myDic["2"]);
Console.WriteLine("key = \"4\", value = {0}.", myDic["4"]);


//判斷key是否存在
if (!myDic.ContainsKey("5"))
{
myDic.Add("5", "joye.net5");
Console.WriteLine("key = \"5\": {0}", myDic["5"]);
}
//移除
myDic.Remove("1");


if (!myDic.ContainsKey("1"))
{
Console.WriteLine("Key \"1\" is not found.");
}
//foreach 取值
foreach (var item in myDic)
{
Console.WriteLine("Key = {0}, Value = {1}", item.Key, item.Value);
}
//所有的值
foreach (var item in myDic.Values)
{
Console.WriteLine("Value = {0}",item);
}


//所有的key
foreach (var item in myDic.Keys)
{
Console.WriteLine("Key = {0}", item);
}
Console.ReadKey();
}
}
}

更多資料參考:Dictionary 類

三、ConcurrentDictionary

表示可由多個執行緒同時訪問的鍵/值對的執行緒安全集合。

ConcurrentDictionary< TKey,  TValue>  framework4出現的,可由多個執行緒同時訪問,且執行緒安全。用法同Dictionary很多相同,但是多了一些方法。ConcurrentDictionary 屬於System.Collections.Concurrent 名稱空間按照MSDN上所說:

System.Collections.Concurrent 名稱空間提供多個執行緒安全集合類。當有多個執行緒併發訪問集合時,應使用這些類代替 System.Collections 和 System.Collections.Generic 名稱空間中的對應型別。

更多資料:ConcurrentDictionary<TKey,?TValue> 類

四、對比總結

分別插入500萬條資料,然後遍歷,看看耗時。

using System;
using System.Collections;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Diagnostics;


namespace WebApp
{
class Program
{
static Hashtable _hashtable;
static Dictionary<string, string> _dictionary;
static ConcurrentDictionary<string, string> _conDictionary;
static void Main(string[] args)
{
Compare(5000000);
Console.ReadLine();
Console.Read();
}


public static void Compare(int dataCount)
{
_hashtable = new Hashtable();
_dictionary = new Dictionary<string, string>();
_conDictionary=new ConcurrentDictionary<string, string>();
Stopwatch stopWatch = new Stopwatch();


// Hashtable
stopWatch.Start();
for (int i = 0; i < dataCount; i++)
{
_hashtable.Add("key" + i.ToString(), "Value" + i.ToString());
}
stopWatch.Stop();
Console.WriteLine("HashTable插" + dataCount + "條耗時(毫秒):" + stopWatch.ElapsedMilliseconds);


//Dictionary
stopWatch.Reset();
stopWatch.Start();
for (int i = 0; i < dataCount; i++)
{
_dictionary.Add("key" + i.ToString(), "Value" +i.ToString());
}
stopWatch.Stop();
Console.WriteLine("Dictionary插" + dataCount + "條耗時(毫秒):" + stopWatch.ElapsedMilliseconds);


//ConcurrentDictionary
stopWatch.Reset();
stopWatch.Start();
for (int i = 0; i < dataCount; i++)
{
_conDictionary.TryAdd("key" + i.ToString(), "Value" + i.ToString());
}
stopWatch.Stop();
Console.WriteLine("ConcurrentDictionary插" + dataCount + "條耗時(毫秒):" + stopWatch.ElapsedMilliseconds);


// Hashtable
stopWatch.Reset();
stopWatch.Start();
for (int i = 0; i < _hashtable.Count; i++)
{
var key = _hashtable[i];
}
stopWatch.Stop();
Console.WriteLine("HashTable遍歷時間(毫秒):" + stopWatch.ElapsedMilliseconds);


//Dictionary
stopWatch.Reset();
stopWatch.Start();
for (int i = 0; i < _hashtable.Count; i++)
{
var key = _dictionary["key" + i.ToString()];
}
stopWatch.Stop();
Console.WriteLine("Dictionary遍歷時間(毫秒):" + stopWatch.ElapsedMilliseconds);


//ConcurrentDictionary
stopWatch.Reset();
stopWatch.Start();
for (int i = 0; i < _hashtable.Count; i++)
{
var key = _conDictionary["key"+i.ToString()];
}
stopWatch.Stop();
Console.WriteLine("ConcurrentDictionary遍歷時間(毫秒):" + stopWatch.ElapsedMilliseconds);
}
}
}

執行結果:

可以看出:

大資料插入Dictionary花費時間最少

遍歷HashTable最快是Dictionary的1/5,ConcurrentDictionary的1/10

單執行緒建議用Dictionary,多執行緒建議用ConcurrentDictionary或者HashTable(Hashtable tab = Hashtable.Synchronized(new Hashtable());獲得執行緒安全的物件)

往期 精彩 回顧

【推薦】.NET Core開發實戰視訊課程   ★★★

.NET Core實戰專案之CMS 第一章 入門篇-開篇及總體規劃

【.NET Core微服務實戰-統一身份認證】開篇及目錄索引

Redis基本使用及百億資料量中的使用技巧分享(附視訊地址及觀看指南)

.NET Core中的一個介面多種實現的依賴注入與動態選擇看這篇就夠了

10個小技巧助您寫出高效能的ASP.NET Core程式碼

用abp vNext快速開發Quartz.NET定時任務管理介面

在ASP.NET Core中建立基於Quartz.NET託管服務輕鬆實現作業排程

現身說法:實際業務出發分析百億資料量下的多表查詢優化

關於C#非同步程式設計你應該瞭解的幾點建議

C#非同步程式設計看這篇就夠了