深入解读Dictionary
source link: http://mp.weixin.qq.com/s?__biz=MzI1NDc0ODMzNg%3D%3D&%3Bmid=2247484754&%3Bidx=1&%3Bsn=346a32c689b3aef317426e339d2ac5d7
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
深入解读Dictionary
Dictionary<TKey,TValue>
是日常.net开发中最常用的数据类型之一,基本上遇到键值对类型的数据时第一反应就是使用这种散列表。散列表特别适合快速查找操作,查找的效率是常数阶O(1)。那么为什么这种数据类型的查找效率能够这么高效?它背后的数据类型是如何支撑这种查找效率的?它在使用过程中有没有什么局限性?一起来探究下这个数据类型的奥秘吧。
本文内容针对的是 .Net Framework 4.5.1
的代码实现,在其他.Net版本中或多或少都会有些差异,但是基本的原理还是相同的。
本文的内容主要分为三个部分,第一部分是从代码的角度来分析并以图文并茂的方式通俗的解释Dictionary如何解决的散列冲突并实现高效的数据插入和查找。第二部分名为“眼见为实”,由于第一部分是从代码层面分析Dictionary的实现,侧重于理论分析,因此第二部分使用windbg直接分析内存结构,跟第一部分的理论分析相互印证,加深对于这种数据类型的深入理解。最后是从数据结构的时间复杂度的角度进行分析并提出了几条实践建议。
本文内容:
-
第一部分 代码分析
-
散列冲突
-
Dictionary代码解析
-
Dictionary操作实例分析
-
-
第二部分 眼见为实
-
添加第一个元素后的内存结构
-
添加第四个元素后的内存结构
-
-
第三部分
-
时间复杂度分析
-
实践建议
-
散列冲突
提到散列表,就不能不提散列冲突。由于哈希算法被计算的数据是无限的,而计算后的结果范围有限,因此总会存在不同的数据经过计算后得到的值相同,这就是哈希冲突。(两个不同的数据计算后的结果一样)。散列冲突的解决方案有好几个,比如开放寻址法、链式寻址法。
Dictionary使用的是链式寻址法,也叫做拉链法。拉链法的基本思想是将散列值相同的数据存在同一个链表中,如果有散列值相同的元素,则加到链表的头部。同样道理,在查找元素的时候,先计算散列值,然后在对应散列值的链表中查找目标元素。
用图来表达链式寻址法的思想:
Dictionary 的内部数据结构
Dictionary的内部存储数据主要是依赖了两个数组,分别是 int[] buckets
和 Entry[] entries
。其中 buckets
是Dictionary所有操作的入口,类似于上文中解说拉链法所用的图中的那个竖着的数据结构。 Entry
是一个结构体,用于封装所有的元素并且增加了next字段用于构建链表数据结构。为了便于理解,下文中截取了一段相关的源代码并增加了注释。
1//数据在Dictionary<TKey,TValue>的存储形式,所有的键值对在Dictionary<TKey,TValue>都是被包装成一个个的Entry保存在内存中 2private struct Entry { 3 public int hashCode; // 散列计算结果的低31位数,默认值为-1 4 public int next; // 下一个Entry的索引值,链表的最后一个Entry的next为-1 5 public TKey key; // Entry对象的Key对应于传入的TKey 6 public TValue value; // Entry对象的Value对应与传入的TValue 7} 8 9private int[] buckets; //hashCode桶,是查找所有Entry的第一级数据结构 10private Entry[] entries; //保存真正的数据
下文中以 Dictionary<int,string>
为例,分析 Dictionary
在使用过程中内部数据的组织方式。
Dictionary初始化
初始化代码:
1Dictionary<int, string> dictionary = new Dictionary<int, string>();
Dictionary
的初始化时, buckets
和 entries
的长度都是0。
添加一个元素
1dictionary.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 添加第一个元 素
添加第二个元素
1dictionary.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添加第二个元素
添加第三个元素
1dictionary.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添加第三个元素
添加第四个元素
1dictionary.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
的内容数据结构:
第二次扩容后的Dictionary
添加元素
当前已经完成了 entries
和 bucket
数组的扩容,有了充裕的空间来存储新的元素,所以可以在新的数据结构的基础上继续添加元素。
当向 Dictionary
中添加第四个元素后,内部数据结构是这样的:
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添加第一个元素后的内存结构
执行代码:
1Dictionary<int, string> dic = new Dictionary<int, string>(); 2dic.Add(1, "xyxy"); 3Console.Read();
打开windbg附加到该进程(由于使用的是控制台应用程序,当前线程是0号线程,因此如果附加进程后默认的不是0号线程时执行 ~0s
切换到0号线程),执行 !clrstack -l
查看当前线程及线程上使用的所有变量:
10:000> !clrstack -l 2OS Thread Id: 0x48b8 (0) 3 Child SP IP Call Site 40000006de697e998 00007ffab577c134 [InlinedCallFrame: 0000006de697e998] Microsoft.Win32.Win32Native.ReadFile(Microsoft.Win32.SafeHandles.SafeFileHandle, Byte*, Int32, Int32 ByRef, IntPtr) 50000006de697e998 00007ffa96abc9c8 [InlinedCallFrame: 0000006de697e998] Microsoft.Win32.Win32Native.ReadFile(Microsoft.Win32.SafeHandles.SafeFileHandle, Byte*, Int32, Int32 ByRef, IntPtr) 60000006de697e960 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 7DomainNeutralILStubClass.IL_STUB_PInvoke(Microsoft.Win32.SafeHandles.SafeFileHandle, Byte*, Int32, Int32 ByRef, IntPtr) 8 90000006de697ea40 00007ffa972d39ec System.IO.__ConsoleStream.ReadFileNative(Microsoft.Win32.SafeHandles.SafeFileHandle, Byte[], Int32, Int32, Boolean, Boolean, Int32 ByRef) 10 LOCALS: 11 <no data> 12 <no data> 13 <no data> 14 <no data> 15 <no data> 16 <no data> 17 180000006de697ead0 00007ffa972d38f5 System.IO.__ConsoleStream.Read(Byte[], Int32, Int32) 19 LOCALS: 20 <no data> 21 <no data> 22 230000006de697eb30 00007ffa96a882d4 System.IO.StreamReader.ReadBuffer() 24 LOCALS: 25 <no data> 26 <no data> 27 280000006de697eb80 00007ffa97275f23 System.IO.StreamReader.Read() 29 LOCALS: 30 <no data> 31 320000006de697ebb0 00007ffa9747a2fd System.IO.TextReader+SyncTextReader.Read() 33 340000006de697ec10 00007ffa97272698 System.Console.Read() 35 360000006de697ec40 00007ffa38670909 ConsoleTest.DictionaryDebug.Main(System.String[]) 37 LOCALS: 38 0x0000006de697ec70 = 0x00000215680d2dd8 39 400000006de697ee88 00007ffa97ba6913 [GCFrame: 0000006de697ee88]
通过对于线程堆栈的分析很容易看出当前线程上使用了一个局部变量,地址为: 0x000001d86c972dd8
,使用 !do
命令查看该变量的内容:
10:000> !do 0x00000215680d2dd8 2Name: System.Collections.Generic.Dictionary`2[[System.Int32, mscorlib],[System.String, mscorlib]] 3MethodTable: 00007ffa96513328 4EEClass: 00007ffa9662f610 5Size: 80(0x50) bytes 6File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll 7Fields: 8 MT Field Offset Type VT Attr Value Name 900007ffa964a8538 4001887 8 System.Int32[] 0 instance 00000215680d2ee8 buckets 1000007ffa976c4dc0 4001888 10 ...non, mscorlib]][] 0 instance 00000215680d2f10 entries 1100007ffa964a85a0 4001889 38 System.Int32 1 instance 1 count 1200007ffa964a85a0 400188a 3c System.Int32 1 instance 1 version 1300007ffa964a85a0 400188b 40 System.Int32 1 instance -1 freeList 1400007ffa964a85a0 400188c 44 System.Int32 1 instance 0 freeCount 1500007ffa96519630 400188d 18 ...Int32, mscorlib]] 0 instance 00000215680d2ed0 comparer 1600007ffa964c6ad0 400188e 20 ...Canon, mscorlib]] 0 instance 0000000000000000 keys 1700007ffa977214e0 400188f 28 ...Canon, mscorlib]] 0 instance 0000000000000000 values 1800007ffa964a5dd8 4001890 30 System.Object 0 instance 0000000000000000 _syncRoot
从内存结构来看,该变量中就是我们查找的Dic存在buckets、entries、count、version等字段,其中buckets和entries在上文中已经有多次提及,也是本文的分析重点。既然要眼见为实,那么buckets和entries这两个数组的内容到底是什么样的呢?这两个都是数组,一个是int数组,另一个是结构体数组,对于这两个内容分别使用 !da
命令查看其内容:
首先是buckets的内容:
10:000> !da -start 0 -details 00000215680d2ee8 2Name: System.Int32[] 3MethodTable: 00007ffa964a8538 4EEClass: 00007ffa966160e8 5Size: 36(0x24) bytes 6Array: Rank 1, Number of elements 3, Type Int32 7Element Methodtable: 00007ffa964a85a0 8[0] 00000215680d2ef8 9 Name: System.Int32 10 MethodTable: 00007ffa964a85a0 11 EEClass: 00007ffa96616078 12 Size: 24(0x18) bytes 13 File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll 14 Fields: 15 MT Field Offset Type VT Attr Value Name 16 00007ffa964a85a0 40005a2 0 System.Int32 1 instance -1 m_value 17[1] 00000215680d2efc 18 Name: System.Int32 19 MethodTable: 00007ffa964a85a0 20 EEClass: 00007ffa96616078 21 Size: 24(0x18) bytes 22 File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll 23 Fields: 24 MT Field Offset Type VT Attr Value Name 25 00007ffa964a85a0 40005a2 0 System.Int32 1 instance 0 m_value 26[2] 00000215680d2f00 27 Name: System.Int32 28 MethodTable: 00007ffa964a85a0 29 EEClass: 00007ffa96616078 30 Size: 24(0x18) bytes 31 File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll 32 Fields: 33 MT Field Offset Type VT Attr Value Name 34 00007ffa964a85a0 40005a2 0 System.Int32 1 instance -1 m_value
当前buckets中有三个值,分别是:-1、0和-1,其中-1是数组初始化后的默认值,而下表为1的位置的值0则是上文中添加 dic.Add(1, "xyxy");
这个指令的结果,代表其对应的链表首节点在entries数组中下标为0的位置,那么entries数组中的数值是什么样子的呢?
10:000> !da -start 0 -details 00000215680d2f10 2Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]][] 3MethodTable: 00007ffa965135b8 4EEClass: 00007ffa9662d1f0 5Size: 96(0x60) bytes 6Array: Rank 1, Number of elements 3, Type VALUETYPE 7Element Methodtable: 00007ffa96513558 8[0] 00000215680d2f20 9 Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]] 10 MethodTable: 00007ffa96513558 11 EEClass: 00007ffa966304e8 12 Size: 40(0x28) bytes 13 File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll 14 Fields: 15 MT Field Offset Type VT Attr Value Name 16 00007ffa964a85a0 4003502 8 System.Int32 1 instance 1 hashCode 17 00007ffa964a85a0 4003503 c System.Int32 1 instance -1 next 18 00007ffa964a85a0 4003504 10 System.Int32 1 instance 1 key 19 00007ffa964aa238 4003505 0 System.__Canon 0 instance 00000215680d2db0 value 20[1] 00000215680d2f38 21 Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]] 22 MethodTable: 00007ffa96513558 23 EEClass: 00007ffa966304e8 24 Size: 40(0x28) bytes 25 File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll 26 Fields: 27 MT Field Offset Type VT Attr Value Name 28 00007ffa964a85a0 4003502 8 System.Int32 1 instance 0 hashCode 29 00007ffa964a85a0 4003503 c System.Int32 1 instance 0 next 30 00007ffa964a85a0 4003504 10 System.Int32 1 instance 0 key 31 00007ffa964aa238 4003505 0 System.__Canon 0 instance 0000000000000000 value 32[2] 00000215680d2f50 33 Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]] 34 MethodTable: 00007ffa96513558 35 EEClass: 00007ffa966304e8 36 Size: 40(0x28) bytes 37 File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll 38 Fields: 39 MT Field Offset Type VT Attr Value Name 40 00007ffa964a85a0 4003502 8 System.Int32 1 instance 0 hashCode 41 00007ffa964a85a0 4003503 c System.Int32 1 instance 0 next 42 00007ffa964a85a0 4003504 10 System.Int32 1 instance 0 key 43 00007ffa964aa238 4003505 0 System.__Canon 0 instance 0000000000000000 value
通过对于entries数组的分析可以看出,这个数组也有三个值,其中下标为0的位置已经填入相关内容,比如hashCode为1,key为1,其中value的内容是一个内存地址: 000001d86c972db0
,这个地址指向的就是字符串对象,它的内容是 xyxy
,使用 !do
指令来看下具体内容:
10:000> !do 00000215680d2db0 2Name: System.String 3MethodTable: 00007ffcc6b359c0 4EEClass: 00007ffcc6b12ec0 5Size: 34(0x22) bytes 6File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll 7String: xyxy 8Fields: 9 MT Field Offset Type VT Attr Value Name 1000007ffcc6b385a0 4000283 8 System.Int32 1 instance 4 m_stringLength 1100007ffcc6b36838 4000284 c System.Char 1 instance 78 m_firstChar 1200007ffcc6b359c0 4000288 e0 System.String 0 shared static Empty
简要分析扩容后的内存结构
此次执行的代码为:
1Dictionary<int, string> dic = new Dictionary<int, string>(); 2dic.Add(1, "xyxy"); 3dic.Add(7, "xyxy"); 4dic.Add(2, "xyxy"); 5dic.Add(4, "xyxy"); 6Console.Read();
同样采取附加进程的方式分析这段代码执行后的内存结构,本章节中忽略掉如何查找Dictionary变量地址的部分,直接分析buckets数组和entries数组的内容。
首先是buckets数组的内存结构:
10:000> !da -start 0 -details 0000019a471a54f8 2Name: System.Int32[] 3MethodTable: 00007ffcc6b38538 4EEClass: 00007ffcc6ca60e8 5Size: 52(0x34) bytes 6Array: Rank 1, Number of elements 7, Type Int32 7Element Methodtable: 00007ffcc6b385a0 8[0] 0000019a471a5508 9 Name: System.Int32 10 MethodTable: 00007ffcc6b385a0 11 EEClass: 00007ffcc6ca6078 12 Size: 24(0x18) bytes 13 File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll 14 Fields: 15 MT Field Offset Type VT Attr Value Name 16 00007ffcc6b385a0 40005a2 0 System.Int32 1 instance 1 m_value 17[1] 0000019a471a550c 18 Name: System.Int32 19 MethodTable: 00007ffcc6b385a0 20 EEClass: 00007ffcc6ca6078 21 Size: 24(0x18) bytes 22 File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll 23 Fields: 24 MT Field Offset Type VT Attr Value Name 25 00007ffcc6b385a0 40005a2 0 System.Int32 1 instance 0 m_value 26[2] 0000019a471a5510 27 Name: System.Int32 28 MethodTable: 00007ffcc6b385a0 29 EEClass: 00007ffcc6ca6078 30 Size: 24(0x18) bytes 31 File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll 32 Fields: 33 MT Field Offset Type VT Attr Value Name 34 00007ffcc6b385a0 40005a2 0 System.Int32 1 instance 2 m_value 35[3] 0000019a471a5514 36 Name: System.Int32 37 MethodTable: 00007ffcc6b385a0 38 EEClass: 00007ffcc6ca6078 39 Size: 24(0x18) bytes 40 File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll 41 Fields: 42 MT Field Offset Type VT Attr Value Name 43 00007ffcc6b385a0 40005a2 0 System.Int32 1 instance -1 m_value 44[4] 0000019a471a5518 45 Name: System.Int32 46 MethodTable: 00007ffcc6b385a0 47 EEClass: 00007ffcc6ca6078 48 Size: 24(0x18) bytes 49 File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll 50 Fields: 51 MT Field Offset Type VT Attr Value Name 52 00007ffcc6b385a0 40005a2 0 System.Int32 1 instance 3 m_value 53[5] 0000019a471a551c 54 Name: System.Int32 55 MethodTable: 00007ffcc6b385a0 56 EEClass: 00007ffcc6ca6078 57 Size: 24(0x18) bytes 58 File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll 59 Fields: 60 MT Field Offset Type VT Attr Value Name 61 00007ffcc6b385a0 40005a2 0 System.Int32 1 instance -1 m_value 62[6] 0000019a471a5520 63 Name: System.Int32 64 MethodTable: 00007ffcc6b385a0 65 EEClass: 00007ffcc6ca6078 66 Size: 24(0x18) bytes 67 File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll 68 Fields: 69 MT Field Offset Type VT Attr Value Name 70 00007ffcc6b385a0 40005a2 0 System.Int32 1 instance -1 m_value
然后是entries的内存结构:
10:000> !da -start 0 -details 00000237effb2fa8 2Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]][] 3MethodTable: 00007ffa965135b8 4EEClass: 00007ffa9662d1f0 5Size: 192(0xc0) bytes 6Array: Rank 1, Number of elements 7, Type VALUETYPE 7Element Methodtable: 00007ffa96513558 8[0] 00000237effb2fb8 9 Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]] 10 MethodTable: 00007ffa96513558 11 EEClass: 00007ffa966304e8 12 Size: 40(0x28) bytes 13 File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll 14 Fields: 15 MT Field Offset Type VT Attr Value Name 16 00007ffa964a85a0 4003502 8 System.Int32 1 instance 1 hashCode 17 00007ffa964a85a0 4003503 c System.Int32 1 instance -1 next 18 00007ffa964a85a0 4003504 10 System.Int32 1 instance 1 key 19 00007ffa964aa238 4003505 0 System.__Canon 0 instance 00000237effb2db0 value 20[1] 00000237effb2fd0 21 Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]] 22 MethodTable: 00007ffa96513558 23 EEClass: 00007ffa966304e8 24 Size: 40(0x28) bytes 25 File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll 26 Fields: 27 MT Field Offset Type VT Attr Value Name 28 00007ffa964a85a0 4003502 8 System.Int32 1 instance 7 hashCode 29 00007ffa964a85a0 4003503 c System.Int32 1 instance -1 next 30 00007ffa964a85a0 4003504 10 System.Int32 1 instance 7 key 31 00007ffa964aa238 4003505 0 System.__Canon 0 instance 00000237effb2db0 value 32[2] 00000237effb2fe8 33 Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]] 34 MethodTable: 00007ffa96513558 35 EEClass: 00007ffa966304e8 36 Size: 40(0x28) bytes 37 File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll 38 Fields: 39 MT Field Offset Type VT Attr Value Name 40 00007ffa964a85a0 4003502 8 System.Int32 1 instance 2 hashCode 41 00007ffa964a85a0 4003503 c System.Int32 1 instance -1 next 42 00007ffa964a85a0 4003504 10 System.Int32 1 instance 2 key 43 00007ffa964aa238 4003505 0 System.__Canon 0 instance 00000237effb2db0 value 44[3] 00000237effb3000 45 Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]] 46 MethodTable: 00007ffa96513558 47 EEClass: 00007ffa966304e8 48 Size: 40(0x28) bytes 49 File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll 50 Fields: 51 MT Field Offset Type VT Attr Value Name 52 00007ffa964a85a0 4003502 8 System.Int32 1 instance 4 hashCode 53 00007ffa964a85a0 4003503 c System.Int32 1 instance -1 next 54 00007ffa964a85a0 4003504 10 System.Int32 1 instance 4 key 55 00007ffa964aa238 4003505 0 System.__Canon 0 instance 00000237effb2db0 value 56[4] 00000237effb3018 57 Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]] 58 MethodTable: 00007ffa96513558 59 EEClass: 00007ffa966304e8 60 Size: 40(0x28) bytes 61 File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll 62 Fields: 63 MT Field Offset Type VT Attr Value Name 64 00007ffa964a85a0 4003502 8 System.Int32 1 instance 0 hashCode 65 00007ffa964a85a0 4003503 c System.Int32 1 instance 0 next 66 00007ffa964a85a0 4003504 10 System.Int32 1 instance 0 key 67 00007ffa964aa238 4003505 0 System.__Canon 0 instance 0000000000000000 value 68[5] 00000237effb3030 69 Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]] 70 MethodTable: 00007ffa96513558 71 EEClass: 00007ffa966304e8 72 Size: 40(0x28) bytes 73 File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll 74 Fields: 75 MT Field Offset Type VT Attr Value Name 76 00007ffa964a85a0 4003502 8 System.Int32 1 instance 0 hashCode 77 00007ffa964a85a0 4003503 c System.Int32 1 instance 0 next 78 00007ffa964a85a0 4003504 10 System.Int32 1 instance 0 key 79 00007ffa964aa238 4003505 0 System.__Canon 0 instance 0000000000000000 value 80[6] 00000237effb3048 81 Name: System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]] 82 MethodTable: 00007ffa96513558 83 EEClass: 00007ffa966304e8 84 Size: 40(0x28) bytes 85 File: C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll 86 Fields: 87 MT Field Offset Type VT Attr Value Name 88 00007ffa964a85a0 4003502 8 System.Int32 1 instance 0 hashCode 89 00007ffa964a85a0 4003503 c System.Int32 1 instance 0 next 90 00007ffa964a85a0 4003504 10 System.Int32 1 instance 0 key 91 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 源代码(.net framework4.8版本)
-
.NET中Dictionary 浅析
-
解决hash冲突的三个方法
-
算法复杂度分析(下):最好、最坏、平均、均摊等时间复杂度概述
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK