c# - 具有复杂相等性的 HashSet

Question

考虑下面的类

public class X
{
    //Unique per set / never null
    public ulong A { get; set; }

    //Unique per set / never null
    public string B { get; set; }

    //Combination of C and D is Unique per set / both never null
    public string C { get; set; }
    public string D { get; set; }

    public override bool Equals(object obj)
    {
        var x = (X)obj;

        if (A == x.A || B==x.B)
            return true;

        if (C+D==x.C+x.D)
            return true;

        return false;            
    }

    public override int GetHashCode()
    {
        return 0;
    }
}

我想不出编写一个散列函数，在其中应用上述属性的注释组合，就像在 Equals 函数中一样，在这种情况下，我最好的选择是从 GetHashCode 返回 0。还是我遗漏了什么？

Answer 1

这是不可能的。这是根本问题。事实上这是可能的，但这是一个很难解决的问题。

解释

反过来想一下，在什么情况下你的对象是不相等的？从代码中我可以通过这个表达式看出它们是什么:

return A == x.A || B==x.B || (C+D)==(x.C+x.D)

And not equal 表达式:

return A!=x.A && B!=x.B && (C+D)!=(x.C+x.D)

因此，您的哈希值对于相等表达式中的任何特定值都应该相同，对于非相等表达式中的任何特定值都应该相同。值可以变化到无穷大。

这两个表达式唯一真正可能的解决方案是常量值。但是这个解决方案在性能上不是可选的，因为它只会蒸发 GetHashCode 覆盖的所有含义。

考虑使用 IEqualityComperer 接口(interface)和等式算法来解决您正在解决的任务。

我认为找到相等对象的最佳解决方案是索引。例如，您可以看到数据库是如何制作的，以及它们如何使用位索引。

为什么哈希如此残酷？

如果可能的话，世界上所有的数据库都可以轻松地将所有内容散列到一个哈希表中，所有快速访问的问题都将得到解决。 例如，假设您的对象不是具有属性的对象，而是整个对象状态(例如 32 个 bool 属性可以表示为整数)。

散列函数基于此状态计算散列，但在您的情况下，您明确地告诉它空间中的某些状态实际上是相等的:

class X
{
    bool A;
    bool B;
}

你的空间是:

A      B
false  false  -> 0
false  true   -> 1
true   false  -> 2
true   true   -> 3

如果你这样定义相等性:

bool Equal(X x) { return x.A == A || x.B == B; }

你基本上定义了这个状态平等:

0 == 0
0 == 1
0 == 2
0 != 3

1 == 0
1 == 1
1 != 2
1 == 3

2 == 0
2 != 1
2 == 2
2 == 3

3 != 0
3 == 1
3 == 2
3 == 3

这个集合应该有相​​同的散列:{0,1,2} {0,1,3} {0,2,3} {1,2,3}

因此，您的所有集合在散列中都应该是 EQUAL。由此得出结论，不可能创建比常量值更好的哈希函数。