自定义Deque实现：ArrayDeque与LinkedListDeque的equals方法问题排查

我正在实现自定义Deque接口，除equals方法外其余功能均正常。提交代码到自动检查器时，相等性测试失败，提示**"元素相同的ArrayDeques和LinkedListDeques应相等"**，找不到问题所在。

LinkedListDeque的equals方法实现 #

/** Returns whether the parameter o is equal to the Deque.
 * o is considered equal if it is a Deque and if it contains
 * the same contents (as governed by the generic T's equals method) in the same order. */
 
@Override
public boolean equals(Object o) {
    if (o == null) {
        return false;
    }
    if (o == this) {
        return true;
    }
    if (!(o instanceof Deque)) {
        return false;
    }

    if (o instanceof LinkedListDeque) {
        LinkedListDeque<T> other = (LinkedListDeque<T>) o;
        if (this.size() != other.size()) {
            return false;
        }
        Iterator<T> dequeIt = this.iterator();
        Iterator<T> otherIt = other.iterator();
        while (dequeIt.hasNext()) {
            if (!dequeIt.next().equals(otherIt.next())) {
                return false;
            }
        }
        return true;
    } else if (o instanceof ArrayDeque) {
        ArrayDeque<T> other = (ArrayDeque<T>) o;
        if (this.size() != other.size()) {
            return false;
        }
        Iterator<T> thisIt = iterator();
        Iterator<T> otherIt = other.iterator();
        while (thisIt.hasNext()) {
            if (!thisIt.next().equals(otherIt.next())) {
                return false;
            }
        }
        return true;
    }
    return false;
}

ArrayDeque的equals方法实现 #

@Override
public boolean equals(Object o) {
    if (o == null) {
        return false;
    }
    if (this == o) {
        return true;
    }
    if (!(o instanceof Deque)) {
        return false;
    }
    if (o instanceof ArrayDeque) {
        ArrayDeque<T> other = (ArrayDeque<T>) o;
        if (other.size() != this.size) {
            return false;
        }
        Iterator<T> thisIt = iterator();
        Iterator<T> otherIterator = other.iterator();
        while (thisIt.hasNext()) {
            if (!thisIt.next().equals(otherIterator.next())) {
                return false;
            }
        }
        return true;
    } else if (o instanceof LinkedListDeque) {
        LinkedListDeque<T> other = (LinkedListDeque<T>) o;
        if (other.size() != this.size) {
            return false;
        }
        Iterator<T> thisIt = iterator();
        Iterator<T> otherIterator = other.iterator();
        while (thisIt.hasNext()) {
            if (!thisIt.next().equals(otherIterator.next())) {
                return false;
            }
        }
        return true;
    }
    return false;
}

我的单元测试（已通过） #

@Test
public void randomizedInsertionAndDeletion(){
    ArrayDeque<Integer> deque = new ArrayDeque<>();
    LinkedListDeque<Integer> deque2 = new LinkedListDeque<>();
    int N = 5000;
    for (int i =0; i<N; i++) {
        int operationNumber = StdRandom.uniform(0, 4);
        int randValue = StdRandom.uniform(0, 100);
        if (operationNumber == 0) {
            deque.addFirst(randValue);
            deque2.addFirst(randValue);
            assertEquals((Integer) randValue, deque.removeFirst());
            assertEquals((Integer) randValue, deque2.removeFirst());
        } else if (operationNumber == 1) {
            deque.addLast(randValue);
            deque2.addLast(randValue);
            assertEquals((Integer) randValue, deque.removeLast());
            assertEquals((Integer) randValue, deque2.removeLast());
        } else if (operationNumber == 2) {
            assertEquals(deque.get(0), deque.removeFirst());
            assertEquals(deque2.get(0), deque.removeFirst());
        } else if (operationNumber == 3) {
            assertEquals(deque.removeLast(), deque.get(deque.size()));
        } else if (operationNumber == 4) {
            boolean actual1 = deque.equals(deque2);
            boolean actual2 = deque2.equals(deque);
            assertEquals(true, actual1);
            assertEquals(true, actual2);
        }
    }
}

@Test
public void equals() {
    ArrayDeque<Boolean> deque = new ArrayDeque<>();
    deque.addLast(true);
    deque.addFirst(false);
    deque.addFirst(false);
    deque.addFirst(true);

    LinkedListDeque<Boolean> deque2 = new LinkedListDeque<>();
    deque2.addLast(true);
    deque2.addFirst(false);
    deque2.addFirst(false);
    deque2.addFirst(false);

    assertEquals(false, deque2.equals(deque));
    assertEquals(false, deque.equals(deque2));
}

问题分析与修复方案 #

问题出在ArrayDeque的equals方法中直接访问了size成员变量，而不是调用size()方法。LinkedListDeque的equals里用的是this.size()，而ArrayDeque里用的是this.size，如果你的ArrayDeque中size成员变量没有在add/remove操作时正确同步更新（比如size()方法是通过计算数组头尾指针得到实际大小，而非直接返回size成员变量），就会导致size比较错误，即使元素完全一致也会返回false。

修改ArrayDeque的equals方法，将所有this.size替换为this.size()：

// 第一处修改
if (other.size() != this.size()) {
    return false;
}

// 第二处修改
if (other.size() != this.size()) {
    return false;
}

这样就能保证size比较的是实际元素数量，和LinkedListDeque的逻辑保持一致，通过相等性测试。

内容的提问来源于stack exchange，提问作者bobcob