为什么词典"没有订购"？

Question

我已经在这里回答了许多问题.但究竟是什么意思呢？

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

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

Answer 1

嗯,首先不清楚你是否期望这是插入顺序或键顺序.例如,如果你写了,你会期望结果是什么:

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

你会期待"三"还是"零"？

碰巧,我认为当前的实现保留了插入顺序,只要你永远不会删除任何东西 - 但你不能依赖于此.这是一个实现细节,将来可能会发生变化.

删除也会影响这一点.例如,您期望这个程序的结果是什么？

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的新条目使用了之前使用的空出条目.但是这不会得到保证.

Rehashing(当字典的底层存储需要扩展时)会影响事物...各种事情都会发生.

只是不要将它视为有序集合.它不是为此而设计的.即使它现在正好工作,你仍然依赖于无证的行为,这违背了班级的目的.

Answer 2

A Dictionary<TKey, TValue>表示哈希表,在哈希表中没有顺序概念.

该文档解释了它相当不错:

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

Answer 3

这里有很多好的想法,但是分散,所以我会尝试创建一个更好地解决问题的答案,即使问题已得到解答.

首先,词典没有保证顺序,因此您只能使用它来快速查找键并找到相应的值,或者您可以枚举所有键值对而无需关心订单是什么.

如果你想要订单,你使用OrderedDictionary,但权衡是查找速度较慢,所以如果你不需要订单,不要求它.

字典(以及Java中的HashMap)使用散列.无论你的桌子大小如何,这都是O(1)时间.有序字典通常使用某种平衡树,即O(log2(n)),因此随着数据的增长,访问速度变慢.为了比较,对于100万个元素,大约为2 ^ 20,所以你必须做20个查找树的顺序,但是1个用于哈希映射.那更快了.

哈希是确定性的.非确定性意味着当您第一次散列(5)并且下次散列(5)时,您会得到一个不同的位置.那将是完全无用的.

人们想要说的是,如果您将字符添加到字典中,则订单很复杂,并且在您添加(或可能删除)元素时可能会发生变化.例如,假设哈希表中有500k个元素,并且您有400k值.当你再添加一个时,你就达到了临界阈值,因为它需要大约20%的空闲空间才能有效,所以它分配了一个更大的表(比如100万个条目)并重新散列所有的值.现在他们都在不同的位置.

如果你两次构建相同的词典(仔细阅读我的陈述,相同),你将获得相同的顺序.但正如乔恩所说,不要指望它.太多的东西可以使它不一样,即使是最初分配的大小.

这提出了一个很好的观点.必须调整散列映射的确非常非常昂贵.这意味着你必须分配一个更大的表,并重新插入每个键值对.所以非常值得分配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都具有相同的值.这与词典的确定性行为无关.

哈希是计算机科学中一个很棒的主题,我最喜欢在数据结构中教学.

查看Cormen和Leiserson获取关于红黑树和散列的高端书籍这个名叫Bob的人有一个关于哈希和最佳哈希的好网站:http://burtleburtle.net/bob

Answer 4

订单是不确定的.

从这里开始

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

也许满足您的需求OrderedDictionary是必需的.