了解Dictionary的开发者都知道,与List相比,字典的添加会慢一些,但是查找会快一些,那么Dictionary是如何实现的呢?字典构造下面的代码让我看看字典在构造过程中做了什么:privatevoidInitialize(intcapacity){intprime=HashHelpers.GetPrime(capacity);this.buckets=newint[prime];对于(inti=0;i[prime];这个.freeList=-1;}来看看原来Dictionary在构造的时候做了如下事情:大于字典的一个最小素数的容量。this.buckets主要用于Hash碰撞,this.entries用于存放字典内容和标识下一个元素的位置。下面以Dictionary为例,说明如何给Dictionary添加元素:首先构造一个:Dictionarytest=newDictionary(6);初始化后:添加元素时,Test.Add(4,"4")后Bucket和collection中entries的变化:根据Hash算法:4.GetHashCode()%7=4,所以和slot发生碰撞buckets中下标为4,此时由于Count为0,所以元素放在Entries中的第0个元素上。添加后Count变为1Test.Add(11,"11")根据Hash算法11.GetHashCode()%7=4,所以再次碰撞到Buckets下标为4的slot上,因为这个slot上的值为不再是-1,此时Count=1,所以将这个新加入的元素放到entries中下标为1的数组中,让Buckets槽指向下标为1的entry中,with的entry下标为0的entrysubscript1.Test.Add(18,"18")我们加18,让HashCode再次和Buckets中下标为4的slot发生碰撞,此时新元素被添加到count+1的位置,并且Bucket槽指向新元素,新元素Next指向Entries中下标为1的元素。此时,你会发现所有具有相同hashcode的元素组成了一个链表。如果元素碰撞次数增加,链表就会变长。它也需要相对更多的时间。Test.Add(19,"19")再次添加元素19。这时候Hash和另外一个slot碰撞了,但是元素还是加到了count+1的位置。删除元素时集合内部的变化Test.Remove(4)当我们删除一个元素时,我们传递一个碰撞,沿着链表搜索3次,找到key为4的元素的位置,并删除当前元素。并将FreeList的位置指向当前删除元素的位置,设置FreeCount为1Test.Remove(18)删除Key为18的元素,依然通过碰撞,沿链表查找2次,找到当前元素,删除当前元素,让FreeList指向当前元素,当前元素的Next指向上一个FreeList元素。此时你会发现FreeList指向一个不包含任何元素的链表,FreeCount表示不包含元素的链表的长度。Test.Add(20,"20")添加另一个元素。此时由于FreeList链表不为空,所以会先将字典添加到FreeList链表指向的位置。添加后FreeCount减1,FreeList链表长度变为1。总结:通过上面的测试,我们可以发现Dictionary在增删元素的过程如下:使用Hash算法进行碰撞指定的Bucket,与同一个Bucket槽中的所有数据碰撞形成单链表。默认情况下,Entries槽中的数据按照添加的顺序排列删除的数据,会形成一个FreeList链表。添加数据时,先向FreeList链表添加数据。如果FreeList为空,字典查询会按照count排序,效率取决于碰撞次数。这也解释了为什么Dictionarylookup会很快。好吧,我已经起来了很长时间了,所以我今天要写这个。如果您从阅读中有所收获,请帮助我。如有任何疑问,欢迎拍砖。