.Net 5 的 HashSet<string> + SequenceEqual() 结果令人惊讶？

Question

给出这样的代码...

var a = new HashSet<string>(){  "A", "A", "B" };
var b = new HashSet<string>(){  "A", "B" };

var areTheyEqual = a.SequenceEqual(b);

我希望 areTheyEqual 是 false，但它是 true：

查看 documentation for .SequenceEqual ("Determines whether two sequences are equal according to an equality comparer."), and even the code，我仍然有点困惑为什么逐个索引/组合的 .MoveNext 和 .Equals() 调用总体上可以产生 true。

如果有人能阐明为什么会发生这种情况，我将不胜感激在这里提供更多见解。

Answer 1

根据 documentation，强调我的：

The HashSet<T> class provides high-performance set operations. A set is a collection that contains no duplicate elements, and whose elements are in no particular order.

还有：

The HashSet<T> class is based on the model of mathematical sets and provides high-performance set operations similar to accessing the keys of the Dictionary<TKey,TValue> or Hashtable collections.

鉴于这两个评论，

// a ends up containing "A" and "B", rather than "A", "A", and "B"
var a = new HashSet<string>(){  "A", "A", "B" };
var b = new HashSet<string>(){  "A", "B" };

var areTheyEqual = a.SequenceEqual(b);

所以它们是等价的。但是，正如文档所述，HashSet 的实现不保证项目的存储或迭代顺序。这意味着您不应该依赖两个 HashSet 之间的比较工作，即使您查看了当前版本的 .NET 的实现，因为实现可以自由更改任何未来版本的顺序。

相反，您可以使用 SortedSet:

A SortedSet<T> object maintains a sorted order without affecting performance as elements are inserted and deleted. Duplicate elements are not allowed. Changing the sort values of existing items is not supported and may lead to unexpected behavior.

因此，给定：

var a = new SortedSet<string>() { "A", "A", "B" };
var b = new SortedSet<string>() { "B", "A" };

a.SequenceEqual(b);

这些被认为是相等的。

顺便说一句，HashSet 的 Add method, and SortedSet's equivalent、returns bool，如果将项目添加到 [=50]，则为 true =]，如果不是，则 false。这为您提供了一种确定何时尝试插入重复项的方法，如果这在插入时对您很重要。这与 List.Add() 形成对比，其中列表将愉快地存储重复项，这意味着此处 API 的差异有助于传达 collection 类型之间的差异。

Answer 2

@John H 的回答并没有说明全部。

此测试通过。

public void SequenceEqualTest()
{
    var a = new HashSet<string> { "A", "A", "B" };
    var b = new HashSet<string> { "A", "B"};
    var c = new HashSet<string> { "B", "A"};
    a.SequenceEqual(b).Should().BeTrue();
    a.SequenceEqual(c).Should().BeFalse();
    b.SequenceEqual(c).Should().BeFalse();
}

第一个断言是有道理的，因为用“A”、“A”、“B”初始化与“A”、“B”相同，因为第二个“A”是通过调用私有方法抛出的， AddIfNotPresent.

同时

whose elements are in no particular order

是正确的，从实用的角度来说，两个初始化的顺序将导致相同的底层数据结构，它使用相同的底层确定性枚举器。因此，两个哈希集上的枚举数为 SequenceEqual.

提供了相同的结果

那么为什么接下来的两个断言是错误的？

嗯，上面的构造函数采用 IEnumerable<string>，它具有调用代码指定的确定性顺序； a和b有一个顺序，c有相反的顺序。此构造函数调用 UnionWith，它对调用 AddIfNotPresent 的输入集合进行操作，后者使用散列表所期望的分桶机制。该机制导致内容位于不同的桶中。

这就是我的意思。在 a 和 c 的调试器下，我们得到

a	c

这清楚地表明数据结构中的内部槽被翻转了。枚举器的肉是

while (_index < _set._lastIndex)
{
    if (_set._slots[_index].hashCode >= 0)
    {
        _current = _set._slots[_index].value;
        _index++;
        return true;
    }
    _index++;
}

这清楚地显示了代码从最低索引槽到最高索引槽的确定性枚举。

.Net 5 的 HashSet<string> + SequenceEqual() 结果令人惊讶？

.Net 5's HashSet<string> + SequenceEqual() result surprising?

.net

.net-5