正如我在上面的评论中提到的，你的代码有一些编译错误，你遗漏了很多错误，这使得很难100%确定一旦代码完成它应该如何工作。但是在完成代码后，修复了一个明显的拼写错误（你写了，但我相信你的意思是）和一件我认为是拼写错误的事情（我不认为你的意思是嵌套在里面），删除一些no-op代码，并重组一点（到我发现更清晰的风格;YMMV），我得到这个：idx2 = xs.lastIndexOf(o2[i])idx2 = ys.lastIndexOf(o2[i])if (!equal(o1[i], o2[i], xs, ys))if (idx1 == idx2)
boolean equal(final Object[] o1, final Object[] o2)
{
return _equal(o1, o2, new ArrayList<Object>(), new ArrayList<Object>());
}
private static boolean _equal(final Object[] o1, final Object[] o2,
final List<Object> xs, final List<Object> ys)
{
if(o1.length != o2.length)
return false;
xs.add(o1);
ys.add(o2);
try
{
for(int i = 0; i < o1.length; i++)
{
if(o1[i] == null && o2[i] == null)
continue;
if(o1[i] == null || o2[i] == null)
return false;
if(o1[i].equals(o2[i]))
continue;
if(! (o1[i] instanceof Object[]) || ! (o2[i] instanceof Object[]))
return false;
final int idx1 = xs.lastIndexOf(o1[i]);
if(idx1 >= 0 && idx1 == ys.lastIndexOf(o2[i]))
continue;
if(! _equal((Object[])o1[i], (Object[])o2[i], xs, ys))
return false;
}
return true;
}
finally
{
xs.remove(xs.size() - 1);
ys.remove(ys.size() - 1);
}
}
这主要有效。逻辑是，每当它得到两个s时，它就会检查它当前是否正在比较堆栈中更高位置的每个堆栈，如果是这样，它会检查比较其中一个的最顶层堆栈帧是否也是比较另一个的最顶层堆栈帧。（这就是你想要的逻辑，对吧？Object[]
我能看到的唯一严重的错误是在这种情况下：
// a one-element array that directly contains itself:
final Object[] a = { null }; a[0] = a;
// a one-element array that contains itself via another one-element array:
final Object[][] b = { { null } }; b[0][0] = b;
// should return true (right?); instead, overflows the stack:
equal(a, b, new ArrayList<Object>(), new ArrayList<Object>());
您会看到，在上面，的最后一个元素将始终是 ，但 的最后一个元素将在 和 之间交替。在每个递归调用中， 将始终是 的最大索引，而 or（无论需要哪一个）将始终小于 的最大索引。xsaysbb[0]xs.lastIndexOf(a)xsys.lastIndexOf(b)ys.lastIndexOf(b[0])ys
问题是，逻辑不应该是，“最上面的比较与最上面的比较在同一个堆栈帧中”;相反，它应该是，“存在一些堆栈帧 - 任何堆栈帧 - 与”进行比较。但是为了提高效率，我们实际上可以使用逻辑“存在或曾经有过，一个堆栈帧正在/正在比较”;我们可以使用一对数组，而不是两个数组。为此，我写了这样的话：o1[i]o2[i]o1[i]o2[i]o1[i]o2[i]SetList
private static boolean equal(final Object[] a1, final Object[] a2)
{
return _equal(a1, a2, new HashSet<ArrayPair>());
}
private static boolean _equal
(final Object[] a1, final Object[] a2, final Set<ArrayPair> pairs)
{
if(a1 == a2)
return true;
if(a1.length != a2.length)
return false;
if(! pairs.add(new ArrayPair(a1, a2)))
{
// If we're here, then pairs already contained {a1,a2}. This means
// either that we've previously compared a1 and a2 and found them to
// be equal (in which case we obviously want to return true), or
// that we're currently comparing them somewhere higher in the
// stack and haven't *yet* found them to be unequal (in which case
// we still want to return true: if it turns out that they're
// unequal because of some later difference we haven't reached yet,
// that's fine, because the comparison higher in the stack will
// still find that).
return true;
}
for(int i = 0; i < a1.length; ++i)
{
if(a1[i] == a2[i])
continue;
if(a1[i] == null || a2[i] == null)
return false;
if(a1[i].equals(a2[i]))
continue;
if(! (a1[i] instanceof Object[]) || ! (a2[i] instanceof Object[]))
return false;
if(! _equal((Object[]) a1[i], (Object[]) a2[i], pairs))
return false;
}
return true;
}
private static final class ArrayPair
{
private final Object[] a1;
private final Object[] a2;
public ArrayPair(final Object[] a1, final Object[] a2)
{
if(a1 == null || a2 == null)
throw new NullPointerException();
this.a1 = a1;
this.a2 = a2;
}
@Override
public boolean equals(final Object that)
{
if(that instanceof ArrayPair)
if(a1 == ((ArrayPair)that).a1)
return a2 == ((ArrayPair)that).a2;
else
if(a1 == ((ArrayPair)that).a2)
return a2 == ((ArrayPair)that).a1;
else
return false;
else
return false;
}
@Override
public int hashCode()
{ return a1.hashCode() + a2.hashCode(); }
}
应该清楚的是，上述情况不能导致无限递归，因为如果程序具有有限数量的数组，那么它就具有有限数量的数组对，并且一次只有一个堆栈帧可以比较给定的数组对（因为，一旦一对开始被比较， 它被添加到 中，并且将来任何比较该货币对的尝试都将立即返回 ），这意味着在任何给定时间，总堆栈深度都是有限的。（当然，如果数组的数量很大，那么上面的数组仍然可以溢出堆栈;递归是有界的，但最大堆栈大小也是如此。实际上，我建议将 -loop 分成两个循环，一个接一个：第一次，跳过所有数组元素，第二次，跳过所有不是数组的元素。在许多情况下，这可以避免昂贵的比较。pairstrueforfor
还应该清楚的是，上述内容在应该返回时永远不会返回，因为它只有在发现实际差异时才返回。falsetruefalse
最后，我认为应该清楚的是，当它应该返回时，上述内容永远不会返回，因为对于每对对象，总是在所有元素上创建一个完整的循环。这部分更难证明，但从本质上讲，我们已经定义了结构相等，即如果我们能找到它们之间的一些差异，两个数组在结构上才不相等;上面的代码最终会检查它遇到的每个数组的每个元素，所以如果有一个可找到的差异，它就会找到它。truefalse
笔记：
- 我不担心基元数组，等等。亚当的回答提出了一种可能性，即你也希望这些元素进行比较。如果需要，可以很容易地添加它（因为它不需要递归：基元数组不能包含数组），但上面的代码只是使用它们，这意味着引用相等。
int[]double[]Object.equals(Object)
- 上面的代码假定实现对称关系，如其协定所指定。然而，在现实中，这种契约并非总是得到履行。相反，这种契约总是得到履行。例如，是 ，而 is 是 。如果顺序对你的目的很重要—— 如果你想成为和成为 - 那么你会想要改变，可能也要关心哪个数组是哪个。
Object.equals(Object)new java.util.Date(0L).equals(new java.sql.Timestamp(0L))truenew java.sql.Timestamp(0L).equals(new java.util.Date(0L))falseequal(new Object[]{java.util.Date(0L)}, new Object[]{java.sql.Timestamp(0L)})trueequal(new Object[]{java.sql.Timestamp(0L)}, new Object[]{java.util.Date(0L)})falseArrayPair.equals(Object)ArrayPair.hashCode()
