Dictionary<TKey,TValue>是日常.net開發中最常用的數據類型之一，基本上遇到鍵值對類型的數據時第一反應就是使用這種散列表。散列表特別適合快速查找操作，查找的效率是常數階O(1)。那麼為什麼這種數據類型的查找效率能夠這麼高效？它背後的數據類型是如何支撐這種查找效率的？它在使用過程中有沒有什麼局限性？一起來探究下這個數據類型的奧秘吧。
本文內容針對的是.Net Framework 4.5.1的代碼實現，在其他.Net版本中或多或少都會有些差異，但是基本的原理還是相同的。
本文的內容主要分為三個部分，第一部分是從代碼的角度來分析並以圖文並茂的方式通俗的解釋Dictionary如何解決的散列衝突並實現高效的數據插入和查找。第二部分名為“眼見為實”，由於第一部分是從代碼層面分析Dictionary的實現，側重於理論分析，因此第二部分使用windbg直接分析內存結構，跟第一部分的理論分析相互印證，加深對於這種數據類型的深入理解。最後是從數據結構的時間複雜度的角度進行分析並提出了幾條實踐建議。
本文內容：
- 第一部分 代碼分析
- 散列衝突
- Dictionary圖文解析
- Dictionary的初始化
- 添加第四個元素
- 第二部分 眼見為實
- 添加第一個元素后的內存結構
- 添加第四個元素后的內存結構
- 第三部分
- 時間複雜度分析
- 實踐建議
散列衝突
提到散列表，就不能不提散列衝突。由於哈希算法被計算的數據是無限的，而計算后的結果範圍有限，因此總會存在不同的數據經過計算后得到的值相同，這就是哈希衝突。（兩個不同的數據計算后的結果一樣）。散列衝突的解決方案有好幾個，比如開放尋址法、鏈式尋址法。
Dictionary使用的是鏈式尋址法，也叫做拉鏈法。拉鏈法的基本思想是將散列值相同的數據存在同一個鏈表中，如果有散列值相同的元素，則加到鏈表的頭部。同樣道理，在查找元素的時候，先計算散列值，然後在對應散列值的鏈表中查找目標元素。
用圖來表達鏈式尋址法的思想：
Dictionary<TKey,TValue>的內部數據結構
Dictionary的內部存儲數據主要是依賴了兩個數組，分別是int[] buckets和Entry[] entries。其中buckets是Dictionary所有操作的入口，類似於上文中解說拉鏈法所用的圖中的那個豎著的數據結構。Entry是一個結構體，用於封裝所有的元素並且增加了next字段用於構建鏈表數據結構。為了便於理解，下文中截取了一段相關的源代碼並增加了註釋。
//數據在Dictionary<TKey,TValue>的存儲形式，所有的鍵值對在Dictionary<TKey,TValue>都是被包裝成一個個的Entry保存在內存中
private struct Entry {
public int hashCode; // 散列計算結果的低31位數，默認值為-1
public int next; // 下一個Entry的索引值，鏈表的最後一個Entry的next為-1
public TKey key; // Entry對象的Key對應於傳入的TKey
public TValue value; // Entry對象的Value對應與傳入的TValue
}
private int[] buckets; //hashCode的桶，是查找所有Entry的第一級數據結構
private Entry[] entries; //保存真正的數據
下文中以Dictionary<int,string>為例，分析Dictionary在使用過程中內部數據的組織方式。
Dictionary初始化
初始化代碼：
Dictionary<int, string> dictionary = new Dictionary<int, string>();
Dictionary的初始化時，buckets和entries的長度都是0。
添加一個元素
dictionary.Add(1, "xyxy");
向Dictionary中添加這個新元素大致經過了7個步驟：
- 首先判斷數組長度是否需要擴容（原長度為0，需要擴容）；
- 對於數組進行擴容，分別創建長度為3的bucket數組和entries數組（使用大於原數組長度2倍的第一個素數作為新的數組長度）；
- 整數1的hashcode為1；
- 取低31位數值為1（計算公式：hashcode & 0x7FFFFFFF=1）；
- 該key的hashcode落到bucket下標為1的位置（計算公式：hashCode % buckets.Length=1）；
- 將hashcode、key、value包裝起來（封裝到entries數組下標為0的結構體中）；
- 設置bucket[1]的值為0（因為新元素被封裝到了entries數組下標為0的位置）；
當向Dictionary中添加一個元素后，內部數據結構如下圖（為了便於理解，圖上將bucket和entries中各個鏈表頭結點用線標出了關聯關係）：
添加第二個元素
dictionary.Add(7, "xyxy");
向Dictionary中添加這個元素大致經過了6個步驟：
- 計算7的hashcode是7；
- 取低31位數值為7（計算公式：hashcode & 0x7FFFFFFF=1）；
- 該key的hashcode落到bucket下標為1的位置（計算公式：hashCode % buckets.Length=1）；
- 將hashcode、key、value包裝起來（封裝到entries數組下標為1的結構體中，跟步驟3計算得到的1沒有關係，只是因為entries數組下標為1的元素是空着的所以放在這裏）；
- 原bucket[1]為0，所以設置當前結構體的Entry.next為0；
- 設置bucket[1]為1（因為鏈表的頭部節點位於entries數組下標為1的位置）
當向Dictionary中添加第二個元素后，內部數據結構是這樣的：
添加第三個元素
dictionary.Add(2, "xyxy");
向Dictionary添加這個元素經過了如下5個步驟：
- 整數2計算的hashcode是2；
- hashcode取低31位數值為2（計算公式：hashcode & 0x7FFFFFFF=2）；
- 該key的hashcode落到bucket下標為2的位置（計算公式：hashCode % buckets.Length=2）；
- 將hashcode、key、value包裝起來（封裝到entries數組下標為2的結構體中，到此entries的數組就存滿了）；
- 原bucket[2]上為-1，所以bucket[2]節點下並沒有對應鏈表，設置當前結構體的Entry.next為-1；
- 設置bucket[2]為2（因為鏈表的頭部節點位於entries數組下標為2的位置）
當向Dictionary中添加第三個元素后，內部數據結構：
添加第四個元素
dictionary.Add(4, "xyxy");
通過前面幾個操作可以看出，當前數據結構中entries數組中的元素已滿，如果再添加元素的話，會發生怎樣的變化呢？
假如再對於dictionary添加一個元素，原來申請的內存空間肯定是不夠用的，必須對於當前數據結構進行擴容，然後在擴容的基礎上再執行添加元素的操作。那麼在解釋這個Add方法原理的時候，分為兩個場景分別進行：數組擴容和元素添加。
數組擴容
在發現數組容量不夠的時候，Dictionary首先執行擴容操作，擴容的規則與該數據類型首次初始化的規則相同，即使用大於原數組長度2倍的第一個素數7作為新數組的長度（3*2=6，大於6的第一個素數是7）。
擴容步驟：
- 新申請一個容量為7的數組，並將原數組的元素拷貝至新數組（代碼：
Array.Copy(entries, 0, newEntries, 0, count);） - 重新計算原
Dictionary中的元素的hashCode在bucket中的位置（注意新的bucket數組中數值的變化）； - 重新計算鏈表（注意entries數組中結構體的next值的變化）；
擴容完成后Dictionary的內容數據結構：
添加元素
當前已經完成了entries和bucket數組的擴容，有了充裕的空間來存儲新的元素，所以可以在新的數據結構的基礎上繼續添加元素。
當向Dictionary中添加第四個元素后，內部數據結構是這樣的：
添加這個新的元素的步驟：
- 整數4計算的hashcode是4；
- hashcode取低31位數值為4（計算公式：hashcode & 0x7FFFFFFF=4）；
- 該key的hashcode落到bucket下標為4的位置（計算公式：hashCode % buckets.Length=4）；
- 將hashcode、key、value包裝起來；（封裝到entries數組下標為3的結構體中)；
- 原bucket[4]上為-1，所以當前節點下並沒有鏈表，設置當前結構體的Entry.next為-1；
- 設置bucket[4]為3（因為鏈表的頭部節點位於entries數組下標為3的位置）
眼見為實
畢竟本文的主題是圖文並茂分析Dictionary<Tkey,Tvalue>的原理，雖然已經從代碼層面和理論層面分析了Dictionary<Tkey,Tvalue>的實現，但是如果能夠分析這個數據類型的實際內存數據結果，可以獲得更直觀的感受並且對於這個數據類型能夠有更加深入的認識。由於篇幅的限制，無法將Dictionary<Tkey,Tvalue>的所有操作場景結果都進行內存分析，那麼本文中精選有代表性的兩個場景進行分析：一是該數據類型初始化后添加第一個元素的內存結構，二是該數據類型進行第一次擴容后的數據結構。
Dictionary添加第一個元素后的內存結構
執行代碼：
Dictionary<int, string> dic = new Dictionary<int, string>();
dic.Add(1, "xyxy");
Console.Read();
打開windbg附加到該進程(由於使用的是控制台應用程序，當前線程是0號線程，因此如果附加進程后默認的不是0號線程時執行~0s切換到0號線程),執行!clrstack -l查看當前線程及線程上使用的所有變量：
0:000> !clrstack -l
OS Thread Id: 0x48b8 (0)
Child SP IP Call Site
0000006de697e998 00007ffab577c134 [InlinedCallFrame: 0000006de697e998] Microsoft.Win32.Win32Native.ReadFile(Microsoft.Win32.SafeHandles.SafeFileHandle, Byte*, Int32, Int32 ByRef, IntPtr)
0000006de697e998 00007ffa96abc9c8 [InlinedCallFrame: 0000006de697e998] Microsoft.Win32.Win32Native.ReadFile(Microsoft.Win32.SafeHandles.SafeFileHandle, Byte*, Int32, Int32 ByRef, IntPtr)
0000006de697e960 00007ffa96abc9c8 *** ERROR: Module load completed but symbols could not be loaded for C:\WINDOWS\assembly\NativeImages_v4.0.30319_64\mscorlib\5c1b7b73113a6f079ae59ad2eb210951\mscorlib.ni.dll
DomainNeutralILStubClass.IL_STUB_PInvoke(Microsoft.Win32.SafeHandles.SafeFileHandle, Byte*, Int32, Int32 ByRef, IntPtr)
0000006de697ea40 00007ffa972d39ec System.IO.__ConsoleStream.ReadFileNative(Microsoft.Win32.SafeHandles.SafeFileHandle, Byte[], Int32, Int32, Boolean, Boolean, Int32 ByRef)
LOCALS:
<no data>
<no data>
<no data>
<no data>
<no data>
<no data>
0000006de697ead0 00007ffa972d38f5 System.IO.__ConsoleStream.Read(Byte[], Int32, Int32)
LOCALS:
<no data>
<no data>
0000006de697eb30 00007ffa96a882d4 System.IO.StreamReader.ReadBuffer()
LOCALS:
<no data>
<no data>
0000006de697eb80 00007ffa97275f23 System.IO.StreamReader.Read()
LOCALS:
<no data>
0000006de697ebb0 00007ffa9747a2fd System.IO.TextReader+SyncTextReader.Read()
0000006de697ec10 00007ffa97272698 System.Console.Read()
0000006de697ec40 00007ffa38670909 ConsoleTest.DictionaryDebug.Main(System.String[])
LOCALS:
0x0000006de697ec70 = 0x00000215680d2dd8
0000006de697ee88 00007ffa97ba6913 [GCFrame: 0000006de697ee88]
通過對於線程堆棧的分析很容易看出當前線程上使用了一個局部變量，地址為：0x000001d86c972dd8，使用!do命令查看該變量的內容：
0:000> !do 0x00000215680d2dd8
Name: System.Collections.Generic.Dictionary`2[[System.Int32, mscorlib],[System.String, mscorlib]]
MethodTable: 00007ffa96513328
EEClass: 00007ffa9662f610
Size: 80(0x50) bytes
File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
MT Field Offset Type VT Attr Value Name
00007ffa964a8538 4001887 8 System.Int32[] 0 instance 00000215680d2ee8 buckets
00007ffa976c4dc0 4001888 10 ...non, mscorlib]][] 0 instance 00000215680d2f10 entries
00007ffa964a85a0 4001889 38 System.Int32 1 instance 1 count
00007ffa964a85a0 400188a 3c System.Int32 1 instance 1 version
00007ffa964a85a0 400188b 40 System.Int32 1 instance -1 freeList
00007ffa964a85a0 400188c 44 System.Int32 1 instance 0 freeCount
00007ffa96519630 400188d 18 ...Int32, mscorlib]] 0 instance 00000215680d2ed0 comparer
00007ffa964c6ad0 400188e 20 ...Canon, mscorlib]] 0 instance 0000000000000000 keys
00007ffa977214e0 400188f 28 ...Canon, mscorlib]] 0 instance 0000000000000000 values
00007ffa964a5dd8 4001890 30 System.Object 0 instance 0000000000000000 _syncRoot
從內存結構來看，該變量中就是我們查找的Dic存在buckets、entries、count、version等字段，其中buckets和entries在上文中已經有多次提及，也是本文的分析重點。既然要眼見為實，那麼buckets和entries這兩個數組的內容到底是什麼樣的呢？這兩個都是數組，一個是int數組，另一個是結構體數組，對於這兩個內容分別使用!da命令查看其內容：
首先是buckets的內容：
0:000> !da -start 0 -details 00000215680d2ee8
Name: System.Int32[]
MethodTable: 00007ffa964a8538
EEClass: 00007ffa966160e8
Size: 36(0x24) bytes
Array: Rank 1, Number of elements 3, Type Int32
Element Methodtable: 00007ffa964a85a0
[0] 00000215680d2ef8
Name: System.Int32
MethodTable: 00007ffa964a85a0
EEClass: 00007ffa96616078
Size: 24(0x18) bytes
File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
MT Field Offset Type VT Attr Value Name
00007ffa964a85a0 40005a2 0 System.Int32 1 instance -1 m_value
[1] 00000215680d2efc
Name: System.Int32
MethodTable: 00007ffa964a85a0
EEClass: 00007ffa96616078
Size: 24(0x18) bytes
File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
MT Field Offset Type VT Attr Value Name
00007ffa964a85a0 40005a2 0 System.Int32 1 instance 0 m_value
[2] 00000215680d2f00
Name: System.Int32
MethodTable: 00007ffa964a85a0
EEClass: 00007ffa96616078
Size: 24(0x18) bytes
File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
MT Field Offset Type VT Attr Value Name
00007ffa964a85a0 40005a2 0 System.Int32 1 instance -1 m_value
當前buckets中有三個值，分別是：-1、0和-1，其中-1是數組初始化后的默認值，而下錶為1的位置的值0則是上文中添加dic.Add(1, "xyxy");這個指令的結果，代表其對應的鏈表首節點在entries數組中下標為0的位置，那麼entries數組中的數值是什麼樣子的呢？
0:000> !da -start 0 -details 00000215680d2f10
Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]][]
MethodTable: 00007ffa965135b8
EEClass: 00007ffa9662d1f0
Size: 96(0x60) bytes
Array: Rank 1, Number of elements 3, Type VALUETYPE
Element Methodtable: 00007ffa96513558
[0] 00000215680d2f20
Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
MethodTable: 00007ffa96513558
EEClass: 00007ffa966304e8
Size: 40(0x28) bytes
File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
MT Field Offset Type VT Attr Value Name
00007ffa964a85a0 4003502 8 System.Int32 1 instance 1 hashCode
00007ffa964a85a0 4003503 c System.Int32 1 instance -1 next
00007ffa964a85a0 4003504 10 System.Int32 1 instance 1 key
00007ffa964aa238 4003505 0 System.__Canon 0 instance 00000215680d2db0 value
[1] 00000215680d2f38
Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
MethodTable: 00007ffa96513558
EEClass: 00007ffa966304e8
Size: 40(0x28) bytes
File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
MT Field Offset Type VT Attr Value Name
00007ffa964a85a0 4003502 8 System.Int32 1 instance 0 hashCode
00007ffa964a85a0 4003503 c System.Int32 1 instance 0 next
00007ffa964a85a0 4003504 10 System.Int32 1 instance 0 key
00007ffa964aa238 4003505 0 System.__Canon 0 instance 0000000000000000 value
[2] 00000215680d2f50
Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
MethodTable: 00007ffa96513558
EEClass: 00007ffa966304e8
Size: 40(0x28) bytes
File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
MT Field Offset Type VT Attr Value Name
00007ffa964a85a0 4003502 8 System.Int32 1 instance 0 hashCode
00007ffa964a85a0 4003503 c System.Int32 1 instance 0 next
00007ffa964a85a0 4003504 10 System.Int32 1 instance 0 key
00007ffa964aa238 4003505 0 System.__Canon 0 instance 0000000000000000 value
通過對於entries數組的分析可以看出，這個數組也有三個值，其中下標為0的位置已經填入相關內容，比如hashCode為1，key為1，其中value的內容是一個內存地址：000001d86c972db0，這個地址指向的就是字符串對象，它的內容是xyxy，使用!do指令來看下具體內容：
0:000> !do 00000215680d2db0
Name: System.String
MethodTable: 00007ffcc6b359c0
EEClass: 00007ffcc6b12ec0
Size: 34(0x22) bytes
File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
String: xyxy
Fields:
MT Field Offset Type VT Attr Value Name
00007ffcc6b385a0 4000283 8 System.Int32 1 instance 4 m_stringLength
00007ffcc6b36838 4000284 c System.Char 1 instance 78 m_firstChar
00007ffcc6b359c0 4000288 e0 System.String 0 shared static Empty
簡要分析擴容后的內存結構
此次執行的代碼為：
Dictionary<int, string> dic = new Dictionary<int, string>();
dic.Add(1, "xyxy");
dic.Add(7, "xyxy");
dic.Add(2, "xyxy");
dic.Add(4, "xyxy");
Console.Read();
同樣採取附加進程的方式分析這段代碼執行后的內存結構，本章節中忽略掉如何查找Dictionary變量地址的部分，直接分析buckets數組和entries數組的內容。
首先是buckets數組的內存結構：
0:000> !da -start 0 -details 0000019a471a54f8
Name: System.Int32[]
MethodTable: 00007ffcc6b38538
EEClass: 00007ffcc6ca60e8
Size: 52(0x34) bytes
Array: Rank 1, Number of elements 7, Type Int32
Element Methodtable: 00007ffcc6b385a0
[0] 0000019a471a5508
Name: System.Int32
MethodTable: 00007ffcc6b385a0
EEClass: 00007ffcc6ca6078
Size: 24(0x18) bytes
File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
MT Field Offset Type VT Attr Value Name
00007ffcc6b385a0 40005a2 0 System.Int32 1 instance 1 m_value
[1] 0000019a471a550c
Name: System.Int32
MethodTable: 00007ffcc6b385a0
EEClass: 00007ffcc6ca6078
Size: 24(0x18) bytes
File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
MT Field Offset Type VT Attr Value Name
00007ffcc6b385a0 40005a2 0 System.Int32 1 instance 0 m_value
[2] 0000019a471a5510
Name: System.Int32
MethodTable: 00007ffcc6b385a0
EEClass: 00007ffcc6ca6078
Size: 24(0x18) bytes
File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
MT Field Offset Type VT Attr Value Name
00007ffcc6b385a0 40005a2 0 System.Int32 1 instance 2 m_value
[3] 0000019a471a5514
Name: System.Int32
MethodTable: 00007ffcc6b385a0
EEClass: 00007ffcc6ca6078
Size: 24(0x18) bytes
File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
MT Field Offset Type VT Attr Value Name
00007ffcc6b385a0 40005a2 0 System.Int32 1 instance -1 m_value
[4] 0000019a471a5518
Name: System.Int32
MethodTable: 00007ffcc6b385a0
EEClass: 00007ffcc6ca6078
Size: 24(0x18) bytes
File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
MT Field Offset Type VT Attr Value Name
00007ffcc6b385a0 40005a2 0 System.Int32 1 instance 3 m_value
[5] 0000019a471a551c
Name: System.Int32
MethodTable: 00007ffcc6b385a0
EEClass: 00007ffcc6ca6078
Size: 24(0x18) bytes
File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
MT Field Offset Type VT Attr Value Name
00007ffcc6b385a0 40005a2 0 System.Int32 1 instance -1 m_value
[6] 0000019a471a5520
Name: System.Int32
MethodTable: 00007ffcc6b385a0
EEClass: 00007ffcc6ca6078
Size: 24(0x18) bytes
File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
MT Field Offset Type VT Attr Value Name
00007ffcc6b385a0 40005a2 0 System.Int32 1 instance -1 m_value
然後是entries的內存結構：
0:000> !da -start 0 -details 00000237effb2fa8
Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]][]
MethodTable: 00007ffa965135b8
EEClass: 00007ffa9662d1f0
Size: 192(0xc0) bytes
Array: Rank 1, Number of elements 7, Type VALUETYPE
Element Methodtable: 00007ffa96513558
[0] 00000237effb2fb8
Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
MethodTable: 00007ffa96513558
EEClass: 00007ffa966304e8
Size: 40(0x28) bytes
File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
MT Field Offset Type VT Attr Value Name
00007ffa964a85a0 4003502 8 System.Int32 1 instance 1 hashCode
00007ffa964a85a0 4003503 c System.Int32 1 instance -1 next
00007ffa964a85a0 4003504 10 System.Int32 1 instance 1 key
00007ffa964aa238 4003505 0 System.__Canon 0 instance 00000237effb2db0 value
[1] 00000237effb2fd0
Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
MethodTable: 00007ffa96513558
EEClass: 00007ffa966304e8
Size: 40(0x28) bytes
File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
MT Field Offset Type VT Attr Value Name
00007ffa964a85a0 4003502 8 System.Int32 1 instance 7 hashCode
00007ffa964a85a0 4003503 c System.Int32 1 instance -1 next
00007ffa964a85a0 4003504 10 System.Int32 1 instance 7 key
00007ffa964aa238 4003505 0 System.__Canon 0 instance 00000237effb2db0 value
[2] 00000237effb2fe8
Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
MethodTable: 00007ffa96513558
EEClass: 00007ffa966304e8
Size: 40(0x28) bytes
File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
MT Field Offset Type VT Attr Value Name
00007ffa964a85a0 4003502 8 System.Int32 1 instance 2 hashCode
00007ffa964a85a0 4003503 c System.Int32 1 instance -1 next
00007ffa964a85a0 4003504 10 System.Int32 1 instance 2 key
00007ffa964aa238 4003505 0 System.__Canon 0 instance 00000237effb2db0 value
[3] 00000237effb3000
Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
MethodTable: 00007ffa96513558
EEClass: 00007ffa966304e8
Size: 40(0x28) bytes
File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
MT Field Offset Type VT Attr Value Name
00007ffa964a85a0 4003502 8 System.Int32 1 instance 4 hashCode
00007ffa964a85a0 4003503 c System.Int32 1 instance -1 next
00007ffa964a85a0 4003504 10 System.Int32 1 instance 4 key
00007ffa964aa238 4003505 0 System.__Canon 0 instance 00000237effb2db0 value
[4] 00000237effb3018
Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
MethodTable: 00007ffa96513558
EEClass: 00007ffa966304e8
Size: 40(0x28) bytes
File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
MT Field Offset Type VT Attr Value Name
00007ffa964a85a0 4003502 8 System.Int32 1 instance 0 hashCode
00007ffa964a85a0 4003503 c System.Int32 1 instance 0 next
00007ffa964a85a0 4003504 10 System.Int32 1 instance 0 key
00007ffa964aa238 4003505 0 System.__Canon 0 instance 0000000000000000 value
[5] 00000237effb3030
Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
MethodTable: 00007ffa96513558
EEClass: 00007ffa966304e8
Size: 40(0x28) bytes
File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
MT Field Offset Type VT Attr Value Name
00007ffa964a85a0 4003502 8 System.Int32 1 instance 0 hashCode
00007ffa964a85a0 4003503 c System.Int32 1 instance 0 next
00007ffa964a85a0 4003504 10 System.Int32 1 instance 0 key
00007ffa964aa238 4003505 0 System.__Canon 0 instance 0000000000000000 value
[6] 00000237effb3048
Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
MethodTable: 00007ffa96513558
EEClass: 00007ffa966304e8
Size: 40(0x28) bytes
File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
MT Field Offset Type VT Attr Value Name
00007ffa964a85a0 4003502 8 System.Int32 1 instance 0 hashCode
00007ffa964a85a0 4003503 c System.Int32 1 instance 0 next
00007ffa964a85a0 4003504 10 System.Int32 1 instance 0 key
00007ffa964aa238 4003505 0 System.__Canon 0 instance 0000000000000000 value
從內存的結構來看，擴容后bucket數組中使用了下標為0、1、2和4這四個位置，entries中使用了0~3存儲了示例中添加的數據，符合前文中理論分析的結果，兩者相互之間具有良好的印證關係。
時間複雜度分析
時間複雜度表達的是數據結構操作數據的時候所消耗的時間隨着數據集規模的增長的變化趨勢。常用的指標有最好情況時間複雜度、最壞情況時間複雜度和均攤時間複雜度。那麼對於Dictionary<Tkey,TValue>來說，插入和查找過程中這些時間複雜度分別是什麼樣的呢？
最好情況時間複雜度：對於查找來說最好的是元素處於鏈表的頭部，查找效率不會隨着數據規模的增加而增加，因此該複雜度為常量階複雜度，即O(1)；插入操作最理想的情況是數組中有空餘的空間，不需要進行擴容操作，此時時間複雜度也是常量階的，即O(1)；
最壞情況時間複雜度：對於插入來說，比較耗時的操作場景是需要順着鏈表查找符合條件的元素，鏈表越長，查找時間越長（下文稱為場景一）；而對於插入來說最壞的情況是數組長度不足，需要動態擴容並重新組織鏈表結構（下文稱為場景二）；
場景一中時間複雜度隨着鏈表長度的增加而增加，但是Dictionary中規定鏈表的最大長度為100，如果有長度超過100的鏈表就需要擴容並調整鏈表結構，所以順着鏈表查找數據不會隨着數據規模的增長而增長，最大時間複雜度是固定的，因此時間複雜度還是常量階複雜度，即O(1);
場景二中時間複雜度隨着數組中元素的數量增加而增加，如果原來的數組元素為n個，那麼擴容時需要將這n個元素拷貝到新的數組中並計算其在新鏈表中的位置，因此該操作的時間複雜度是隨着數組的長度n的增加而增加的，屬於線性階時間複雜度，即O(n)。
綜合場景一和場景二的分析結果得出最壞情況時間複雜度出現在數據擴容過程中，時間複雜度為O(n)。
最好情況時間複雜度和最壞情況時間複雜度都過於極端，只能描述最好的情況和最壞的情況，那麼在使用過程中如何評價數據結構在大部分情況下的時間複雜度？通常對於複雜的數據結構可以使用均攤時間複雜度來評價這個指標。均攤時間複雜度適用於對於一個數據進行連續操作，大部分情況下時間複雜度都很低，只有個別情況下時間複雜度較高的場景。這些操作存在前後連貫性，這種情況下將較高的複雜度攤派到之前的操作中，一般均攤時間複雜度就相當於最好情況時間複雜度。
通過前面的分析可以看出Dictionary恰好就符合使用均攤時間複雜度分析的場景。以插入操作為例，假設預申請的entries數組長度為n，在第n+1次插入數據時必然會遇到一次數組擴容導致的時間消耗較高的場景。將這次較為複雜的操作的時間均攤到之前的n次操作后，每次操作時間的複雜度也是常量階的，因此Dictionary插入數據時均攤時間複雜度也是O(1)。
實踐建議
首先，Dictionary這種類型適合用於對於數據檢索有明顯目的性的場景，比如讀寫比例比較高的場景。其次，如果有大數據量的場景，最好能夠提前聲明容量，避免多次分配內存帶來的額外的時間和空間上的消耗。因為不進行擴容的場景，插入和查找效率都是常量階O(1)，在引起擴容的情況下，時間複雜度是線性階O(n)。如果僅僅是為了存儲數據，使用Dictionary並不合適，因為它相對於List<T>具有更加複雜的數據結構，這樣會帶來額外的空間上面的消耗。雖然Dictionary<TKey,TValue>的TKey是個任意類型的，但是除非是對於判斷對象是否相等有特殊的要求，否則不建議直接使用自定義類作為Tkey。
總結
C#中的Dictionary<TKey,TValue>是藉助於散列函數構建的高性能數據結構，Dictionary解決散列衝突的方式是使用鏈表來保存散列值存在衝突的節點，俗稱拉鏈法。本文中通過圖文並茂的方式幫助理解Dictionary添加元素和擴容過程這兩個典型的應用場景，在理論分析之後使用windbg分析了內存中的實際結構，以此加深對於這種數據類型的深入理解。隨後在此基礎上分析了Dictionary的時間複雜度。Dictionary的最好情況時間複雜度是O(1)，最壞情況複雜度是O(n)，均攤時間複雜度是O(1)，Dictionary在大多數情況下都是常量階時間複雜度，在內部數組自動擴容過程中會產生明顯的性能下降，因此在實際實踐過程中最好在聲明新對象的時候能夠預估容量，儘力避免數組自動擴容導致的性能下降。
參考資料
- Dictionary<TKey,TValue>源代碼(.net framework4.8版本)
- .NET中Dictionary<TKey, TValue>淺析
- 解決hash衝突的三個方法
- 算法複雜度分析（下）：最好、最壞、平均、均攤等時間複雜度概述
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能
※台北網頁設計公司這麼多該如何選擇?
※智慧手機時代的來臨，RWD網頁設計為架站首選
※評比南投搬家公司費用收費行情懶人包大公開
※幫你省時又省力,新北清潔一流服務好口碑
※回頭車貨運收費標準