我刚看到这个行为，感到有些惊讶...
如果我向字典中添加3或4个元素，然后使用“For Each”获取所有键，它们出现的顺序与我添加它们的顺序相同。
这让我感到惊讶的原因是，字典内部应该是一个哈希表，所以我期望事情按任何顺序出现（按键的哈希排序，对吗？）
我错过了什么吗？ 我可以依赖这种行为吗？
编辑：好的，我已经想到很多可能导致这种情况发生的原因了（例如条目的单独列表，这是否是巧合等）。 我的问题是，有人知道这是如何实现的吗？
11个回答
41
如果你在 .NET Reflector 上查看 3.5 类库，你会发现 Dictionary 的实现实际上是将项目存储在数组中（根据需要调整大小），并对该数组进行哈希索引。当获取键时，它完全忽略哈希表并迭代项目数组。因此，由于新项目添加到数组末尾，你会看到你所描述的行为。似乎如果你执行以下操作：
add 1
add 2
add 3
add 4
remove 2
add 5
因为它重复使用了空槽，所以你将得到1 5 3 4。
需要注意的是，就像许多其他人所说的那样，您不能依赖于未来（或过去）的版本中的这种行为。如果您希望字典被排序，则有一个SortedDictionary类可用于此目的。
- Dolphin
3
7
一个字典以哈希顺序检索项目。它们以插入顺序出现纯属巧合。
MSDN文档如下所述：
键集合中的键顺序未指定，但与由Values属性返回的关联值的顺序相同。
MSDN文档如下所述：
键集合中的键顺序未指定，但与由Values属性返回的关联值的顺序相同。
- Brad Wilson
4
嗯，这不是完全巧合。通过一个小样本，我发现它们通常按照你添加它们的顺序出现。还是很好的答案！ - Danimal
我不认为这是巧合。我改变了相同元素的加法顺序，以查看是否会更改结果。所以这不是发生的事情。如果我有足够大量的数据，.Net 可能会以不同的方式处理它。 - Daniel Magliola
如果你阅读了文档，那么这仍然是一个不应该依赖的巧合。即使你深入代码理解为什么它对于少量键值会这样做，#可能会改变，或者在旧/新框架版本中根本不成立。 - Brad Wilson
1这并不是巧合，而是一种特别不暴露的实现细节。 - Dolphin
5
不能指望这种行为，但也不足为奇。
考虑如何为简单哈希表实现键的迭代。您需要遍历所有哈希桶，无论它们是否为空。从大哈希表中获取小数据集可能效率低下。
因此，保留一个单独的、重复的键列表可能是一个好的优化方法。使用双向链表仍然可以获得常数时间插入/删除。(您将从哈希表桶中保留一个指针指向此列表。) 这样，通过键列表进行迭代仅取决于条目数量，而不是桶数量。
- Eric
2
我认为这源于旧的.NET 1.1时代，那时候有两种字典类型：“ListDictionary”和“HybridDictionary”。ListDictionary是一种作为有序列表实现的字典，并且推荐用于“小型条目集合”。接着你就有了HybridDictionary，最初它是作为列表内部组织的，但是如果超过一个可配置阈值，它将变成哈希表。这是因为历史上认为适当的基于哈希的字典很昂贵。现在来看这没有什么意义，不过我想.NET只是基于旧的HybridDictionary创建了新的Dictionary泛型类。
注意: 无论如何，正如其他人已经指出的，您 永远不应该依赖于字典顺序做任何事情。
- davidg
1
MSDN 中的一句话：
Dictionary<(Of <(TKey, TValue>)>).KeyCollection中键的顺序是未指定的，但与由Dictionary<(Of <(TKey, TValue>)>).Values属性返回的关联值相同。
- korchev
1
你在测试中添加了哪些键，以及按什么顺序添加的？
- lassevk
1
你的条目可能都在字典中的同一个哈希桶中。每个桶可能是桶中条目的列表。这可以解释为什么条目按顺序返回。
- Laplie
0
在某个列表大小范围内，仅检查每个条目而不进行哈希处理更便宜。这可能就是正在发生的事情。
添加100或1000个项目，并查看它们是否仍然按照相同的顺序排列。
- Zan Lynx
1
3.5 版本的实现将按顺序枚举任意数量的元素（有关详细信息，请查看我的答案）。 - Dolphin
0
我讨厌这种“按设计”功能。我认为，当你给你的类起一个如此通用的名称“Dictionary”时，它也应该表现出“通常的预期”。例如，std::map始终保持其键值排序。
编辑：显然解决方案是使用SortedDictionary，它的行为类似于std::map。
- AareP
1
正如被接受的答案所指出的那样，这是由Microsoft实现方式引起的副作用，并不保证“通常情况下”的行为。 “通常情况下”取决于你和谁交流... 类的客户端不应该假设它的实现方式，如果需要特定的行为，则客户端代码应明确地实例化适当的类。 - Andrew Theken
0
据我所知，这不应该是一个可靠的行为。要快速检查它，请使用相同的元素并更改将它们添加到字典中的顺序。您将看到是否按照它们被添加的顺序返回它们，或者这只是巧合。
- rslite
1
我显然做到了 :-)
我按照添加的顺序依次获取它们，这并不是巧合。 - Daniel Magliola
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
SortedDictionary的建议假定用户有明确的排序意图。如果您想保证插入顺序被保留，您应该实现自己的IDictionary<TKey, TValue>实现类。 - James Dunne