Project 1: Data Structures

类值的相等判断永远用.equals()而不是==

花了近两天的时间终于是把Probject 1 完成了，完成了LinkedListDeque和ArrayDeque两种实现的Deque。在此就不再赘述数据结构的实现方法，代码地址

那么我要写一些什么呢？写一些我遇到的问题和bug。

这个bug实在是令人火大，这本是不应该出现的错误

正如二级标题所说的，类值的相等判断永远用.equals()而不是==。而且值得铭记的是，测试文件一定要扩大数据规模，因为扩大规模真的会发现意想不到的错误。

事情的起因是public boolean equals(Object o)这个函数，对于一个自己实现的数据类，这个方法是很有Override的必要的。因为两种数据类基本一样，这里我只用LinkedListDeque举例。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* check if two deques are equal
*
* @param o
* @return true if they are equal, false otherwise
*/
@Override
public boolean equals(Object o) {
    if (o == null) {
        return false;
    }
    if (!(o instanceof Deque)) {
        return false;
    } else {
        Deque<?> other = (Deque<?>) o;
        if (this.size() != other.size()) {
            return false;
        }
        for (int i = 0; i < this.size(); i++) {
            if (this.get(i)!=other.get(i)) {
                return false;
            }
        }
        return true;
    }
}

上面代码是有bug的，我写的时候这种是真的很难注意到。你有可能也没有注意到，接下来是get()函数的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param index
* @return the item at the given index, if no such item exists, return null
*/
@Override
public T get(int index) {
    if (index >= this.size) {
        return null;
    }
    Node current = sentinal.next;
    for (int i = 0; i < index; i++) {
        current = current.next;
    }
    return current.data;
}

到这里其实就已经能看清楚问题所在了，get()函数返回的是类型T，是任意封装类，并不是基础数据类型。众所周知Java在比对类是否相等时，==操作符默认是比对类的地址是否一致，也就是看对方是否是自己。显然我们并不想这么做，我们需要比对的是内部存储的值是否相等。就像十张百元钞票和另外十张百元钞票，都是一千元，代表的价值是相同的，而不是因为钞票编号不同所以表示这两堆钞票是不相等的。

相信学习过CS61B课程的同学都已经有了写测试代码的好习惯。我也是如此，但是很遗憾的是尽管我写了junit测试，也并没有查出来这个bug。以下是我一开始写的测试代码：

1
2
3
4
5
6
7
8
9
10
@Test
public void testEquals() {
    LinkedListDeque<Integer> lld1 = new LinkedListDeque<>();
    LinkedListDeque<Integer> lld2 = new LinkedListDeque<>();
    assertTrue(lld1.equals(lld2));
    lld1.addFirst(1);
    assertFalse(lld1.equals(lld2));
    lld2.addFirst(1);
    assertTrue(lld1.equals(lld2));
}

是的，测试很容易的通过了。这是为什么呢？这里就要引入大名鼎鼎的IntegerCache了。

IntegerCache是Java中的一个类，它是用于缓存Integer对象的一个内部类。在Java中，由于Integer是不可变对象，一些整数值在一定范围内是经常使用的，为了提高性能和节省内存，Java使用了IntegerCache来缓存一些常用的整数对象。
在Java中，对于数值在[-128, 127]范围内的Integer对象，如果通过自动装箱的方式创建，会直接使用IntegerCache中已经存在的对象，而不是每次创建新的对象。这样做可以避免频繁创建新的Integer对象，提高了性能和节省了内存。
例如，当你通过Integer.valueOf()方法创建一个整数值在[-128, 127]范围内的Integer对象时，如果该值在IntegerCache中已经存在，则直接返回缓存中的对象，而不会创建新的对象。
但是需要注意的是，这种缓存机制只适用于整数值在[-128, 127]范围内的情况，超出这个范围的整数值仍然会创建新的Integer对象。

因为IntegerCache的原因，虽然我向两个Deque分别塞入了Ingeter 1，但是实际上这两个1地址是一样的，编号一样的钞票真的不是假钞吗😂

所以正确的测试应该扩大数据规模：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@Test
public void testEquals() {
    LinkedListDeque<Integer> lld1 = new LinkedListDeque<>();
    LinkedListDeque<Integer> lld2 = new LinkedListDeque<>();
    assertTrue(lld1.equals(lld2));
    lld1.addFirst(1);
    assertFalse(lld1.equals(lld2));
    lld2.addFirst(1);
    assertTrue(lld1.equals(lld2));
    for (int i = 1; i <= 1000; i++) {
        lld1.addFirst(i);
        lld2.addFirst(i);
    }
    assertTrue(lld1.equals(lld2));
}

这样因为数据超过了128，显然以前的代码是无法通过这个代码的。在这里贴出修改后正确的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
@Override
public boolean equals(Object o) {
    if (o == null) {
        return false;
    }
    if (!(o instanceof Deque)) {
        return false;
    } else {
        Deque<?> other = (Deque<?>) o;
        if (this.size() != other.size()) {
            return false;
        }
        for (int i = 0; i < this.size(); i++) {
            Object a = this.get(i);
            Object b = other.get(i);
            if (!a.equals(b)) {
                return false;
            }
        }
        return true;
    }
}

直接调用T本身的equals()方法即可，这样即使还是通不过测试的话那也不是咱们代码的错了。

style 问题

这个Project 1还挺有意思的，实现完数据类后还要用自己写的数据类去弹吉他。但是在此项目中，code 的 style 有严格的要求，第一次交代码的时候一共 640 points 因为 style 没有按照要求竟然扣了大约 84 points，。。。。
但是大可不必阅读那长长的 style 要求，只需要把 IDEA 的自动格式化代码打开即可。具体位置是Settings -> Tools -> Actions on Save -> Reformat code。