Shulou(Shulou.com)06/02 Report--

This article shows you how to analyze the internal implementation of Dictionary in C#. The content is concise and easy to understand, which will definitely brighten your eyes. I hope you can get something through the detailed introduction of this article.

Developers who know Dictionary know that dictionary addition is slower than List, but lookups are faster, so how is Dictionary implemented?

Construction of Dictionary

In the following code, let me see what Dictionary does when it is constructed:

Private void Initialize (int capacity)

{

Int prime = HashHelpers.GetPrime (capacity)

This.buckets = new int [prime]

For (int I = 0; I

< this.buckets.Length; i++) { this.buckets[i] = -1; } this.entries = new Entry[prime]; this.freeList = -1; } 我们看到，Dictionary在构造的时候做了以下几件事： 初始化一个this.buckets = new int[prime] 初始化一个this.entries = new Entry[prime] Bucket和entries的容量都为大于字典容量的一个最小的质数 其中this.buckets主要用来进行Hash碰撞，this.entries用来存储字典的内容，并且标识下一个元素的位置。 我们以Dictionary 为例，来展示一下Dictionary如何添加元素： 首先，我们构造一个: Dictionary test = new Dictionary(6); 初始化后： 添加元素时，集合内部Bucket和entries的变化 Test.Add(4,"4″)后： 根据Hash算法： 4.GetHashCode()%7= 4,因此碰撞到buckets中下标为4的槽上，此时由于Count为0，因此元素放在Entries中第0个元素上，添加后Count变为1 Test.Add(11,"11″) 根据Hash算法 11.GetHashCode()%7=4,因此再次碰撞到Buckets中下标为4的槽上，由于此槽上的值已经不为-1，此时Count=1，因此把这 个新加的元素放到entries中下标为1的数组中，并且让Buckets槽指向下标为1的entries中，下标为1的entry之下下标为0的 entries。 Test.Add(18,"18″) 我们添加18，让HashCode再次碰撞到Buckets中下标为4的槽上，这个时候新元素添加到count+1的位置，并且Bucket槽指向 新元素，新元素的Next指向Entries中下标为1的元素。此时你会发现所有hashcode相同的元素都形成了一个链表，如果元素碰撞次数越多，链 表越长。所花费的时间也相对较多。

Test.Add (19, 19)

Add element 19 again, and the Hash collides with another slot, but the element is still added to the location of the count+1.

Changes within the collection when elements are deleted

Test.Remove (4)

When we delete an element, we delete the current element through a collision and look for it three times along the linked list to find the location of the element whose key is 4. And point the location of FreeList to the location of the currently deleted element, and set FreeCount to 1.

Test.Remove (18)

Delete the element with a Key of 18, still through a collision, and look twice along the linked list to find the current element, delete the current element, and let FreeList point to the current element, and the Next of the current element points to the previous FreeList element.

At this point you will find that FreeList points to a linked list, which does not contain any elements, and FreeCount represents the length of the linked list that does not contain elements.

Test.Add (20, "20")

Add another element, and because the FreeList list is not empty, the dictionary will first be added to the location pointed to by the FreeList list, and the length of the FreeCount minus 1 minus 1 will become 1.

Through the above experiments, we can find that Dictionary is adding and deleting elements as follows:

Through the Hash algorithm to collide with the specified Bucket, colliding with all the data on the same Bucket slot to form a single linked list

By default, the data in the Entries slot is arranged in the order in which it is added.

The deleted data will form a linked list of FreeList. When adding data, priority is given to adding data to the FreeList linked list. If FreeList is empty, it will be arranged in count order.

Dictionary queries and their efficiency depend on the number of collisions, which explains why Dictionary lookups are so fast.

The above content is how to analyze the internal implementation of Dictionary in C#. Have you learned the knowledge or skills? If you want to learn more skills or enrich your knowledge reserve, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.