HashSet是否保留了插入顺序？

Question

HashSet.NET 3.5中引入的集合在使用迭代时是否保留了插入顺序foreach？

该文件指出,该集合没有排序,但它并没有说明插入顺序什么.预发布的BCL 博客条目表明它是无序的,但是本文声明它旨在保留插入顺序.我的有限测试表明,该顺序得以保留,但这可能是巧合.

Answer 1

这个HashSet MSDN页面专门说:

集合是一个不包含重复元素的集合,其元素没有特定的顺序.

Answer 2

我认为声称它保留排序的文章是完全错误的.对于简单的测试,由于内部结构,插入顺序可能会得到很好的保留,但是不能保证,并且不会总是以这种方式工作.我会试着想出一个反例.

编辑:这是反例:

using System;
using System.Collections.Generic;

class Test
{
    static void Main()
    {
        var set = new HashSet<int>();

        set.Add(1);
        set.Add(2);
        set.Add(3);
        set.Remove(2);
        set.Add(4);


        foreach (int x in set)
        {
            Console.WriteLine(x);
        }
    }
}

尽管在4之前插入了3个,但这打印了1,4,3.

这是可能的,如果你从来没有删除任何项目,它将保留插入顺序.我不确定,但我不会完全惊讶.但是,我认为依靠它是一个非常糟糕的主意:

• 它没有记录以这种方式工作,文档明确指出它没有排序.
• 我没有看过内部结构或源代码(显然我没有) - 在以坚定的方式提出任何此类声明之前,我必须仔细研究它们.
• 实现可以很容易地在框架的版本之间进行更改.依托这就像依靠string.GetHashCode不改变执行-这部分人确实早在NET 1.1天,然后在执行他们得到了烧没改变.NET 2.0 ...

Answer 3

文件说明:

HashSet <(Of <(T>)>)集合未排序,不能包含重复元素.如果订单或元素重复比应用程序的性能更重要,请考虑使用List <(Of <(T>)>)类和Sort方法.

因此,它是否实际上保留了当前实现中元素的顺序并不重要,因为它没有记录为这样做,即使它现在看起来可能在将来的任何时候都会发生变化(即使在修补程序中也是如此)框架).

您应该根据记录的合同进行编程,而不是实现细节.

Answer 4

阅读HashSet.AddIfNotPresent的源代码，您可以看到插入顺序被保留，假设没有任何删除。

因此new HashSet<string> { "Tom", "Dick", "Harry" }保留了顺序，但如果您随后删除 Dick 并添加 Rick，则顺序将为 [“Tom”、“Rick”、“Harry”]。