目录

• 关键的字段和Entry结构
• 添加键值（Add）
• 取键值（Find）
• 移除键值（Remove）
• 再插入键值

　　本文是对c#中Dictionary内部实现原理进行简单的剖析。如有表述错误，欢迎指正。

　　主要对照源码来解析，目前对照源码的版本是.Net Framwork 4.8，源码地址。

1. 关键的字段和Entry结构

        struct Entry
        {
            public int hashCode;    // key的hashCode & 0x7FFFFFFF
            public int next;            // 指向链表下一个元素的地址（实际就是entries的索引），最后一个元素为-1
            public TKey key;
            public TValue value;
        }
        Entry[] entries;        //存放键值
        int[] buckets;          //存储entries最新元素的索引,其存储位置由取模结果决定。例：假设键值存储在entries的第1元素的位置上，且hashCode和长度的取模结果为2，那么buckets[2] = 1
        int count = 0;         //已存储键值的个数
        int version;             //记录版本，防止迭代过程中集合被更改
        IEqualityComparer<TKey> _comparer;    
        int freeList;             //entries中最新空元素的索引
        int freeCount;         //entries中空元素的个数

2. 添加键值（Add）

        public void Add(TKey key, TValue value) {
            Insert(key, value, true);
        }


        private void Insert(TKey key, TValue value, bool add) {
        
            if( key == null ) {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
            }
            if (buckets == null) Initialize(0);
            int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
            //取模
            int targetBucket = hashCode % buckets.Length;
#if FEATURE_RANDOMIZED_STRING_HASHING
            int collisionCount = 0;
#endif
            for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) {
                if (entries[i].hashCode == hashCode &&  comparer.Equals(entries[i].key, key)) {
                    if (add) {
                         ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
                    }
                    //对于已存在的Key重新赋值
                    entries[i].value = value;
                    version++;
                    return;
                }
#if FEATURE_RANDOMIZED_STRING_HASHING
                collisionCount++;
#endif
            }
            int index;
            if (freeCount > 0) {
                //存在entries中存在空元素
                index = freeList;
                freeList = entries[index].next;
                freeCount--;
            }
            else {
                if (count == entries.Length)
                {
                    //扩容：取大于count * 2的最小素数作为entries和bucket的新容量（即数组长度.Length）
                    Resize();
                    targetBucket = hashCode % buckets.Length;
                }
                index = count;
                count++;
            }
            entries[index].hashCode = hashCode;
            entries[index].next = buckets[targetBucket];
            entries[index].key = key;
            entries[index].value = value;
            //存取链表的头元素的索引（即entries最后存入的元素的在enties中的索引）
            //便于取Key的时每次从链表的头元素开始遍历，详细见FindEntry(TKey key)函数
            buckets[targetBucket] = index;
            version++;
#if FEATURE_RANDOMIZED_STRING_HASHING
#if FEATURE_CORECLR
            // In case we hit the collision threshold we'll need to switch to the  comparer which is using randomized string hashing
            // in this case will be EqualityComparer<string>.Default.
            // Note, randomized string hashing is turned on by default on coreclr so  EqualityComparer<string>.Default will
            // be using randomized string hashing
            if (collisionCount > HashHelpers.HashCollisionThreshold && comparer ==  NonRandomizedStringEqualityComparer.Default)
            {
                comparer = (IEqualityComparer<TKey>)  EqualityComparer<string>.Default;
                Resize(entries.Length, true);
            }
#else
            if(collisionCount > HashHelpers.HashCollisionThreshold &&  HashHelpers.IsWellKnownEqualityComparer(comparer))
            {
                //如果碰撞次数（单链表长度）大于设置的最大碰撞阈值，需要扩容
                comparer = (IEqualityComparer<TKey>)  HashHelpers.GetRandomizedEqualityComparer(comparer);
                Resize(entries.Length, true);
            }
#endif // FEATURE_CORECLR
#endif
        }

****************************************************************************************************************************