Java自定义集合的equals方法：深度比较与性能优化

@Override
public boolean equals(Object o) {
    // 1. 自反性：与自身比较，始终返回true
    if (o == this) {
        return true;
    }

    // 2. 与null比较，以及类型检查：如果o为null或不是Deque类型，则返回false
    // 注意：这里使用Deque<?>是为了更好地处理泛型，确保类型兼容性
    if (o == null || !(o instanceof Deque)) {
        return false;
    }

    // 3. 类型转换：将Object o转换为Deque类型
    Deque<?> otherDeque = (Deque<?>) o;

    // 4. 大小比较：如果两个Deque的大小不同，则它们不可能相等
    if (otherDeque.size() != this.size()) {
        return false;
    }

    // ... 接下来是元素逐一比较的逻辑
    return true; // 占位符，实际逻辑在此处实现
}

// 示例：使用get(index)进行比较（不推荐用于O(N)的get实现）
// ... (前置检查代码)
for (int i = 0; i < this.size(); i++) {
    Object element1 = this.get(i);
    Object element2 = otherDeque.get(i); // 如果otherDeque.get(i)是O(N)，则整体O(N^2)

    // 使用Objects.equals进行null安全比较
    if (!Objects.equals(element1, element2)) {
        return false;
    }
}
return true;

// 示例：使用迭代器进行比较（推荐）
// ... (前置检查代码)

// 获取两个Deque的迭代器
Iterator<T> thisIterator = this.iterator(); // 假设ArrayDeque实现了Iterable<T>
Iterator<?> otherIterator = otherDeque.iterator();

// 逐一比较元素，直到其中一个迭代器没有更多元素
while (thisIterator.hasNext() && otherIterator.hasNext()) {
    T element1 = thisIterator.next();
    Object element2 = otherIterator.next();

    // 使用Objects.equals进行null安全比较，并依赖元素自身的equals方法
    if (!Objects.equals(element1, element2)) {
        return false;
    }
}

// 由于之前已经检查了size是否相等，所以循环结束后，两个迭代器应该同时耗尽。
// 如果循环结束但其中一个还有元素（这在size检查后不应该发生），则表示逻辑错误。
return true;

import java.util.Iterator;
import java.util.Objects; // 引入Objects类，提供null-safe的equals方法

// 假设 Deque 接口和 ArrayDeque 类定义如下
interface Deque<T> extends Iterable<T> { // Deque接口应继承Iterable
    int size();
    // 其他 Deque 方法...
}

public class ArrayDeque<T> implements Deque<T> {
    private T[] ts;
    private int size;
    private int firposition; // 队列头部索引
    private int lastposition; // 队列尾部索引

    public ArrayDeque() {
        ts = (T[]) new Object[8];
        size = 0;
        firposition = ts.length / 2;
        lastposition = ts.length / 2;
    }

    // 假设get方法和iterator方法已正确实现
    public T get(int i) {
        if (i < 0 || i >= size) {
            return null; // 或者抛出IndexOutOfBoundsException
        }
        int actualIndex = (firposition + i) % ts.length;
        return ts[actualIndex];
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Iterator<T> iterator() {
        return new ArrayDequeIterator();
    }

    private class ArrayDequeIterator implements Iterator<T> {
        private int currentPosition = firposition;
        private int count = 0; // 记录已遍历的元素数量

        @Override
        public boolean hasNext() {
            return count < size;
        }

        @Override
        public T next() {
            if (!hasNext()) {
                throw new java.util.NoSuchElementException();
            }
            T item = ts[currentPosition];
            currentPosition = (currentPosition + 1) % ts.length;
            count++;
            return item;
        }
    }

    @Override
    public boolean equals(Object o) {
        // 1. 自反性
        if (o == this) {
            return true;
        }

        // 2. null检查和类型检查
        // 使用 instanceof 判断是否是 Deque 类型，而不是具体的 ArrayDeque 类型
        // 这样可以实现与 LinkedListArrayDeque 等其他 Deque 实现的比较
        if (o == null || !(o instanceof Deque)) {
            return false;
        }

        // 3. 类型转换
        // 使用 Deque<?> 来兼容不同泛型参数的 Deque 实例
        Deque<?> otherDeque = (Deque<?>) o;

        // 4. 大小比较
        if (otherDeque.size() != this.size()) {
            return false;
        }

        // 5. 元素逐一比较：使用迭代器提高性能
        Iterator<T> thisIterator = this.iterator();
        Iterator<?> otherIterator = otherDeque.iterator();

        while (thisIterator.hasNext()) { // 循环条件只需检查一个迭代器，因为大小已确定相等
            T element1 = thisIterator.next();
            Object element2 = otherIterator.next(); // otherDeque可能持有不同类型的元素

            // 使用 Objects.equals 进行 null-safe 比较
            // 这会调用 element1.equals(element2)，如果 element1 为 null 则直接返回 false
            if (!Objects.equals(element1, element2)) {
                return false;
            }
        }

        // 所有元素都相等，且大小相同
        return true;
    }
}