设为首页 加入收藏

TOP

一步一步剖析Dictionary实现原理(四)
2019-10-11 11:20:01 】 浏览:595
Tags:步一步 剖析 Dictionary 实现 原理
es[i].next) {
if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i; }

 4. 移除键值(Remove)

        public bool Remove(TKey key) {
            if(key == null) {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
            }
            if (buckets != null) {
                int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
                int bucket = hashCode % buckets.Length;
                int last = -1;
                //其原理先取出键值,然后记录entries空闲的索引(freeList)和空闲个数(freeCount)
                for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next)  {
                    if (entries[i].hashCode == hashCode &&  comparer.Equals(entries[i].key, key)) {
                        if (last < 0) {
                            buckets[bucket] = entries[i].next;
                        }
                        else {
                            entries[last].next = entries[i].next;
                        }
                        entries[i].hashCode = -1;
                        //建立空闲链表
                        entries[i].next = freeList;
                        entries[i].key = default(TKey);
                        entries[i].value = default(TValue);
                        //保存entryies中空元素的索引
                        //便于插入新键值时,放在当前索引的位置,减少entryies空间上的浪费
                        freeList = i;
                        //空元素的个数加1
                        freeCount++;
                        version++;
                        return true;
                    }
                }
            }
            return false;
        }
*******************************************************************
        static void Foo()
        {
            ......
            //移除
            new List<int> { 22, 29 }.ForEach(item => dicData.Remove(item));
        } 

4.1 移除Key=22后,freeList = 3, freeCount = 1,

 4.2 移除Key=36后,freeList = 5, freeCount = 2, 

 5. 再插入键值

如上图,当移除掉{36,36}后,会发现又诞生一个含有两个元素的“新链表”(上图灰色框)。这个作用就是为了插入新键值时,按照“新链表”记录的索引顺序插入到entries数组中。
例:添加键值{22,22},{25,25},此时freeList = 5,freeCount = 2;
  1. 给entries[5]赋值,freeList = 3, freeCount = 1;
  2. 给entries[3]赋值,freeList = -1, freeCount = 0;

 

 希望此文能够让你对于Dictionary内部实现有所认识。

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

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目