原 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中的顺序是不可信任的，如果一定要使用，需要考虑全面些。