值等于和循环引用：如何解决无限递归？

Question

我有一些包含几个字段的类。我需要通过值来比较它们，即如果一个类的两个实例包含相同的数据，则它们是相等的。我已经覆盖了GetHashCode和Equals方法。

可能会发生这些类包含循环引用。

例如：我们希望模拟机构（如政府，体育俱乐部等）。一个机构有一个名字。 A Club是一个有名字和成员名单的机构。每个成员都有一个Person，它有一个名字和一个最喜欢的机构。如果某个俱乐部的成员将该俱乐部作为他最喜欢的机构，我们有一个循环参考。

但循环引用与值相等一起导致无限递归。下面是一个代码示例：

interface IInstitution { string Name { get; } } 

class Club : IInstitution 
{ 
    public string Name { get; set; } 
    public HashSet<Person> Members { get; set; } 

    public override int GetHashCode() { return Name.GetHashCode() + Members.Count; } 

    public override bool Equals(object obj) 
    { 
     Club other = obj as Club; 
     if (other == null) 
      return false; 

     return Name.Equals(other.Name) && Members.SetEquals(other.Members); 
    } 
} 

class Person 
{ 
    public string Name { get; set; } 
    public IInstitution FavouriteInstitution { get; set; } 

    public override int GetHashCode() { return Name.GetHashCode(); } 

    public override bool Equals(object obj) 
    { 
     Person other = obj as Person; 
     if (other == null) 
      return false; 

     return Name.Equals(other.Name) 
      && FavouriteInstitution.Equals(other.FavouriteInstitution); 
    } 
} 

class Program 
{ 
    public static void Main() 
    { 
     Club c1 = new Club { Name = "myClub", Members = new HashSet<Person>() }; 
     Person p1 = new Person { Name = "Johnny", FavouriteInstitution = c1 } 
     c1.Members.Add(p1); 

     Club c2 = new Club { Name = "myClub", Members = new HashSet<Person>() }; 
     Person p2 = new Person { Name = "Johnny", FavouriteInstitution = c2 } 
     c2.Members.Add(p2); 

     bool c1_and_c2_equal = c1.Equals(c2); // StackOverflowException! 
      // c1.Equals(c2) calls Members.SetEquals(other.Members) 
      // Members.SetEquals(other.Members) calls p1.Equals(p2) 
      // p1.Equals(p2) calls c1.Equals(c2) 
    } 
} 

c1_and_c2_equal应该返回true，而事实上我们（人类）可以看出，他们是价值相等的思维一点点，不会导致无限递归。但是，我无法真正说出我们如何解释这一点。但是，既然有可能，我希望有一种方法可以在代码中解决这个问题！

所以问题是：如何检查值相等而不会遇到无限递归？

请注意，我需要通常解决循环引用，而不仅仅是上面的情况。自c1参考文献p1和p1参考文献c1我将称它为2圈。可以有其他的n圈，例如如果一个俱乐部A有一个会员M，他的最爱是俱乐部B，该俱乐部的会员N最喜欢的俱乐部是A。那将是一个4圈。其他对象模型也可能允许奇数为n的n圈。我正在寻找一种解决所有这些问题的方法，因为我不会提前知道n可以拥有哪些价值。

Answer 1

对于我感兴趣的

一般情况下 - 我们在那里有类C1，...，Cn其中每个类可以有任意数量的值（如int，string，... ），以及任何数目的参考文献的任何其它类的C1，...，Cn（例如，通过具有针对每个类型Ci一个字段ICollection<Ci>） -

问题“是两个对象A和B等于？ “，在我这里所描述的平等意识，

似乎等同于

问题“两年有限，直接连接，彩色图表G和H，不存在从G的同构到H？“。

这里是等价：

• 图形顶点对应于object S（类实例）
• 图中的边对应于引用object小号
• 颜色对应于值的砾岩和类型本身（即两个顶点的颜色相同，如果它们对应的object具有相同的类型和相同的值）

这是一个NP难题，所以我认为我会放弃实施该计划的计划，而采用无循环参考的方法。

Answer 2

一个简单的解决方法（用于RDBMS）是使用唯一的Id来标识Person（任何类型）。那么你不需要比较每一个其他的财产，你永远不会遇到这样的cuircular参考。

另一种方法是在Equals中进行不同的比较，因此只提供深度检查，仅针对Equals的类型，而不针对引用类型。你可以使用自定义比较：

public class PersonNameComparer : IEqualityComparer<Person> 
{ 
    public bool Equals(Person x, Person y) 
    { 
     if (x == null && y == null) return true; 
     if (x == null || y == null) return false; 
     if(object.ReferenceEquals(x, y)) return true; 
     return x.Name == y.Name; 
    } 

    public int GetHashCode(Person obj) 
    { 
     return obj?.Name?.GetHashCode() ?? int.MinValue; 
    } 
} 

现在你可以改变Equals实施Club避免了Members（人）会用自己深深的检查，其中包括机构，但只有他们Name：

public override bool Equals(object obj) 
{ 
    if (Object.ReferenceEquals(this, obj)) 
     return true; 

    Club other = obj as Club; 
    if (other == null) 
     return false; 

    var personNameComparer = new PersonNameComparer(); 
    return Name.Equals(other.Name) 
     && Members.Count == other.Members.Count 
     && !Members.Except(other.Members, personNameComparer).Any(); 
} 

您注意到我无法使用SetEquals，因为我的自定义比较器没有超载。

Answer 3

根据Dryadwoods的建议，我更改了Equals方法，以便我可以跟踪已经比较的项目。

首先，我们需要一个相等比较器，它检查参考平等相应对元素：

public class ValuePairRefEqualityComparer<T> : IEqualityComparer<(T,T)> where T : class 
{ 
    public static ValuePairRefEqualityComparer<T> Instance 
     = new ValuePairRefEqualityComparer<T>(); 
    private ValuePairRefEqualityComparer() { } 

    public bool Equals((T,T) x, (T,T) y) 
    { 
     return ReferenceEquals(x.Item1, y.Item1) 
      && ReferenceEquals(x.Item2, y.Item2); 
    } 

    public int GetHashCode((T,T) obj) 
    { 
     return RuntimeHelpers.GetHashCode(obj.Item1) 
      + 2 * RuntimeHelpers.GetHashCode(obj.Item2); 
    } 
} 

这里是的Club改性Equals方法：

static HashSet<(Club,Club)> checkedPairs 
    = new HashSet<(Club,Club)>(ValuePairRefEqualityComparer<Club>.Instance); 

public override bool Equals(object obj) 
{ 
    Club other = obj as Club; 
    if (other == null) 
     return false; 

    if (!Name.Equals(other.Name)) 
     return; 

    if (checkedPairs.Contains((this,other)) || checkedPairs.Contains((other,this))) 
     return true; 

    checkedPairs.Add((this,other)); 

    bool membersEqual = Members.SetEquals(other.Members); 
    checkedPairs.Clear(); 
    return membersEqual; 
} 

版本为Person类似于。请注意，我添加(this,other)到checkedPairs并检查或者(this,other)或(other,this)载，因为这可能会发生的c1.Equals(c2)第一个电话之后，我们最终得到的c2.Equals(c1)代替c1.Equals(c2)通话。我不确定这是否真的发生，但由于我看不到SetEquals的实施，我相信这是一种可能性。

由于我对已经检查过的对使用静态字段并不满意（如果程序并发，它将不起作用！），我问另一个问题：make a variable last for a call stack。