C# 中的 HashSet 和 Java 中的 HashSet 之间的区别。有什么替代方案

Question

我在 C# 与 Java 中遇到了这种奇怪的行为。 Java 中的 HashSet 似乎会比较对象中的内容并拒绝重复项，或者在检查“包含”时给出一个布尔值。在 C# 中情况并非如此。以下是代码示例： Java代码：

HashSet<List<Integer>> setOfLists = new HashSet<List<Integer>>();

List<Integer> list1 = Arrays.asList(1, 2, 3);
List<Integer> list2 = Arrays.asList(1, 2, 3);

// Adding list1 and list2 to the HashSet
setOfLists.add(list1);
setOfLists.add(list2);

// Checking if list1 is in the HashSet
System.out.println(setOfLists.contains(list1)); // Output is true

// Checking if new Array with same content is in the HashSet
System.out.println(setOfLists.contains(Arrays.asList(1, 2, 3))); // Output is true

// Checking the length of the HashSet
System.out.println(setOfLists.size()); // Output is 1

C#代码：

HashSet<List<int>> setOfLists = new HashSet<List<int>>();

List<int> list1 = new List<int> { 1, 2, 3 };
List<int> list2 = new List<int> { 1, 2, 3 };

// Adding list1 and list2 to the HashSet
setOfLists.Add(list1);
setOfLists.Add(list2);

// Checking if list1 is in the HashSet
Console.WriteLine(setOfLists.Contains(list1)); // Output is true

// Checking if new Array with same content is in the HashSet
Console.WriteLine(setOfLists.Contains(new List<int> { 1, 2, 3 })); // Output is false
// Checking the length of the HashSet
Console.WriteLine(setOfLists.Count); // Output is 2

我不明白为什么会有这种差异。正如我们在 Print 语句中看到的，对于对象，C# 无法通过内容查找重复项。 HashSet 应该用于消除重复项，并在 O(1) 时间内完成。

我从之前的答案中看到的最大区别是所有建议的解决方案的时间复杂度都是 O(N)，其中 N 是 HashSet 中元素（列表）的数量。然而，在 Java 中，这似乎不需要显式修改比较器就能发生，并且至少对于相当小的列表来说具有 O(1) 复杂度。

是否有任何替代选项可以在 C# 中实现这一目标，以 O(1) 时间复杂度实现这一目标？

Answer 1

List<T>

 类不会覆盖 

Equals() 或

GetHashCode()

方法，请参阅

检查两个列表是否相等

。这意味着这两个列表

List<int> list1 = new List<int> { 1, 2, 3 };
List<int> list2 = new List<int> { 1, 2, 3 };

不相等（根据

Equals()

），请参见以下示例代码：

List<int> list1 = new List<int> { 1, 2, 3 };
List<int> list2 = new List<int> { 1, 2, 3 };

Console.WriteLine(list1);
Console.WriteLine(list2);

Console.WriteLine(list1.GetHashCode());
Console.WriteLine(list2.GetHashCode());

Console.WriteLine(list1.Equals(list2));

这可能会生成以下输出：

System.Collections.Generic.List`1[System.Int32]
System.Collections.Generic.List`1[System.Int32]
37320431
339559
False

因此， 

HashSet<List<int>>

实例包含两个列表引用，它们（仍然）不相等，如代码中所示：

Console.WriteLine(setOfLists.Count); // Output is 2

解决方案是提供 

HashSet

实例应使用的自定义 IEqualityComparer 实现。它可能看起来像这样：

public class ListIntSequenceEqualComparator : IEqualityComparer<List<int>>
{
    public bool Equals(List<int> x, List<int> y)
    {
        return x.SequenceEqual(y);
    }

    public int GetHashCode([DisallowNull] List<int> obj)
    {
        return obj.Sum(); // or some other valid hashcode calculation
    }
}

通过此实现，您将获得与 java 中一样的预期结果：

HashSet<List<int>> setOfLists = new HashSet<List<int>>(new ListIntSequenceEqualComparator());

List<int> list1 = new List<int> { 1, 2, 3 };
List<int> list2 = new List<int> { 1, 2, 3 };

// Adding list1 and list2 to the HashSet
setOfLists.Add(list1);
setOfLists.Add(list2);

// Checking if list1 is in the HashSet
Console.WriteLine(setOfLists.Contains(list1));

// Checking if new Array with same content is in the HashSet
Console.WriteLine(setOfLists.Contains(new List<int> { 1, 2, 3 }));
// Checking the length of the HashSet
Console.WriteLine(setOfLists.Count);

这将生成以下输出：

True
True
1