我刚刚看到这种行为，我对此感到有点惊讶......
如果我将 3 或 4 个元素添加到字典，然后执行“For Each”以获取所有键，它们会按照我添加它们的顺序出现。
这让我感到惊讶的原因是 Dictionary 应该是内部的 HashTable，所以我希望事情以任何顺序出现（按键的哈希排序，对吗？）
我在这里想念什么？这是我可以指望的行为吗？
编辑：好的，我已经想到了可能发生这种情况的许多原因（例如条目的单独列表，这是否是巧合等）。我的问题是，有人知道这到底是如何工作的吗？
Daniel Magliola
问问题
4052 次
11 回答
41
如果您在 3.5 类库上使用 .NET Reflector，您可以看到 Dictionary 的实现实际上将项目存储在一个数组中（根据需要调整大小），并将索引散列到该数组中。获取密钥时，它完全忽略哈希表并遍历项目数组。出于这个原因，您将看到您所描述的行为，因为新项目被添加到数组的末尾。如果您执行以下操作，则看起来像：
add 1
add 2
add 3
add 4
remove 2
add 5
你会得到 1 5 3 4 因为它重用了空槽。
重要的是要注意，就像许多其他人一样，您不能指望在未来（或过去）版本中出现这种行为。如果您希望对字典进行排序，那么为此目的有一个SortedDictionary类。
于 2009-06-10T16:54:38.010 回答
7
字典以散列顺序检索项目。他们按插入顺序出现的事实完全是巧合。
MSDN 文档说：
KeyCollection 中键的顺序未指定，但它与 Values 属性返回的 ValueCollection 中的关联值的顺序相同。
于 2008-09-30T18:25:02.130 回答
5
你不能指望这种行为，但这并不奇怪。
考虑如何为一个简单的哈希表实现键迭代。您需要遍历所有哈希桶，无论它们是否有任何内容。从大哈希表中获取小数据集可能效率低下。
因此，保留一个单独的重复键列表可能是一个很好的优化。使用双链表，您仍然可以获得恒定时间的插入/删除。（您可以将哈希表存储桶中的指针保留回该列表。）这样遍历键列表仅取决于条目数，而不取决于存储桶数。
于 2008-09-30T18:31:51.023 回答
2
我认为这来自旧的 .NET 1.1 时代，您有两种字典“ListDictionary”和“HybridDictionary”。ListDictionary是内部实现为有序列表的字典，推荐用于“小型条目集”。然后你有HybridDictionary，它最初在内部组织为一个列表，但如果它变得大于可配置的阈值，它将成为一个哈希表。这样做是因为历史上正确的基于散列的字典被认为是昂贵的。现在日子没有多大意义，但我认为.NET 只是基于旧的 HybridDictionary 的新 Dictionary 泛型类。
注意：无论如何，正如其他人已经指出的那样，你永远不应该指望字典顺序来做任何事情
于 2008-09-30T18:34:20.673 回答
1
来自MSDN的引用：
Dictionary<(Of <(TKey, TValue>)>).KeyCollection 中键的顺序未指定，但与 Dictionary<(Of <(TKey, TValue>)>) 中关联值的顺序相同Dictionary<(Of <(TKey, TValue>)>).Values 属性返回的 .ValueCollection。
于 2008-09-30T18:27:46.867 回答
1
您在测试中添加了哪些键，按什么顺序添加？
于 2008-09-30T18:29:27.753 回答
1
您的条目可能都在字典中的同一个哈希桶中。每个桶可能是桶中条目的列表。这将解释按顺序返回的条目。
于 2008-09-30T19:02:58.950 回答
0
据我所知，这不应该是一种可以依赖的行为。要快速检查它，请使用相同的元素并更改将它们添加到字典的顺序。您会看到是否按照添加顺序将它们取回，或者这只是巧合。
于 2008-09-30T18:26:01.583 回答
0
在达到一定的列表大小之前，只检查每个条目而不是散列会更便宜。这可能就是正在发生的事情。
添加 100 或 1000 个项目，看看它们是否仍处于相同的顺序。
于 2008-12-09T22:31:40.553 回答
0
我讨厌这种“设计”的功能。我认为，当给你的班级起一个像“字典”这样的通用名称时，它的行为也应该“像一般预期的那样”。例如 std::map 总是保持它的键值排序。
编辑：显然解决方案是使用 SortedDictionary，其行为类似于 std::map。
于 2010-08-11T07:38:10.657 回答
-1
这个问题和许多答案似乎误解了哈希表或字典的目的。这些数据结构对于数据结构中包含的项目的值（或实际上是键）的枚举没有指定的行为。
字典或哈希表的目的是能够有效地查找给定已知键的特定值。任何字典或哈希表的内部实现都应该在查找中提供这种效率，但不需要提供关于枚举或值或键上的“每个”类型迭代的任何特定行为。
简而言之，内部数据结构可以按照它希望的任何方式存储和枚举这些值，包括它们被插入的顺序。
于 2009-05-05T14:52:19.123 回答