原 NET中dictionary的一个小坑

魂祭心

发布于 2018-05-17 09:38:34

68100

代码可运行

文章被收录于专栏：魂祭心魂祭心

运行总次数：0

代码可运行

问题描述：前段时间做个东西，打算在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;
       }
   }