为什么具有相同元素的HashSet在调用GetHashCode()时返回不同的值？

Question

为什么HashSet<T>.GetHashCode()在有相同元素时返回不同的哈希码？

例如：

[Fact]
public void EqualSetsHaveSameHashCodes()
{
    var set1 = new HashSet<int>(new [] { 1, 2, 3 } );
    var set2 = new HashSet<int>(new [] { 1, 2, 3 } );

    Assert.Equal(set1.GetHashCode(), set2.GetHashCode());
}

这个测试失败了。为什么呢？

我怎样才能得到我需要的结果？“相等的集合产生相同的哈希值”

- SuperJMN

---

你需要实现自己的GetHashCode函数，该函数基于元素。 - LarsTech

请查看Hashset.GetHashCode方法的文档 https://learn.microsoft.com/zh-cn/dotnet/api/system.collections.generic.hashset-1?view=netframework-4.7.2#methods - Sir Rufo

你的哈希函数正在比较两个数组，而不是数组的内容。 - jdweng

相等的集合确实会给出相同的哈希码。你的 set1 和 set2 不相等，因为它们是不同的对象。测试一下；set1.Equals(set2) 返回 false。 - Dour High Arch

这感觉像是一个 XY 问题 - https://meta.stackexchange.com/questions/66377/what-is-the-xy-problem 。你为什么关心 HashCode？你的真正潜在问题是什么？ - mjwills

Answer 1

HashSet<T>默认情况下没有值相等的语义。它具有引用相等的语义，因此即使包含的元素相同，两个不同的哈希集合也不会相等或具有相同的哈希码。

您需要使用特定目的的IEqualityComparer<HashSet<int>>来获得所需的行为。您可以编写自己的实现，也可以使用框架为您提供的默认实现：

var hashSetOfIntComparer = HashSet<int>.CreateSetComparer();

//will evaluate to true
var haveSameHash = hashSetOfIntComparer.GetHashCode(set1) ==
                   hashSetOfIntComparer.GetHashCode(set2);

简而言之：

我该如何得到我需要的结果？“相等的集合给出相同的哈希码”

如果您计划使用默认实现的HashSet<T>.GetHashCode()，那么您无法得到所需的结果。您可以使用特殊的比较器或扩展HashSet<T>并覆盖Equals和GetHashCode以满足您的需求。

- InBetween

Answer 2

默认情况下（除非有特殊说明），只有引用类型引用同一对象时才被认为相等。作为开发人员，您可以重写Equals()和GetHashCode()方法，以便您认为相等的对象返回Equals为true，并且GetHashCode返回相同的int值。

根据您使用的测试框架，将存在CollectionAssert.AreEquivalent()或接受比较器的Assert.Equal的覆盖。

- Adam G

---

如果你想比较集合而不是哈希码，你已经有内置的方法 (SetEquals) 可以使用，不需要额外引入库。 - greenoldman

Answer 3

你可以实现一个自定义的HashSet，覆盖GetHashCode函数，从所有内容生成新的哈希码，如下所示：

public class HashSetWithGetHashCode<T> : HashSet<T>
{
    public override int GetHashCode()
    {
        unchecked // Overflow is fine, just wrap
        {
            int hash = 17;
            foreach (var item in this)
                hash = hash * 23 + item.GetHashCode();
            return hash;
        }
    }
}

- Nathan Werry

---

这将给你一个O(n)的复杂度，这对于获取哈希码来说是不可取的。恐怕这就是被踩的原因。 - SuperJMN

我看不到比O(N)更快的方法，但更令人担忧的是，这个实现取决于排序，这对于HashSet来说并不合适。 - Jon Skeet

Jon Skeet 很棒。除了之前提到的性能问题，按照这个函数的要求排序元素或者保持已排序项目的并行集合，在哈希操作中会是可以接受的吗？ - Nathan Werry

这完全是错误的。相等的集合必须生成相同的哈希码，并且在HashSet或Dictionary元素上进行迭代并不能保证顺序。但对于所有元素使用相同的权重将能解决问题。 - greenoldman