值等於和循環引用：如何解決無限遞歸？

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。