了解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会很快。好吧，我已经起来了很长时间了，所以我今天要写这个。如果您从阅读中有所收获，请帮助我。如有任何疑问，欢迎拍砖。
