.NET中DictionaryTKey, TValue浅析

作者:盐城市天行软件有限公司  来源:www.szgjp.com未知  发布时间:2017-09-10 10:11:24
.NET中DictionaryTKey, TValue浅析 .NET中Dictionary<TKey, Tvalue>是非常常用的key-value的数据结构,也就是其实就是传说中的哈希表。.NET中还有一个叫做Hashtable的类型,两个类型都是哈希表。这两个类型都可以实现键值对存储的功能,区别就是一个是泛型一个不是并且内部实现有一些不同。今天就研究一下.NET中的Dictionary<TKey, TValue>以及一些相关问题。

文中如有错误,望指出。

什么是哈希表

Wikipedia中对于Hash table的定义是这样的:

In computing, a hash table (also hash map) is a data structure used to implement an associative array, a structure that can map keys to values.

它是一个通过关键字直接访问内存存储位置的数据结构,这是一个所有数据结构教科书里都会有的一个数据结构,这里不做太多的研究。但是有几个概念还是要提一下,因为对于我们理解Dictionary的内部实现很大作用。

更多哈希表的内容:Wikipedia,Hashtable 博客

碰撞(Collision)及处理

由于我们在数据结构中采用的哈希算法不是一个完美的哈希算法,同时我们会限制我们用来存储的内存空间。所以发生碰撞是不可能避免的,所以很处理如何碰撞就是设计哈希表的时候需要考虑的一个很重要的因素。

处理碰撞有很多方法,例如开放寻址法(Open Adressing),分离链接法(Separate chaining)。Dictionary中采用的是一个叫做Separate chaining with linked lists的方法。

通过下面这个Wikipedia上的图就可以很清楚的认识到这是一个什么样子的方法。

分离链接法例子

利用两个数组,buckets数组只保存一个地址,这个地址指向的是entries数组中的一个实例(entry)。当哈希值冲突的时候则需要往当前指向的那个实例的链表的末端添加一个新实例即可。

装填因子(Load Factor)

装填因子的存在是因为在开放定址方法中,当数组中的内容越来越多的时候则冲突的概率就会越来越大,而在开放定址方法中冲突的解决方案是采用探测法,而这种冲突会带来性能的极大损失。wikipedia中的这张图比较了分散链接和线性探测法在不同装填因子的情况下CPU缓存不命中的对应关系。

cpu cach miss - load factor

在Dictionary采用的这种方法里,装填因子并不是一个重要的因素不会对性能有太大影响,所以Dictionary默认使用了1并认为没有必要提供任何接口去设置这个值。

Dictionary内部如何实现

先来介绍几个在Dictionary中重要的变量:

int[] buckets 和 Entry[] entries

IEqualityComparer<TKey> comparer

.

这两个就是在上面提到的两个数组,所谓的 Separate chaining with linked lists。

在往Dictionary中添加一对新值的时候需要计算key的Hashcode,冲突的时候也需要判断两个value是不是相等。这个comparer就是来做这个事情的,那么这里为什么不直接调用key重载的GetHashCode和Equal方法呢?这个会在下文中讲到。

插入

通过一个例子来说明Dictionary在插入的时候做了什么。

Dictionary<int, string=""> dict = new Dictionary<int, string="">();

dict.Add(0, "zero");

dict.Add(12, "twelve");

dict.Add(15, "fiften");

dict.Add(4, "four");

下面这张“图”能够看出两个数组在插入操作中的变化,结合源代码细细品味就能知道发生了什么。

--------- ---------

|buckets| |entries|

|-------| |-------|

| 0 | | -->| hashcode=0,key=0,next=-1,value="zero"

|-------| |-------|

| -1 | | empty |

|-------| |-------|

| -1 | | empty |

|-------| |-------|

--------- ---------

|buckets| |entries|

|-------| |-------|

| 1 | | -->| hashcode=0,key=0,next=-1,value="zero"

|-------| |-------|

| -1 | | -->| hashcode=12,key=12,next=0,value="twelve"

|-------| |-------|

| -1 | | empty |

|-------| |-------|

--------- ---------

|buckets| |entries|

|-------| |-------|

| 2 | | -->| hashcode=0,key=0,next=-1,value="zero"

|-------| |-------|

| -1 | | -->| hashcode=12,key=12,next=0,value="twelve"

|-------| |-------|

| -1 | | -->| hashcode=15,key=15,next=1,value="fiften"

|-------| |-------|

--------- ---------

|buckets| |entries|

|-------| |-------|

| 0 | | -->| hashcode=0,key=0,next=-1,value="zero"

|-------| |-------|

| 2 | | -->| hashcode=12,key=12,next=-1,value="twelve"

|-------| |-------|

| -1 | | -->| hashcode=15,key=15,next=-1,value="fiften"

|-------| |-------|

| -1 | | -->| hashcode=4,key=4,next=-1,value="four"

|-------| |-------|

| 3 | | empty |

|-------| |-------|

| 1 | | empty |

|-------| |-------|

| -1 | | empty |

|-------| |-------|

扩容

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:武汉网站建设 https://www.feimao666.com


上一篇:Python KNN算法
下一篇:最后一页