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

Question

我有一些包含多个字段的 classes。我需要按值比较它们，即如果 class 的两个实例包含相同的数据，则它们是相等的。为此，我已经覆盖了 GetHashCode 和 Equals 方法。

这些 class 可能会包含循环引用。

示例： 我们想要建立机构模型（如政府、体育俱乐部等）。一个机构有一个名字。 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); // WhosebugException!
            // 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应该returntrue，其实我们（人类）稍加思考就可以看出他们是价值平等的，不用运行进入无限递归。但是，我真的不能说我们是如何解决这个问题的。但既然可以，我希望也有办法在代码中解决这个问题！

所以问题是：如何在没有运行无限递归的情况下检查值是否相等？

请注意，我需要解决一般的循环引用，而不仅仅是上面的情况。我将其称为 2 圈，因为 c1 引用了 p1，而 p1 引用了 c1。可以有其他 n 圈，例如如果一个俱乐部 A 有一个成员 M，其最喜欢的俱乐部 B 有成员 N，其最喜欢的俱乐部是 A。那将是一个4圈。其他对象模型也可能允许具有奇数 n 的 n 圆。我正在寻找一种方法来一次解决所有这些问题，因为我不会事先知道 n 可以有哪个值。

Answer 1

一个简单的解决方法（在 RDBMS 中使用）是使用唯一的 Id 来标识 Person（任何类型）。然后你不需要比较每个其他属性并且你永远不会运行进入这样的循环引用。

另一种方法是在 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;
    }
}

现在您可以更改 Club 的 Equals 实施，以避免 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 2

根据 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 的实现，我相信这是有可能的。

因为我不喜欢为已经检查过的对使用静态字段（如果程序是并发的，它将不起作用！），我问了另一个问题：.

Answer 3

对于我感兴趣的一般情况

-- 我们有 classes C1, ..., Cn 其中每个 classes 可以有任意数量的值（比如 int, string, ...) 以及对 C1, ..., Cn 的任何其他 classes 的任意数量的引用（例如通过每种类型 Ci 都有一个字段 ICollection<Ci>) --

问题"Are two objects A and B equal?"，在我这里描述的平等意义上，

似乎等同于

问题"For two finite, directed, connected, colored graphs G and H, does there exist an isomorphism from G to H?".

这是等价的：

图顶点对应于 objects（class 个实例）
图边对应于对 objects
颜色对应于值的组合和类型本身（即如果两个顶点对应的 object 具有相同的类型和相同的值，则它们的颜色相同）

这是一个 NP-hard 问题，所以我想我要放弃我的计划来实现它，转而采用无循环引用的方法。

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

Value-equals and circular references: how to resolve infinite recursion?

c#

recursion

equality

infinite