logo标签列表

为什么字典是“无序”的？

c#.netdictionarybase-class-libraryoperator-precedence
49

我在这里看到过很多问题的答案中都有这样的说法，但它具体是什么意思呢？

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");

上述代码似乎按预期工作。那么字典被认为是无序的是什么意思？在什么情况下，上述代码可能失败？

5
即使特定测试通过，字典的顺序也不能保证，在一般情况下不能依赖它。 - sorpigal
2
@Sorpigal：是的，但是为什么？怎么做？ - fearofawhackplanet
3
词典并非无序，只是不一定有序，这两者并不相同。 - Petruza
为什么和如何访问字典或哈希表中的第n个项目在https://dev59.com/VlPTa4cB1Zd3GeqPhTl3中有详细介绍。 - Simon Whitaker
可能是 为什么.Net字典中的条目按添加顺序排序？ 的重复问题。 - nawfal
显示剩余2条评论
7个回答
78

首先，有一件事情不清楚，那就是您希望这是按照插入顺序还是键顺序排序。例如，如果您编写以下代码：

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);

你会期待 "three" 还是 "zero"？

恰好，目前的实现（如果你从未删除任何东西）似乎保留插入顺序，但是你不应该依赖于此。这只是一个实现细节，而且将来可能会发生变化。

删除操作也会影响顺序。例如，对于以下程序，你会期望得到什么结果？

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号使用过的空置条目。但这也不能保证。

重新散列（当字典的底层存储需要扩展时）可能会影响到各种各样的东西......

只是不要把它作为有序集合来处理。它不是为此而设计的。即使现在它碰巧工作，你仍然依赖于未记录的行为，这违背了类的目的。

1
@fearofawhackplanet：好的，所以您期望插入顺序。那么您对我的第二个示例有什么期望？ - Jon Skeet
2
字典通常按照最有效的获取值的顺序进行排序。它们是查找表。在C#中，插入顺序似乎被保留，除非修改了字典，但例如在Python中，它是按键值的哈希值排序的，以便可以进行快速读取。无论如何，正如Jon所说：永远不要信任字典的顺序；它可能会在运行、实现和架构之间完全变化。 - Blixt
3
@Dov：我不同意。假设它是通过哈希码排序的，Foo中没有任何东西覆盖了GetHashCode……那么添加新的Foo实例的连续运行可能会显示不同的顺序。当然，这取决于你所说的“相同的插入顺序”的含义——但我看不到任何东西试图保证顺序“最好是相同的”，我也不想依赖它。 - Jon Skeet
3
这是一篇文章，描述了如何在不改变内容的情况下改变字典顺序。链接为：http://blogs.msdn.com/b/ericlippert/archive/2011/05/23/read-only-and-threadsafe-are-different.aspx - adrianm
1
我可以确认插入顺序是不可靠的。我刚刚花了几个小时追踪一个错误，因为我在将近5年前编写的某个库代码中依赖于插入顺序。在这个特定的情况下，它工作得很好。有两个字典添加了相同的项目，按照相同的顺序，但根据情况它们并不会以相同的方式返回。 - A.R.
显示剩余7条评论
27

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

文档已经很好地解释了：

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

4
哈希表针对随机访问进行了优化，而不是顺序访问。它们为了更快的访问速度而牺牲了排序功能。 - Noufal Ibrahim
2
在我看来，考虑到它具有“未定义的顺序”而不是“无序”的特点更有意义。在我看来，这些语言术语并不完全意味着相同的事情。 - fearofawhackplanet
10
这里有很多好的想法，但它们比较零散，所以我会尝试创建一个更好的答案来梳理它，尽管问题已经得到了解答。
首先，字典没有保证的顺序，所以你只能使用它快速查找键并找到对应的值，或者枚举所有键-值对而不关心顺序。
如果你需要顺序，可以使用OrderedDictionary，但是牺牲的是查找速度，所以如果你不需要顺序，请不要请求它。
字典（和Java中的HashMap）使用哈希。这是O(1)时间，无论表的大小如何。有序字典通常使用某种平衡树，其复杂度为O(log2(n))，因此随着数据增长，访问速度变慢。比较一下，对于100万个元素，那就是2^20的数量级，因此你需要在树中进行约20次查找，但在哈希映射中只需要1次。这非常快。
哈希是确定性的。非确定性意味着当你第一次散列(5)，然后你再次散列(5)，你会得到一个不同的位置。那将是完全没用的。
人们想要说的是，如果你向字典添加东西，顺序很复杂，并且在添加（或可能删除）元素时会发生变化。例如，假设哈希表中有500k个元素，并且有400k个值。当你添加一个值时，你就达到了关键的阈值，因为它需要大约20%的空间才能高效地进行处理，因此它会分配一个更大的表（比如1百万个条目）并重新散列所有值。现在它们都在不同的位置。
如果你两次构建相同的字典（仔细阅读我的陈述，是相同的），你会得到相同的顺序。但正如Jon所说的，不要指望它。太多的事情可以使它不同，甚至最初分配的大小也可能不同。
这提出了一个很好的观点。调整哈希映射大小非常昂贵。这意味着你必须分配一个更大的表，并重新插入每个键-值对。因此，与其让它增长一次，不如预先分配10倍的内存。知道哈希映射的大小，并尽可能地预先分配足够的内存，这是一个巨大的性能优势。如果你选择的大小太小，那么如果你有一个糟糕的实现不调整大小，它可能会导致灾难。
现在Jon在他的答案中与我争论的是，如果你在两个不同的运行中向字典添加对象，则会获得两个不同的顺序。这是真的，但这不是字典的错。
当你说：
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具有相同的值，这与字典的确定性行为无关。 哈希是计算机科学中一个很棒的主题，也是我最喜欢在数据结构课上讲解的主题。 查看Cormen和Leiserson的高端书籍，了解红黑树与哈希的比较。这个名叫Bob的人有一个关于哈希和最优哈希的好网站：http://burtleburtle.net/bob。
4

这个顺序是非确定性的。

从这里开始

为了枚举的目的，字典中的每个项都被视为一个KeyValuePair结构，表示一个值和它的键。返回这些项的顺序是未定义的。

也许对于您的需求，OrderedDictionary是所需的。

1
顺序肯定是未定义的，但在大多数实现中可能是确定性的。 - Brian
当然，顺序是确定的。你的意思是如果插入或删除一个值，顺序可以随时改变。那是完全不同的事情。 - Dov
如果您将相同的值添加到字典中，它们将以相同的顺序出现在字典中。这是确定性的。否则，您将拥有一个非常有缺陷的哈希表。 - Dov
0

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

0

Dictionary<TKey,TValue>类使用基于数组的索引链接列表实现。如果从未删除任何项，则后备存储将按顺序保存项目。但是，当删除项目时，在扩展数组之前将标记要重用的空间。因此，例如将十个项目添加到新字典中，删除第四个项目，添加新项目并枚举字典时，新项目可能会出现在第四个位置而不是第十个位置，但不能保证不同版本的Dictionary将以相同的方式处理事情。

我认为，微软应该记录下这样一个事实：从未删除任何项的字典将按原始顺序枚举项目，但一旦删除任何项，对字典的任何未来更改都可能会任意地改变其中的项目。对于大多数合理的字典实现，只要不删除任何项，维护这样的保证就相对便宜；在删除项目后继续维护保证将更加昂贵。

或者，拥有一个AddOnlyDictionary可能会有所帮助，它可以在单个写入者与任意数量的读取器并行时保证线程安全，并保证项目按顺序保留（请注意，如果仅添加项目 - 从未删除或以其他方式修改 - 可以仅通过注意它当前包含多少项来“拍摄”）。使通用字典线程安全是昂贵的，但添加上面的线程安全级别将很便宜。请注意，高效的多作者多读者使用不需要使用读写锁，只需让作者锁定并且读者不必打扰即可处理。

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

0

默认情况下，Dictionary<string, Obj> 按插入顺序排序，而不是 SortedDictionary<string, Obj>。有趣的是，你需要明确声明一个 SortedDictionary 才能拥有按键字符串顺序排序的字典：

public SortedDictionary<string, Row> forecastMTX = new SortedDictionary<string, Row>();
2
我认为当你对某人进行负评时，即使你不喜欢那个人，给出解释也是一种好的、专业的方式。请通过 StackOverflow 的消息工具让我知道你为什么给了我一个负评。不要只是负评我而不说任何话，让我一无所知，不知道我做错了什么，因为这是一个为每个人学习的论坛。 - Jenna Leaf
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接