原 NET中dictionary的一个小坑

问题描述:前段时间做个东西,打算在dictionary上按顺序扫描,不复合key条件的元素移动到末尾,然后减少计数,计算下 一个元素。目的就是一遍扫描实现对key的分组处理,减少遍历次数。然而程序表现与预想中不一致,表现

                 出来 就 是移除再插入的顺序和处理前的顺序一致。

                复现后的场景:

                  移除顺序对添加的顺序有影响。

原因:

        产生这个问题的原因在于Dictionary内部的实现机制,简单来说dictionary中维护了一个bucket数组和entry数组,

       前者用于key的hash定位,后者负责数据存储,一个freelist维护了一个当前空位入口。至于细节请参考这篇博客

http://www.cnblogs.com/1-2-3/archive/2010/10/25/generic-dictionary-source-part2.html

        查看源码中移除代码:

        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;               
                 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);                        
                         freeList = i;                        
                         freeCount++;                        
                         version++;                        
                         return true;
                    }
                }
            }            
            return false;
        }

         字典每次移除都会清空当前entry并将entry并入空闲索引链接中,指针指向上一个空位,当前entry作为索引链接的入口。

Add的方法源码截取:

            int index;            
            if (freeCount > 0) 
            {                
            index = freeList;               
            freeList = entries[index].next;  
            freeCount--;
            }            
            else {                
            if (count == entries.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;            
            buckets[targetBucket] = index;            
            version++;

代码中首先需要获取到空闲位置,index=freeList中获取了最近移除的位置。后边对这个entry进行赋值了。

在看dictionary中获取顺序的代码截取:

  while ((uint)index < (uint)dictionary.count) 
  {                    
      if (dictionary.entries[index].hashCode >= 0) 
      {                        
           current = new KeyValuePair<TKey, TValue>(dictionary.entries[index].key, dictionary.entries[index].value);                        
            index++;                        
            return true;
       }
   }

位置是在enrties块上面进行顺序读取的。

分析:

       结合三段代码分析,当移除一个键的时候,当前块会成为空白块的入口,再次添加键的时候会重新占据这个位置。这可以解释我碰到的死循环问题。

     图解中可以看出这种情况的原因。结果符合预期的。dictionary中的顺序是不可信任的,如果一定要使用,需要考虑全面些。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏何俊林

Android开发基础规范(二)

前言:Android中一些开发规范,避免给自己和别人少留坑。 二、代码相关 2.2.15 Field Ordering 属性排序 在类文件顶部声明的任何属性都...

1957
来自专栏自动化测试实战

flask第二十五篇——控制语句

23112
来自专栏二进制文集

Google Protocol Buffers 数据交换协议

protobuf(Protocol Buffers)是Google推出的一个结构化数据交换协议,用于传递自定义的消息格式,可用于同一台机器的进程间、不同设备进程...

1993
来自专栏大内老A

ASP.NET Core中的依赖注入(5): ServiceProvider实现揭秘 【总体设计 】

本系列前面的文章我们主要以编程的角度对ASP.NET Core的依赖注入系统进行了详细的介绍,如果读者朋友们对这些内容具有深刻的理解,我相信你们已经可以正确是使...

2086
来自专栏Android常用基础

Android中的ClassLoader分析

Dalvik是Google公司自己设计用于Android平台的Java虚拟机。它可以支持已转换为.dex(即Dalvik Executable)格式的Java应...

2641
来自专栏猿份到

LeakCanary源码浅析

在Android开发中最让人们头疼的就是内存泄漏了,今天来介绍一个查看内存是否泄漏的工具LeakCanary,并通过研究源码明白它是如何分析和查找存在泄漏信息的...

3475
来自专栏博客园

路由

    路由提供了Route类作为IRouter的标准实现。当调用RouteAsync方法时,Route使用路由模板语法定义匹配URL路径的模式,当调用GetV...

1565
来自专栏程序员互动联盟

Android编程规范

命名规则: 1). 类名,接口名: 以大写开头,如果一个类的类名由多个单词组成,所有单词的首字母必须大写,单词尽量写全称,不要简写,除非约定俗成的名字,例如:...

4157
来自专栏自动化测试实战

flask第二十三篇——模板【5】过滤器

2389
来自专栏Android知识点总结

2-SII--应用本包下文件写入和读取

904

扫码关注云+社区