为什么.Net字典中的条目还有其他顺序？
https://stackoverflow.com/questions/154307
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我刚看到这种行为，我对此感到有些惊讶......
如果我向Dictionary添加3或4个元素，然后执行<！> quot; For Each <！> quot;为了得到所有的密钥，它们按我添加的顺序显示。
这让我感到惊讶的原因是一个字典在内部应该是一个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中的关联值的顺序相同。
你不能指望这种行为，但这并不奇怪。
考虑如何为简单的哈希表实现密钥迭代。您需要遍历所有散列桶，无论它们是否包含任何内容。从大哈希表中获取一个小数据集可能效率低下。
因此，保留单独的重复键列表可能是一个很好的优化。使用双链表您仍然可以获得恒定时间插入/删除。 （您可以将指向散列表桶的指针保留回此列表。）这样，遍历键列表的方式只取决于条目数，而不取决于桶数。
我认为这来自旧的.NET 1.1，你有两种词典<！> quot; ListDictionary <！> quot;和<！> quot; HybridDictionary <！> quot;。 ListDictionary 是一个内部实现的词典有序列表，建议用于<！>“小条目<！>”;然后你有 HybridDictionary ，这是最初的在内部组织为一个列表，但如果它增长大于可配置的阈值将成为哈希表。这样做是因为历史上适当的基于散列的词典被认为是昂贵的。现在是一个没有多大意义的日子，但我认为.NET只是基于旧HybridDictionary的新词典泛型类。
注意：无论如何，正如其他人已经指出的那样，你永远不会指望任何字典顺序
来自 MSDN 的引用：
中的键的顺序 字典<！> lt;（Of <！> lt;（TKey， TValue <！> gt;）<！> gt;）。KeyCollection是 未指定，但它是相同的顺序 作为关联的值 字典<！> lt;（Of <！> lt;（TKey， TValue GT <！>）GT <！>;）ValueCollection 字典返回<！> lt;（Of <！> lt;（TKey， TValue <！> gt;）<！> gt;）。值属性。
您在测试中添加了哪些键，以及按什么顺序添加？
您的条目可能都在字典中的相同哈希桶中。每个存储桶可能都是存储桶中的条目列表。这将解释按顺序返回的条目。
据我所知，这不应该是一种依赖的行为。要快速检查它，请使用相同的元素并更改将它们添加到字典中的顺序。你会看到你是否按照添加的顺序取回它们，或者只是巧合。
直到某个列表大小，只检查每个条目而不是散列是更便宜的。这可能就是发生的事情。
添加100或1000个项目，看看它们是否仍然处于相同的顺序。
我讨厌这种<！>“;设计<！>”;功能。我认为在给你的班级这样一个通用名称<！> quot; Dictionary <！> quot;时，它也应该表现为<！> quot;正如通常预期的那样<！>“。例如，std :: map始终保持其键值排序。
编辑：显然解决方案是使用SortedDictionary，其行为与std :: map类似。
问题和许多答案似乎误解了哈希表或字典的目的。这些数据结构对于数据结构中包含的项的值（或实际上是键）的枚举没有指定的行为。
字典或散列表的目的是能够在给定已知密钥的情况下有效地查找特定值。任何字典或散列表的内部实现应该在查找中提供这种效率，但不需要提供关于枚举的任何特定行为或<！>“;对于每个<！>”;键入值或键的迭代。
简而言之，内部数据结构可以以任何方式存储和枚举这些值，包括它们的插入顺序。
