7

我可以为以下比较器逻辑编写哈希码函数吗？

如果 (A, B, C) 中的至少两个属性匹配，则 的两个实例My相等。

Equals 部分很简单，但我对哈希码部分感到困惑，我的一部分人认为这可能是不可能的。

class MyOtherComparer : IEqualityComparer<My>
{
    public bool Equals(My x, My y)
    {
        if (Object.ReferenceEquals(x, y)) 
            return true;      

        if (Object.ReferenceEquals(x, null) || Object.ReferenceEquals(y, null)) 
            return false;

        int matches = 0;

        if(x.A == y.A) matches++;

        if(x.B == y.B) matches++;

        if(x.C == y.C) matches++;

        // match on two out of three
        return  (matches > 1)
    }

    // If Equals() returns true for a pair of objects 
    // then GetHashCode() must return the same value for these objects.
    public int GetHashCode(My x)
    {
       // ???
    }
}

更新：除了 Reed Copsey 的正确答案之外，Ethan Brown 清楚地说明了关于模糊比较器的一般有用性的一个非常重要的观点 - 请参阅他的答案以及全面了解这个问题/答案的基础。

4

6 回答 6

5

是的，这是可能的。最简单的实现是始终返回一个常量。 

public int GetHashCode(My x) 
{ 
   return 0;
}

GetHashCode文档指出：

实现需要确保如果 Equals 方法为两个对象 x 和 y 返回 true，则 GetHashCode 方法为 x 返回的值必须等于为 y 返回的值。

但是，您也可以完全自由地为两个不相等的对象返回相同的哈希码。

话虽如此，这可能会导致某些算法的性能非常差，因为您会遇到很多哈希冲突。但是，鉴于您的奇数/唯一相等性检查的性质，这可能是必需的。

请注意，无论如何这都会有问题。鉴于您的逻辑，可能有三个对象， wherecomparer.Equals(foo, bar)==true和comparer.Equals(foo, baz)==truebut comparer.Equals(baz, bar)==false。这在使用的许多情况下可能会出现问题IEqualityComparer<T>。

于 2012-06-04T17:52:34.137 回答
1

对于两个相等的对象，哈希码必须相同，但对于两个不同的对象，它不必不同。您可以为所有对象返回相同的值以满足IEqualityComparer消费者的需求，但我不知道在您的情况下从哈希中获得任何速度优势。

于 2012-06-04T17:52:07.390 回答
1

我可以为以下比较器逻辑编写哈希码函数吗？

是的。你总是可以为任何东西写一个哈希码。问题是它的效率如何。无论如何，您始终可以拥有：

public int GetHashCode()
{
  return 0;
}

它总是有效的，但它非常*低效*。

于 2012-06-04T17:53:33.053 回答
1

假设我们有 2 个对象 A，B。它们中的每一个都有属性 p1、p2 和 p3。假设 A.p1 == B.p1 和 A.p3 == B.p3 ，如果哈希函数依赖于 p2 ，那么 A 和 B 会有所不同，因此它们不相等。如果要根据 p1 和 p3 计算哈希函数，有很多例子哈希函数不会返回正确的哈希值，并且许多相等的对象将不相等。我认为我们不能有一个变量函数。您可以使用一个常量，但如果您想将其用作字典或哈希表中的哈希键，您将不会获得接近 O(1) 的复杂性。

于 2012-06-04T17:56:48.780 回答
1

获得非常数散列函数的核心问题是您无法确保跨等式的传递性。通常，相等被认为是可传递的。也就是说，A=B 和 B=C 意味着 A=C（这进一步意味着 A、B 和 C 都将具有相同的哈希码）。但是，根据您对相等的定义，您可以有 A=B、B=C 和 A!=C。理想情况下，不相等的元素会有不同的哈希码，所以 A 和 C 会有不同的哈希码；但它们不能，因为它们都等于 B，所以它们都必须具有相同的哈希码。

获得非常量散列函数的唯一方法是，如果您对总集合有所了解。您必须将集合划分为“平等箱”，其中箱中的每个元素都等于箱中的其他元素（包括一个箱的可能性）。一旦你完成了这个分区，你就可以使用它来生成一个非常数算法（假设你得到多个 bin）来生成哈希码。

关于平等箱的想法是可能有很多这样的箱配置。作为选择标准，您可能希望最大化 bin 的数量（以提高哈希表查找性能）。退化的情况（如 Reed Copsey 的正确答案所示）是您将所有内容放在同一个 bin 中（尽管，正如 supercat 在下面的评论中指出的那样，“平等 bin”这个名称会产生误导）。这不会违反哈希值的任何约束，但会导致期望具有产生非退化分区的值的算法性能不佳。

正如下面 supercat 指出的那样，要满足哈希值的约束，必须满足以下条件：如果两个元素在两个不同的 bin 中，则它们一定不相等（但是，同一个 bin 中的两个元素不必相等） .

于 2012-06-04T18:17:10.357 回答
0

看到您真正的问题是处理 except 扩展方法，我决定为您提出一些建议，尽管不是真正的答案。

public class EqualityComparer<T> : IEqualityComparer<T>
{
    private readonly Func<T, T, bool> _comparer;
    private readonly Func<T, int> _hashCoder;

    public EqualityComparer(Func<T, T, bool> comparer, Func<T, int> hashCoder = null)
    {
        if (comparer == null)
        {
            throw new ArgumentNullException("comparer");
        }

        this._comparer = comparer;
        this._hashCoder = hashCoder ?? (x => 0);
    }

    public bool Equals(T x, T y)
    {
        return this._comparer(x, y);
    }

    public int GetHashCode(T obj)
    {
        return this._hashCoder(obj);
    }
}

然后你可以像这样使用它：

arr1.Except(arr2, new EqualityComparer<dynamic>((x, y) =>
     {
         if (ReferenceEquals(x, y))
             return true;

         if (ReferenceEquals(x, null) ||
             ReferenceEquals(y, null))
             return false;

         var matches = 0;

         if (x.A == y.A) matches++;
         if (x.B == y.B) matches++;
         if (x.C == y.C) matches++;

         return (matches > 1);
     }));
于 2012-06-04T18:21:46.160 回答