为什么字典“没有sorting”?

我在这里阅读了许多问题。 但究竟是什么意思?

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

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

那么,一方面,你是否期望这是插入订单还是按键顺序呢 ? 例如,如果你写了下面的话,你会期望结果如何?

 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的新条目已经使用了以前由2使用的腾出的条目。但是这并不能保证。

重新散列(当字典的底层存储需要扩展时)可能会影响事物……各种各样的事情。

只是不要把它当作一个有序的集合。 这不是为此而devise的。 即使碰巧现在工作,你依靠的是无证的行为,违背了课堂的目的。

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

文档解释得非常好:

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

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

首先,字典没有保证的顺序,所以你只用它来快速查找一个键并find一个相应的值,或者你通过所有的键值对枚举,而不关心顺序是什么。

如果你想要订单,你可以使用OrderedDictionary,但是折中的办法是查找速度较慢,所以如果你不需要订单,就不要求了。

字典(和Java中的HashMap)使用散列。 这是O(1)时间,不pipe你的表的大小。 有序字典通常使用某种平衡树,即O(log2(n)),以便数据增长,访问速度变慢。 为了比较一百万个元素,大概是2 ^ 20的数量级,所以你必须按照树的20次查找的顺序进行比较,而对于一个哈希映射,则需要1次。 这是一个很快很多。

散列是确定性的。 非确定性意味着当你第一次散列(5),而下一次散列(5)时,你得到了一个不同的地方。 那完全没用。

人们想要说的是,如果你把东西添加到字典中,顺序是复杂的,并且随着你添加(或者可能移除)一个元​​素而改变。 例如,假设哈希表中有500k个元素,并且有400k个值。 当你再添加一个时,你会达到关键的阈值,因为它需要大约20%的空间来提高效率,所以它会分配一个更大的表(比如说,100万个条目)并重新整理所有的值。 现在他们都在不同的位置比以前。

如果你两次build立同一个词典(仔细阅读我的陈述,相同),你会得到相同的顺序。 但正如Jon所说,不要指望它。 太多的东西可以使它不一样,即使是最初分配的大小。

这提出了一个很好的观点。 调整散列图的大小确实非常昂贵。 这意味着你必须分配一个更大的表,并重新插入每个键值对。 因此,分配10倍的内存是非常值得的,而不是一个单一的增长。 知道你的hashmap的大小,并尽可能预分配足够的,这是一个巨大的performance胜利。 如果你的实现不好,不能resize,如果你select的大小太小,这可能是一个灾难。

现在,Jon在我的评论中与我讨论的是,如果在两个不同的运行中将对象添加到字典中,您将得到两种不同的sorting。 诚然,但这不是字典的错。

当你说:

 new Foo(); 

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

如果在字典中使用值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

顺序是非确定性的。

从这里

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

也许你需要OrderedDictionary是必需的。

我不知道C#或.NET中的任何一个,但Dictionary的一般概念是它是键值对的集合。
例如,迭代列表或数组时,您不会按顺序访问字典。
你有一个密钥访问,然后发现是否有价值的字典上的密钥,它是什么。
在你的例子中,你发布了一个数字键盘的字典,这个键盘恰好是连续的,没有间隙,并且按照插入的升序排列。
但是无论按照哪个顺序为键“2”插入一个值,在查询键“2”时总会得到相同的值。
我不知道,如果C#允许,我猜是的,除了数字以外,还有其他的键types,但是在这种情况下,它是一样的,没有明确的键顺序。
与现实生活字典的类比可能会令人困惑,因为这些单词的关键字是按字母顺序排列的,所以我们可以更快地find它们,但是如果它们不是这样的话,那么字典无论如何都会起作用,因为“Aardvark “即使是在”斑马“之后,也会有相同的含义。 另一方面,想一本小说,改变页面的顺序是没有意义的,因为它们本质上是一个有序的集合。

Dictionary<TKey,TValue>是使用数组支持的索引链表实现的。 如果没有物品被移除,则后备商店将按顺序保存物品。 然而,当一个项目被删除时,这个空间将在数组展开之前被标记为重用。 因此,如果例如将10个项目添加到新字典中,则删除第四项目,添加新项目并且列举字典,新项目将可能出现第四而不是第十,但是不能保证不同版本的Dictionary将以相同的方式处理事情。

恕我直言,这将有助于微软文件,没有任何项目被删除的字典将按原始顺序枚举项目,但是一旦任何项目被删除,任何将来对字典的更改可能任意排列其中的项目。 只要没有项目被删除,坚持这样的保证对于大多数合理的字典实现来说是相对便宜的。 在物品被删除后继续维持保证将会更加昂贵。

或者,可能有一个AddOnlyDictionary对于一个作者来说可能是线程安全的,并且可以与任意数量的读者同时使用,并且保证顺序地保留项目(注意,如果项目只是被添加的 – 从不删除或者修改 – 一个人可能只是通过注意它目前包含多less物品来获取“快照”)。 制作一个通用词典是线程安全的是昂贵的,但是增加上述的线程安全级别会很便宜。 请注意,高效的多笔记本多读卡器使用不需要使用读写器locking,但可以简单地通过让作者locking并让读卡器不打扰来处理。

当然,Microsoft并没有实现AddOnlyDictionary ,但是有趣的是,线程安全的ConditionalWeakTable具有只读语义,可能是因为 – 如前所述 – 将并发性添加到只能添加的集合而不是允许删除的collections。

Dictionary <string,Obj>,而不是SortedDictionary <string,Obj>,默认为按插入顺序sorting。 足够奇怪的是,你需要专门声明一个SortedDictionary来使用一个按键string顺序sorting的字典:

 public SortedDictionary<string, Row> forecastMTX = new SortedDictionary<string, Row>();