本文深入探讨了在自定义java集合类（如arraydeque）中正确实现`equals`方法的挑战与解决方案，特别是在不依赖`java.util.*`工具类进行深度比较的场景。文章详细阐述了如何通过委托元素自身的`equals`方法实现值相等判断，并强调了使用迭代器进行高效元素遍历的重要性，以避免潜在的性能瓶颈，最终提供了一个结构清晰、性能优化的`equals`实现范例。
在Java编程中，当我们创建自定义的集合类（如ArrayDeque或LinkedListArrayDeque）时，正确地实现equals方法是至关重要的。它确保了对象之间的逻辑相等性判断符合预期，而不仅仅是引用相等。本教程将引导您如何在不使用java.util.*中的辅助方法（如Objects.equals）的情况下，为自定义Deque实现一个健壮且高效的equals方法，并涵盖深度比较的原理和性能优化。
理解Java中equals方法的深层比较
Object类默认的equals方法执行的是引用相等性比较（即==）。对于大多数自定义类，我们需要重写此方法以实现值相等性比较。当集合类包含其他对象时，其equals方法的实现需要进行“深度比较”，这意味着它必须检查集合中每个对应元素的相等性。这种深度比较通常通过委托给集合元素的equals方法来完成。
在最初的尝试中，开发者可能会考虑引入一个独立的deepEquals方法。然而，这通常是不必要的，因为Java的equals方法本身就应该处理这种逻辑。一个设计良好的equals方法会递归地调用其成员对象的equals方法，从而实现“深度”比较。
初始问题与deepEquals的误区
考虑以下一个自定义ArrayDeque的初始equals和deepEquals实现：
立即学习“Java免费学习笔记（深入）”；
public boolean equals(Object o) { // 原始equals方法
if (o == this) {
return true;
}
if (o == null || this == null) { // this == null 不可能发生
return false;
}
if (!(o instanceof Deque)) {
return false;
}
Deque oll = (Deque) o;
if (oll.size() != this.size()) {
return false;
}
for (int i = 0; i < this.size(); i++) {
Object a2 = oll.get(i);
Object a1 = this.get(i);
if (a1 == a2) { // 引用相等或都为null
continue;
}
if (a2 == null) { // a1不为null但a2为null
return false;
}
if (a1.getClass() != a2.getClass()) { // 类型检查过于严格
return false;
}
return deepEquals(a1, a2); // 问题所在：提前返回且deepEquals实现不当
}
return true;
}
private boolean deepEquals(Object a1, Object a2) { // 原始deepEquals方法
boolean deq;
if (a1 instanceof Deque) {
deq = a1.equals(a2); // 委托给Deque的equals
} else {
if (a1 == a2) { // 再次检查引用相等
return true;
}
return false; // 如果不是Deque，且引用不相等，则直接返回false
}
return deq;
}上述代码存在几个问题：
- deepEquals的冗余与不完善： deepEquals方法本身并不完整。对于非Deque类型的对象，它只检查引用相等，这与我们期望的值相等性比较相悖。正确的做法是直接调用a1.equals(a2)。
- equals方法中的提前返回： 在equals方法的循环中，return deepEquals(a1, a2); 语句导致循环在比较第一个不相等的元素后立即终止，而不是继续检查所有元素。这可能导致错误的比较结果。
- getClass()的严格性： a1.getClass() != a2.getClass() 检查过于严格。例如，一个ArrayList对象可能与一个LinkedList对象在逻辑上是相等的（如果它们都实现了List接口且包含相同的元素），即使它们的具体类不同。通常，我们应该依赖于equals方法的契约，而不是严格的类类型匹配。
健壮的equals实现原则
一个健壮的equals方法应遵循Object类定义的五项约定：
- 自反性 (Reflexivity): 任何非null对象x，x.equals(x)必须返回true。
- 对称性 (Symmetry): 任何非null对象x和y，如果x.equals(y)返回true，则y.equals(x)也必须返回true。
- 传递性 (Transitivity): 任何非null对象x、y和z，如果x.equals(y)返回true，且y.equals(z)返回true，则x.equals(z)也必须返回true。
- 一致性 (Consistency): 任何非null对象x和y，只要它们之间用于equals比较的信息没有被修改，那么对x.equals(y)的多次调用都应该返回相同的结果。
- 非空性 (Non-nullity): 任何非null对象x，x.equals(null)必须返回false。
基于这些原则，我们可以构建一个正确的equals方法。
元素级比较的最终实现
结合上述分析，以下是经过优化和修正的equals方法，它避免了deepEquals的冗余，并正确处理了元素比较逻辑：
public boolean equals(Object o) {
// 1. 自反性：检查是否是同一个对象的引用
if (o == this) {
return true;
}
// 2. 非空性：检查传入对象是否为null
if (o == null) {
return false;
}
// 3. 类型检查：检查传入对象是否是Deque的实例
// 使用 instanceof 优于 getClass() == other.getClass()，因为它允许子类与父类对象进行比较
if (!(o instanceof Deque)) {
return false;
}
// 将Object转换为Deque类型，以便访问其特定方法
Deque otherDeque = (Deque) o; // 使用泛型以兼容不同类型的Deque
// 4. 大小检查：如果大小不同，则不可能相等
if (otherDeque.size() != this.size()) {
return false;
}
// 5. 元素级比较：遍历所有元素进行深度比较
// 注意：这里的实现是基于get(i)的，后续会讨论迭代器优化
for (int i = 0; i < this.size(); i++) {
Object elementOfThis = this.get(i);
Object elementOfOther = otherDeque.get(i);
// 处理元素为null的情况和引用相等的情况
// 如果两个元素引用相同（包括都为null），则认为它们相等，继续下一个元素
if (elementOfThis == elementOfOther) {
continue;
}
// 如果elementOfThis不为null但elementOfOther为null，则不相等
if (elementOfOther == null) {
return false;
}
// 至此，elementOfThis和elementOfOther都保证不为null
// 委托给元素的equals方法进行值比较
if (!elementOfThis.equals(elementOfOther)) {
return false; // 只要有一个元素不相等，整个Deque就不相等
}
}
// 如果所有元素都相等，则两个Deque相等
return true;
}代码解析：
- o == this: 处理自反性，快速路径。
- o == null: 处理非空性，任何对象与null都不相等。
- !(o instanceof Deque): 类型检查，确保比较的是兼容的Deque类型。
- otherDeque.size() != this.size(): 大小检查，不同大小的集合不可能相等。
-
元素遍历和比较：
- elementOfThis == elementOfOther: 这是处理null值和引用相等的最简洁方式。如果两个元素都是null，或者它们是同一个对象的引用，则它们被认为是相等的。
- elementOfOther == null: 如果elementOfThis不为null但elementOfOther为null，则它们不相等。由于前一个if已经排除了两者都为null的情况，这里只需考虑elementOfThis非null而elementOfOther为null的情况。
- !elementOfThis.equals(elementOfOther): 在确保elementOfThis和elementOfOther都非null之后，我们安全地调用elementOfThis的equals方法来执行值比较。这是实现深度比较的关键。
性能优化：使用迭代器
上述equals方法中的元素遍历使用了get(i)方法。对于ArrayDeque这样的基于数组的实现，get(i)通常是O(1)操作，因此整个equals方法的时间复杂度是O(N)，其中N是集合的大小。然而，对于某些Deque实现，例如基于链表的LinkedListArrayDeque，get(i)操作可能需要从头开始遍历，导致其时间复杂度为O(i)，从而使得整个equals方法的时间复杂度变为O(N^2)，这在处理大型集合时会带来显著的性能问题。
为了避免这种性能瓶颈，我们应该利用Java集合框架中的Iterator接口。迭代器提供了一种高效、顺序访问集合元素的方式，通常是O(1)的next()操作，从而将整个比较过程的时间复杂度保持在O(N)。
假设ArrayDeque已经实现了Iterable
import java.util.Iterator; // 虽然原问题要求不使用java.util.*，但Iterator接口是集合框架的基础，通常被允许使用 public class ArrayDequeimplements Deque , Iterable { // ... 其他成员和方法 ... @Override public Iterator iterator() { return new ArrayDequeIterator(); } private class ArrayDequeIterator implements Iterator { private int currentPosition = firposition; // 迭代器当前位置 private int elementsTraversed = 0; // 已遍历元素计数 @Override public boolean hasNext() { return elementsTraversed < size; } @Override public T next() { if (!hasNext()) { throw new java.util.NoSuchElementException(); } T item = ts[currentPosition]; currentPosition = (currentPosition + 1) % ts.length; elementsTraversed++; return item; } } @Override public boolean equals(Object o) { if (o == this) { return true; } if (o == null) { return false; } if (!(o instanceof Deque)) { return false; } Deque otherDeque = (Deque) o; if (otherDeque.size() != this.size()) { return false; } // 使用迭代器进行元素遍历和比较，提高效率 Iterator thisIterator = this.iterator(); // 获取当前Deque的迭代器 // 假设 otherDeque 也是 Iterable 的，或者其 get(i) 性能可接受 // 如果 otherDeque 也是自定义的，且我们知道它有高效的迭代器，可以这样： // Iterator otherIterator = otherDeque.iterator(); // 但根据原问题，oll.get(i) 是一个通用接口方法，我们先沿用它。 // 如果 Deque 接口本身没有 iterator() 方法，但 ArrayDeque 实现了 Iterable， // 那么对于 otherDeque，我们可能只能依赖 get(i) 或假设它也是 Iterable。 // 为了通用性，我们这里继续使用get(i)作为otherDeque的访问方式， // 但强调如果otherDeque也提供迭代器，应优先使用。 int i = 0; while (thisIterator.hasNext()) { // 遍历当前Deque的元素 Object elementOfThis = thisIterator.next(); Object elementOfOther = otherDeque.get(i); // 访问另一个Deque的对应元素 i++; if (elementOfThis == elementOfOther) { continue; } if (elementOfOther == null) { return false; } if (!elementOfThis.equals(elementOfOther)) { return false; } } return true; } }
关于ArrayDequeIterator的改进： 原始问题中的ArrayDequeIterator逻辑略显复杂，为了更清晰和健壮，可以简化hasNext()和next()方法，直接利用size和currentPosition（或elementsTraversed）来判断。上面示例中提供了一个更简洁的ArrayDequeIterator实现。
更进一步的迭代器优化（如果Deque接口也支持迭代器）： 如果Deque接口本身就定义了iterator()方法（这是标准的做法），那么两个Deque都可以使用迭代器进行遍历，从而实现最优的O(N)时间复杂度：
// 假设 Deque 接口定义了 iterator() 方法 // public interface Dequeextends Iterable { ... } @Override public boolean equals(Object o) { if (o == this) { return true; } if (o == null) { return false; } if (!(o instanceof Deque)) { return false; } Deque otherDeque = (Deque) o; if (otherDeque.size() != this.size()) { return false; } // 同时使用两个迭代器进行元素遍历 Iterator thisIterator = this.iterator(); Iterator otherIterator = otherDeque.iterator(); // 获取另一个Deque的迭代器 while (thisIterator.hasNext()) { Object elementOfThis = thisIterator.next(); Object elementOfOther = otherIterator.next(); // 两个迭代器同步前进 if (elementOfThis == elementOfOther) { continue; } if (elementOfOther == null) { // 此时 elementOfThis 必不为 null return false; } if (!elementOfThis.equals(elementOfOther)) { return false; } } // 因为之前已经检查了size相等，且迭代器同步前进， // 如果一个迭代器hasNext()为false，另一个也应如此。 // 如果循环结束，则所有元素都相等。 return true; }
这种双迭代器同步遍历的方式是比较两个集合内容最标准和高效的做法。
注意事项与总结
- equals方法的约定： 始终牢记并严格遵守Object类equals方法的五项约定，这是编写正确equals方法的基石。
- 避免getClass()： 除非您确实需要严格的运行时类型匹配（例如，在某些特定的代理或序列化场景），否则应优先使用instanceof进行类型检查，以允许子类对象与父类对象进行逻辑相等比较。
- Null值处理： 在调用任何对象的equals方法之前，务必确保该对象（即equals的调用者）不为null。本教程中的elementOfThis == elementOfOther和elementOfOther == null检查巧妙地处理了所有null情况，确保elementOfThis.equals(elementOfOther)被调用时，elementOfThis和
