Array.IStructuralEquatable.GetHashCode存在Bug吗？

Question

Array.IStructuralEquatable.GetHashCode存在Bug吗？

6

在编写一个使用字节数组作为内部存储的不可变ByteArray类时，我实现了IStructuralEquatable接口。在我的实现中，我将计算哈希码的任务委托给了内部数组。在测试过程中，令我惊讶的是，我发现我的两个不同的数组具有相同的结构哈希码，也就是说它们从GetHashCode返回了相同的值。要复现：

IStructuralEquatable array11 = new int[] { 1, 1 };
IStructuralEquatable array12 = new int[] { 1, 2 };
IStructuralEquatable array22 = new int[] { 2, 2 };

var comparer = EqualityComparer<int>.Default;
Console.WriteLine(array11.GetHashCode(comparer));     // 32
Console.WriteLine(array12.GetHashCode(comparer));     // 32
Console.WriteLine(array22.GetHashCode(comparer));     // 64

IStructuralEquatable 是一个相当新的且不为人知的接口，但我在某处读到它可以用于比较集合和数组的内容。我是错了吗？还是我的 .Net 出了问题？

请注意，我并不是在谈论 Object.GetHashCode！

编辑：所以，显然我错了，因为不相等的对象可能具有相等的哈希码。但是，GetHashCode 返回一组随机分布的值不是一个要求吗？经过更多测试，我发现任何两个具有相同第一个元素的数组具有相同的哈希值。我仍然认为这是奇怪的行为。

- Daniel A.A. Pelsmaeker

除了指向重复哈希码作为记录行为的答案之外，一些推理和反思也会导致您得出相同的结论。考虑到只有约42亿个不同的哈希码。您能创建超过此数量的GetHashCode调用类型的不同对象吗？在这种情况下，很容易看出答案是“是”。因此，GetHashCode是一种压缩投影到较小集合的方式-必定存在重复项。 - codekaizen

可能让你惊讶的是，Array.IStructuralEquatable.GetHashCode 只使用最后8个元素来计算哈希码。 - Michael Graczyk

实际上有一个 bug。请看我的编辑。 - Michael Graczyk

@MichaelGraczyk - 尽管在某个特定平台上的 .Net 版本可能是正确的，但我还是不得不发出标准警告，不要依赖哈希码的值或计算方式，因为不能保证在更新或平台之间相同。 - codekaizen

@codekaizen 是的，我会澄清我所说的是微软.NET。 - Michael Graczyk

3个回答

5

这个 bug 已经修复，至少从 .NET 4.6.2 开始。你可以通过 Reference Source 查看。

ret = CombineHashCodes(ret, comparer.GetHashCode(GetValue(i)));

- Mathieu Renda

0

GetHashCode 对于不相等的实例不返回唯一值。但是，相等的实例总是返回相同的哈希码。

引用自 Object.GetHashCode 方法：

如果两个对象比较为相等，则每个对象的 GetHashCode 方法必须返回相同的值。但是，如果两个对象不相等，则两个对象的 GetHashCode 方法不必返回不同的值。

你的观察结果与文档不冲突，并且实现中没有错误。

- Martin Liversage

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Michael Graczyk · Accepted Answer

你所描述的不是一个 bug。GetHashCode() 不保证对于不相等的对象产生唯一的哈希值。

来自MSDN：

如果两个对象比较相等，每个对象的 GetHashCode 方法必须返回相同的值。但是，如果两个对象不相等，则这两个对象的 GetHashCode 方法不必返回不同的值。编辑虽然 MSFT .NET 实现了 Array.IStructuralEquatable 的 GetHashCode() 遵循上述 MSDN 文档的原则，但似乎作者并没有按照预期实现它。

以下是 "Array.cs" 中的代码：

    int IStructuralEquatable.GetHashCode(IEqualityComparer comparer) { 
        if (comparer == null)
            throw new ArgumentNullException("comparer"); 
        Contract.EndContractBlock();

        int ret = 0;

        for (int i = (this.Length >= 8 ? this.Length - 8 : 0); i < this.Length; i++) {
            ret = CombineHashCodes(ret, comparer.GetHashCode(GetValue(0))); 
        } 

        return ret; 
    }

请特别注意这一行：

ret = CombineHashCodes(ret, comparer.GetHashCode(GetValue(0)));

除非我弄错了，否则这里的0应该是指i。由于这个原因，对于具有相同max(0, n-8th)元素的数组（其中n是数组的长度），GetHashCode()总是返回相同的值。这并不是错误（不违反文档），但显然不如替换0为i好。此外，如果代码只使用数组中的单个值，则没有循环的必要。