值等于和循环引用:如何解决无限递归?
我有一些包含几个字段的类。我需要通过值来比较它们,即如果一个类的两个实例包含相同的数据,则它们是相等的。我已经覆盖了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); // *Exception!
// 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可以拥有哪些价值。
对于我感兴趣的
一般情况下 - 我们在那里有类C1
,...,Cn
其中每个类可以有任意数量的值(如int
,string
,... ),以及任何数目的参考文献的任何其它类的C1
,...,Cn
(例如,通过具有针对每个类型Ci
一个字段ICollection<Ci>
) -
问题“是两个对象A
和B
等于? “,在我这里所描述的平等意识,
似乎等同于
问题“两年有限,直接连接,彩色图表G
和H
,不存在从G
的同构到H
?“。
这里是等价:
- 图形顶点对应于
object
S(类实例) - 图中的边对应于引用
object
小号 - 颜色对应于值的砾岩和类型本身(即两个顶点的颜色相同,如果它们对应的
object
具有相同的类型和相同的值)
这是一个NP难题,所以我认为我会放弃实施该计划的计划,而采用无循环参考的方法。
一个简单的解决方法(用于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
,因为我的自定义比较器没有超载。
根据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。
就像你说的那样,一个无限递归可能发生在X长度的圆圈中(例如:在10次迭代之后,它指向第二个圆柱体,然后圆圈再次开始)。如果递归是从1导航到1,而不是1导航到很多,那么我会包含一个“访问节点”列表,并验证当前是否已经处理,如果是,则返回。 – Dryadwoods
正如上面建议的那样,通过/保存一个哈希集或其他已经被测试/被调用的引用。它可以是一个可选参数,设置为null,在第一次调用之后被创建并传递。 – Rob
在我的opionion中,你的'Equals'实现太严格了。为什么两个人只有拥有同一个喜爱的设备才是平等的?为什么一个人在这个周末去新俱乐部时会有所不同?一个简单的解决方法是引入一个'Id'属性 –