应该是:如果字典只是添加值,那么是顺序的,如果有移除操作,那么就不能保证是顺序的
我们查看Dictionary的源代码会发现下面核心代码:
private void Insert(TKey key, TValue value, bool add)
{
int freeList;
if (key == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
if (this.buckets == null)
{
this.Initialize(0);
}
int num = this.comparer.GetHashCode(key) & 0x7fffffff;
int index = num % this.buckets.Length;
for (int i = this.buckets[index]; i >= 0; i = this.entries[i].next)
{
if ((this.entries[i].hashCode == num) && this.comparer.Equals(this.entries[i].key, key))
{
if (add)
{
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
}
this.entries[i].value = value;
this.version++;
return;
}
}
if (this.freeCount > 0)
{
freeList = this.freeList;
this.freeList = this.entries[freeList].next;
this.freeCount--;
}
else
{
if (this.count == this.entries.Length)
{
this.Resize();
index = num % this.buckets.Length;
}
freeList = this.count;
this.count++;
}
this.entries[freeList].hashCode = num;
this.entries[freeList].next = this.buckets[index];
this.entries[freeList].key = key;
this.entries[freeList].value = value;
this.buckets[index] = freeList;
this.version++;
}
由上面可以看出,freeList决定了该插入数组的位置,如果没有经过Remove的时候,freeCount值一直为0,所以是顺序添加的。
下面是两个测试:
public class Node
{
public int ID
{
get;
set;
}
public override int GetHashCode() //如果让所有的Hashcode相等
{
return 0;
}
}
private static void DictionaryForeachTest()
{
int count = 100;
Dictionary<int, int> dic = new Dictionary<int, int>(count);
for (int i = 0; i < count; i++)
{
if (i % 2 == 0)
{
dic.Add(i, i);
}
}
for (int i = 0; i < count; i++)
{
if (i % 4 == 0)
{
dic.Remove(i);
}
}
for (int i = 0; i < count; i++)
{
if (i % 2 == 1)
{
dic.Add(i, i);
}
}
foreach (int i in dic.Keys)
{
Console.WriteLine(string.Format("i={0},hashcode={1}",i,i.GetHashCode()));
}
}
private static void DictionaryForeachTest1()
{
int count = 100;
Dictionary<Node, int> dic = new Dictionary<Node, int>(count);
List<Node> removedNodes = new List<Node>();
for (int i = 0; i < count; i++)
{
Node node = new Node { ID = i };
if (i % 2 == 0)
{
dic.Add(node, i);
}
if (i % 4 == 0)
{
removedNodes.Add(node);
}
}
for (int i = 0; i < removedNodes.Count; i++)
{
dic.Remove(removedNodes[i]);
}
for (int i = 0; i < count; i++)
{
if (i % 2 == 1)
{
dic.Add(new Node { ID = i }, i);
}
}
foreach (Node node in dic.Keys)
{
Console.WriteLine(string.Format("node={0},hashcode={1}", node.ID, node.GetHashCode()));
}
}
public class MyDictionary<TKey,TValue>
{
private object _syncRoot;
private int[] buckets;
private IEqualityComparer<TKey> comparer;
private const string ComparerName = "Comparer";
private int count;
private Entry[] entries;
private int freeCount;
private int freeList;
private const string HashSizeName = "HashSize";
//private KeyCollection<TKey, TValue> keys;
private const string KeyValuePairsName = "KeyValuePairs";
//private SerializationInfo m_siInfo;
//private ValueCollection<TKey, TValue> values;
private int version;
private const string VersionName = "Version";
public MyDictionary()
{
int prime = 100;
this.buckets = new int[prime];
for (int i = 0; i < this.buckets.Length; i++)
{
this.buckets[i] = -1;
}
this.entries = new Entry[prime];
this.freeList = -1;
}
public void Insert(TKey key, TValue value, bool add)
{
int freeList;
int num = key.GetHashCode() & 0x7fffffff;
int index = num % this.buckets.Length;
for (int i = this.buckets[index]; i >= 0; i = this.entries[i].next)
{
if ((this.entries[i].hashCode == num) && this.comparer.Equals(this.entries[i].key, key))
{
if (add)
{
throw new Exception();
}
this.entries[i].value = value;
this.version++;
return;
}
}
if (this.freeCount > 0)
{
freeList = this.freeList;
this.freeList = this.entries[freeList].next;
this.freeCount--;
}
else
{
//if (this.count == this.entries.Length)
//{
// this.Resize();
// index = num % this.buckets.Length;
//}
freeList = this.count;
this.count++;
}
if (this.buckets[index]!=-1)
{
}
this.entries[freeList].hashCode = num;
this.entries[freeList].next = this.buckets[index];
this.entries[freeList].key = key;
this.entries[freeList].value = value;
this.buckets[index] = freeList;
}
private int FindEntry(TKey key)
{
if (this.buckets != null)
{
int num = this.comparer.GetHashCode(key) & 0x7fffffff;
for (int i = this.buckets[num % this.buckets.Length]; i >= 0; i = this.entries[i].next)
{
if ((this.entries[i].hashCode == num) && this.comparer.Equals(this.entries[i].key, key))
{
return i;
}
}
}
return -1;
}
private struct Entry
{
public int hashCode;
public int next;
public TKey key;
public TValue value;
}
}
//简单记录:
this.entries是按照添加的顺序,添加到数据中,但是数据本身又以链表的方式保存,记录着下一个和自己Hashcode相等的对象的Index(Entry.next)
this.buckets 记录对象Hashcode在this.entries的Index(只记录最新一次,因为按照最新一次的对象,就可以以链表的方式找到所有相同Hashcode的对象)
测试的程序:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication4
{
class Program
{
static void Main(string[] args)
{
Dictionary<Node, int> data = new Dictionary<Node, int>(1024);
DictionaryForeachTest();
DictionaryForeachTest1();
}
private static void DictionaryForeachTest()
{
int count = 100;
Dictionary<int, int> dic = new Dictionary<int, int>(count);
//Dictionary a = new Dictionary();
for (int i = 0; i < count; i++)
{
if (i % 2 == 0)
{
dic.Add(i, i);
//a.Insert(i, i, true);
}
}
for (int i = 0; i < count; i++)
{
if (i % 4 == 0)
{
dic.Remove(i);
}
}
for (int i = 0; i < count; i++)
{
if (i % 2 == 1)
{
dic.Add(i, i);
}
}
foreach (int i in dic.Keys)
{
Console.WriteLine(string.Format("i={0},hashcode={1}",i,i.GetHashCode()));
}
}
private static void DictionaryForeachTest1()
{
int count = 100;
Dictionary<Node, int> dic = new Dictionary<Node, int>(count);
MyDictionary<Node, int> mydic = new MyDictionary<Node, int>();
List<Node> removedNodes = new List<Node>();
for (int i = 0; i < count; i++)
{
Node node = new Node { ID = i };
if (i % 2 == 0)
{
dic.Add(node, i);
mydic.Insert(node,i,true);
}
if (i % 4 == 0)
{
removedNodes.Add(node);
}
}
mydic.FindEntry(removedNodes[0]);
for (int i = 0; i < removedNodes.Count; i++)
{
dic.Remove(removedNodes[i]);
}
for (int i = 0; i < count; i++)
{
if (i % 2 == 1)
{
dic.Add(new Node { ID = i }, i);
}
}
foreach (Node node in dic.Keys)
{
Console.WriteLine(string.Format("node={0},hashcode={1}", node.ID, node.GetHashCode()));
}
}
}
public class MyDictionary<TKey,TValue>
{
private object _syncRoot;
private int[] buckets;
private IEqualityComparer<TKey> comparer;
private const string ComparerName = "Comparer";
private int count;
private Entry[] entries;
private int freeCount;
private int freeList;
private const string HashSizeName = "HashSize";
//private KeyCollection<TKey, TValue> keys;
private const string KeyValuePairsName = "KeyValuePairs";
//private SerializationInfo m_siInfo;
//private ValueCollection<TKey, TValue> values;
private int version;
private const string VersionName = "Version";
public MyDictionary()
{
int prime = 100;
this.buckets = new int[prime];
for (int i = 0; i < this.buckets.Length; i++)
{
this.buckets[i] = -1;
}
this.entries = new Entry[prime];
this.freeList = -1;
}
public void Insert(TKey key, TValue value, bool add)
{
int freeList;
int num = key.GetHashCode() & 0x7fffffff;
int index = num % this.buckets.Length;
for (int i = this.buckets[index]; i >= 0; i = this.entries[i].next)
{
if ((this.entries[i].hashCode == num) &&Object.Equals(this.entries[i].key, key))
{
if (add)
{
throw new Exception();
}
this.entries[i].value = value;
this.version++;
return;
}
}
if (this.freeCount > 0)
{
freeList = this.freeList;
this.freeList = this.entries[freeList].next;
this.freeCount--;
}
else
{
//if (this.count == this.entries.Length)
//{
// this.Resize();
// index = num % this.buckets.Length;
//}
freeList = this.count;
this.count++;
}
if (this.buckets[index]!=-1)
{
}
this.entries[freeList].hashCode = num;
this.entries[freeList].next = this.buckets[index];
this.entries[freeList].key = key;
this.entries[freeList].value = value;
this.buckets[index] = freeList;
}
public int FindEntry(TKey key)
{
if (this.buckets != null)
{
int num = key.GetHashCode() & 0x7fffffff;
for (int i = this.buckets[num % this.buckets.Length]; i >= 0; i = this.entries[i].next)
{
if ((this.entries[i].hashCode == num) && Object.Equals(this.entries[i].key, key))
{
return i;
}
}
}
return -1;
}
private struct Entry
{
public int hashCode;
public int next;
public TKey key;
public TValue value;
}
}
public class Node
{
public int ID
{
get;
set;
}
public override int GetHashCode()
{
return 0;
}
}
}