HashSet的复杂平等

考虑下面的类HashSet的复杂平等

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还是我错过了什么？

来源

2016-09-21 Bread

在不同状态下返回零是非常糟糕的解决方案 – eocron

我无法理解如何在不完全验证“ A = A'，'B = B'，'C = C'，和'D = D' ... –

@ eocron06真的很糟糕的是返回'GetHashCode'的改变值... ...一直返回0 LEA st满足物品在容器中时价值不应该改变的合同。事实上，它使HashSet操作O（n），但至少他们会产生正确的结果。 –

这是不可能的。这是根本问题。其实这是可能的，但这是非常难解决的问题。

说明

试想一下反向，在这种情况下，你的对象是不相等？从代码中，我可以看到他们是通过这种表达平等：

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

而且不等于表达：

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

所以，你的哈希应该是一样的平等表达任何特定的值，同样对于任何特定不是平等表达中的价值。值可以变化为无穷大。

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

考虑使用IEqualityComperer接口以及您正在解决的任务的等式alghorithms。

我想找到相等的对象最好的解决办法是索引。您可以看到如何创建数据库以及它们如何使用位索引。

散列为什么这么残忍？

如果有可能，在世界上所有的数据库很容易凑在一个哈希表中的一切，并能够快速访问所有的问题都将迎刃而解。例如，想象您的对象不是作为具有属性的对象，而是作为整个对象状态（例如32个布尔属性可以表示为整数）。

Hash函数的计算基于这种状态下散，但在你的情况下，你明确地告诉大家，从它的空间，有些国家实际上等于：

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; }

你基本上定义这个状态平等Y：

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}

所以，你所有的集合都应该等于散列。由此得出结论，这不可能比常量值更好地创建哈希函数。

来源

2016-09-21 07:24:48 eocron

如果你有'&&'而不是'||'，那会有效。 – MarcinJuraszek

我编辑了我的答案。 – eocron

-3

你可以考虑创建一个匿名类型，然后从返回的哈希码：

public override int GetHashCode() 
{ 
    // Check that an existing code hasn't already been returned 

    return new { A, B, C + D }.GetHashCode(); 
}

确保你创造一些自动化的测试来验证对象具有相同的值返回相同的哈希码。

请记住，一旦散列码被发出，您必须继续返回该代码而不是新代码。

来源

2016-09-21 07:33:04

在这种情况下，我认为将对象定义为唯一的散列码（即覆盖GetHashCode）不应该是用于特定HashSet的散列码。

换句话说，如果你的类的属性是所有等于（如果任何属性匹配，则不应该）。但是，如果您想按特定标准对它们进行分组，请使用IEqualityComparer<X>的特定实施。

此外，强烈考虑使类不可变。

除此之外，我认为唯一的散列码真的会工作是不变的。任何试图成为更聪明会失败：

// if any of the properties match, consider the class equal 
public class AnyPropertyEqualityComparer : IEqualityComparer<X> 
{ 
    public bool Equals(X x, X y) 
    { 
     if (object.ReferenceEquals(x, y)) 
      return true; 

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

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

    public int GetHashCode(X x) 
    { 
     return 42; 
    } 
}

既然你将必须评估在任何情况下，所有的属性，一个HashSet也不会有多大效果在这种情况下，你还不如用普通List<T>（其中如果将项目列表插入到“哈希集合”中，将降级到O(n*n)

来源

2016-09-21 07:46:24 Groo

HashSet的复杂平等

回答

相关问题