设为首页 加入收藏

TOP

一步一步剖析Dictionary实现原理(一)
2019-10-11 11:20:01 】 浏览:600
Tags:步一步 剖析 Dictionary 实现 原理

目录

  • 关键的字段和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
        }

****************************************************************************************************************************
首页 上一页 1 2 3 4 下一页 尾页 1/4/4
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇没有了 下一篇vscode解决nuget插件不能使用的问..

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目