47

我已阅读此内容以回答这里的许多问题。但这究竟是什么意思？

var test = new Dictionary<int, string>();
test.Add(0, "zero");
test.Add(1, "one");
test.Add(2, "two");
test.Add(3, "three");

Assert(test.ElementAt(2).Value == "two");

上面的代码似乎按预期工作。那么字典以什么方式被认为是无序的呢？上面的代码在什么情况下会失败？

4

7 回答 7

77

好吧，一方面不清楚您是否希望这是insert-order或key-order。例如，如果您这样写，您期望结果是什么：

var test = new Dictionary<int, string>();
test.Add(3, "three");
test.Add(2, "two");
test.Add(1, "one");
test.Add(0, "zero");

Console.WriteLine(test.ElementAt(0).Value);

你会期待“三”还是“零”？

碰巧的是，我认为当前的实现会保留插入顺序，只要您从不删除任何内容 - 但您不能依赖 this。这是一个实现细节，将来可能会改变。

删除也会影响这一点。例如，您希望这个程序的结果是什么？

using System;
using System.Collections.Generic;

class Test
{ 
    static void Main() 
    {
        var test = new Dictionary<int, string>();
        test.Add(3, "three");
        test.Add(2, "two");
        test.Add(1, "one");
        test.Add(0, "zero");

        test.Remove(2);
        test.Add(5, "five");

        foreach (var pair in test)
        {
            Console.WriteLine(pair.Key);
        }
    }     
}

它实际上是（在我的盒子上）3、5、1、0。5 的新条目使用了 2 之前使用的空出条目。但这也不能保证。

重新散列（当字典的底层存储需要扩展时）可能会影响事情......各种各样的事情都会发生。

只是不要将其视为有序集合。它不是为此而设计的。即使它现在恰好起作用，您也依赖于违反课程目的的无证行为。

于 2011-06-17T10:58:56.970 回答
26

ADictionary<TKey, TValue>代表一个哈希表，在哈希表中没有顺序的概念。

该文档很好地解释了它：

出于枚举的目的，字典中的每个项目都被视为表示值及其键的 KeyValuePair 结构。返回项目的顺序未定义。

于 2011-06-17T10:58:03.227 回答
10

这里有很多好主意，但分散，所以我将尝试创建一个更好的答案，即使问题已经得到解答。

首先，Dictionary 没有保证顺序，因此您仅使用它来快速查找键并找到相应的值，或者您枚举所有键值对而不关心顺序是什么。

如果您想要订购，您可以使用 OrderedDictionary 但权衡是查找速度较慢，因此如果您不需要订购，请不要要求它。

字典（和 Java 中的 HashMap）使用散列。无论您的表格大小如何，这都是 O(1) 时间。有序字典通常使用某种平衡树，即 O(log2(n))，因此随着数据的增长，访问速度会变慢。比较一下，对于 100 万个元素，大约是 2^20，所以你必须对树进行大约 20 次查找，而对于哈希映射则需要 1 次。这要快很多。

散列是确定性的。非确定性意味着当你第一次散列（5），下一次散列（5）时，你会得到一个不同的地方。那将是完全没有用的。

人们的意思是，如果您将内容添加到字典中，则顺序很复杂，并且在您添加（或可能删除）元素时随时更改。例如，假设哈希表中有 50 万个元素，而您有 40 万个值。当您再添加一个时，您将达到临界阈值，因为它需要大约 20% 的空白空间才能有效，因此它分配了一个更大的表（例如，100 万个条目）并重新散列所有值。现在他们都在与以前不同的位置。

如果您两次构建相同的字典（仔细阅读我的声明，THE SAME），您将得到相同的顺序。但正如乔恩正确所说，不要指望它。太多的东西可以使它不一样，即使是最初分配的大小。

这提出了一个很好的观点。必须调整哈希图的大小真的非常昂贵。这意味着您必须分配一个更大的表，并重新插入每个键值对。因此，非常值得分配 10 倍所需的内存，而不是必须进行一次增长。了解您的 hashmap 大小，并尽可能预先分配足够的空间，这是一个巨大的性能优势。如果你有一个不调整大小的糟糕实现，如果你选择的尺寸太小，那可能是一场灾难。

现在 Jon 在我的回答中与我争论的是，如果您在两次不同的运行中将对象添加到 Dictionary 中，您将获得两种不同的排序。没错，但这不是字典的错。

当你说：

new Foo();

您正在内存中的新位置创建一个新对象。

如果您使用值 Foo 作为字典中的键，没有其他信息，他们唯一能做的就是使用对象的地址作为键。

这意味着

var f1 = new Foo(1);
var f2 = new Foo(1);

f1 和 f2 不是同一个对象，即使它们具有相同的值。

因此，如果您要将它们放入字典中：

var test = new Dictionary<Foo, string>();
test.Add(f1, "zero");

不要指望它与以下内容相同：

var test = new Dictionary<Foo, string>();
test.Add(f2, "zero");

即使 f1 和 f2 具有相同的值。这与 Dictionary 的确定性行为无关。

散列是计算机科学中一个很棒的话题，我最喜欢在数据结构方面教授。

查看 Cormen 和 Leiserson 了解关于红黑树与哈希的高端书籍 这个名叫 Bob 的人有一个很棒的关于哈希和最佳哈希的网站：http: //burtleburtle.net/bob

于 2011-06-17T18:21:38.390 回答
4

顺序是不确定的。

从这里

出于枚举的目的，字典中的每个项目都被视为表示值及其键的 KeyValuePair 结构。返回项目的顺序未定义。

也许为了您的需要OrderedDictionary是必需的。

于 2011-06-17T10:59:23.770 回答
0

我不知道 C# 或任何 .NET，但 Dictionary 的一般概念是它是键值对的集合。
您不会像在迭代列表或数组时那样按顺序访问字典。
您通过拥有一个键来访问，然后查找字典中该键是否存在值以及它是什么。
在您的示例中，您发布了一个带有数字键的字典，这些键恰好是连续的，没有间隙并且按插入的升序排列。
但无论您以何种顺序为键 '2' 插入值，在查询键 '2' 时总是会得到相同的值。
我不知道 C# 是否允许（我猜是的）具有数字以外的键类型，但在这种情况下，它是相同的，键上没有明确的顺序。
与现实生活中的字典的类比可能会令人困惑，因为作为单词的键是按字母顺序排列的，因此我们可以更快地找到它们，但如果不是这样，字典无论如何都会起作用，因为“Aardvark”这个词的定义" 将具有相同的含义，即使它出现在 "Zebra" 之后。另一方面，想想一本小说，改变页面的顺序没有任何意义，因为它们本质上是一个有序的集合。

于 2011-06-17T12:19:44.710 回答
0

该类Dictionary<TKey,TValue>是使用数组支持的索引链表实现的。如果没有项目被删除，后备存储将按顺序保存项目。然而，当一个项目被删除时，该空间将在数组展开之前被标记为重复使用。因此，如果将十个项目添加到一个新字典中，则删除第四个项目，添加一个新项目，然后枚举字典，新项目可能会出现在第四而不是第十，但不能保证不同版本的Dictionary处理方式相同。

恕我直言，Microsoft 记录一个从未删除任何项目的字典将按原始顺序枚举项目，但一旦删除任何项目，未来对字典的任何更改都可能会任意置换其中的项目，这对 Microsoft 会很有帮助。对于大多数合理的字典实现而言，只要不删除任何项目就坚持这样的保证相对便宜；在删除项目后继续维护保证会更加昂贵。

AddOnlyDictionary或者，对于单个写入器与任意数量的读取器同时具有线程安全的线程可能会有所帮助，并保证按顺序保留项目（请注意，如果仅添加项目 - 从不删除或以其他方式修改 - - 只需注意它当前包含多少项目，就可以拍摄“快照”）。使通用字典线程安全是昂贵的，但添加上述线程安全级别会很便宜。请注意，高效的多写入器多读取器使用不需要使用读取器-写入器锁，而可以简单地通过让写入器锁定而让读取器不费心来处理。

当然， Microsoft 并没有实现AddOnlyDictionary如上所述的 an，但有趣的是，线程安全ConditionalWeakTable具有仅添加语义，可能是因为 - 如前所述 - 将并发添加到仅添加集合比添加允许删除的集合。

于 2014-07-12T17:51:45.690 回答
0

Dictionary< string, Obj>，而不是 SortedDictionary< string, Obj >，默认按插入顺序排序。奇怪的是，您需要专门声明一个 SortedDictionary 以拥有一个按键字符串顺序排序的字典：

public SortedDictionary<string, Row> forecastMTX = new SortedDictionary<string, Row>();
于 2016-08-30T19:53:53.033 回答