为什么.Net字典中的条目还有其他顺序？

我刚刚看到这种行为,我对此感到有些惊讶......

如果我向Dictionary添加3或4个元素,然后执行"For Each"以获取所有键,它们将按照我添加它们的相同顺序显示.

这让我感到惊讶的原因是一个字典在内部应该是一个HashTable,所以我期望事情以任何顺序出现(按键的哈希排序,对吧？)

我在这里错过了什么？这是我可以依靠的行为吗？

编辑:好的,我已经想到了为什么会发生这种情况的许多原因(比如条目的单独列表,这是巧合等).我的问题是,有谁知道这是如何工作的？

如果在3.5类库上使用.NET Reflector,您可以看到Dictionary的实现实际上将项存储在一个数组中(根据需要调整大小),并将索引哈希到该数组中.获取密钥时,它会完全忽略哈希表并迭代项目数组.因此,您将看到自从在数组末尾添加新项目以来所描述的行为.看起来如果您执行以下操作:

add 1
add 2
add 3
add 4
remove 2
add 5

你会得到1 5 3 4因为它重复使用空槽.

值得注意的是,与许多其他人一样,您不能指望在将来(或过去)版本中出现这种行为.如果您希望对字典进行排序,那么为此目的有一个SortedDictionary类.

字典以散列顺序检索项目.它们以插入顺序出现的事实完全是巧合.

MSDN文档说:

KeyCollection中的键的顺序是未指定的,但它与Values属性返回的ValueCollection中的关联值的顺序相同.

你不能指望这种行为,但这并不奇怪.

考虑如何为简单的哈希表实现密钥迭代.您需要遍历所有散列桶,无论它们是否包含任何内容.从大哈希表中获取小数据集可能效率低下.

因此,保留单独的重复键列表可能是一个很好的优化.使用双链表您仍然可以获得恒定时间插入/删除.(您可以将指向散列表桶的指针保留回此列表.)这样,遍历密钥列表的方式仅取决于条目数,而不取决于存储桶数量.