cs61b week5 -- Object Methods

(在2020后的版本把2018写的ArrayMap改成了ArraySet,因此下面的案例基于ArraySet)
所有的类都隐式地继承了Object,且包含Object的以下方法:

  • String toString()
  • boolean equals(Object obj)
  • Class getClass()
  • int hashCode()
  • protected Objectclone()
  • protected void finalize()
  • void notify()
  • void notifyAll()
  • void wait()
  • void wait(long timeout)
  • void wait(long timeout, int nanos)

本次课我们重点介绍前两个方法

1.toString()

当你每次调用System.out.println(x)时,无论x原本的类型是什么,都会发生隐式地转换,System.out.println(Object x) calls x.toString()
(If you’re curious: println calls String.valueOf which calls toString)

String x = x.toString();
System.out.println(x);

默认的Object的toString()方法转换的格式为:

classname @ hex_memory
类名@十六进制内存地址

因此如果打印我们自己写的ArraySet,其结果是:

$ java ArraySetPrintDemo
ArraySet@75412c2f

但是Java.util内置的List,Set,Map均Override了Object原来的toString()方法,因此如果我们使用内置的List:

    public static void main(String[] args ) {
        List a = new ArrayList<>();
        a.add(1);
        a.add(2);
        a.add(3);
        System.out.println(a);
    }

就会打印出赏心悦目的结果:

[1, 2, 3]

我们的目标是,让我们自己写的ArraySet也打印出这种漂亮的结果,也就是我们需要Override原本的toString()
先回顾一下我们的ArraySet:

public class ArraySet implements Iterable {
    private T[] items;
    private int size; // the next item to be added will be at position size

    public ArraySet() {
        items = (T[]) new Object[100];
        size = 0;
    }

    /* Returns true if this map contains a mapping for the specified key.
     */
    public boolean contains(T x) {
        for (int i = 0; i < size; i += 1) {
            if (items[i].equals(x)) {
                return true;
            }
        }
        return false;
    }

    /* Associates the specified value with the specified key in this map.
       Throws an IllegalArgumentException if the key is null. */
    public void add(T x) {
        if (x == null) {
            throw new IllegalArgumentException("can't add null");
        }
        if (contains(x)) {
            return;
        }
        items[size] = x;
        size += 1;
    }

    /* Returns the number of key-value mappings in this map. */
    public int size() {
        return size;
    }
    

    @Override
    public String toString() {
        /* hmmm */
    }


    @Override
    public boolean equals(Object other) {
        /* hmmm */
    }

    public static void main(String[] args) {
        ArraySet aset = new ArraySet<>();
        aset.add(5);
        aset.add(23);
        aset.add(42);
        
        //toString
        System.out.println(aset);
        
    }

解决方案:

@Override
public String toString() {
    String returnString = "{";
    for (int i = 0; i < size; i += 1) {
        returnString += keys[i];
        returnString += ", ";
    }
    returnString += "}";
    return returnString;
}

这样的toString()虽然能实现我们的目标,但是效率上非常低,这是因为Java中,String是不变量(还记得不变量吗?回顾一下以前的笔记),因此当每次执行字符串拼接时:

returnString += keys[i];

Java都是从头创建一个新的副本,然后再将字符拼接,最后返回该副本,因此,假设拼接一个字符需要1s,对字符串"{ 1 2 3 }"进行拼接,则需要

  • { (1s)
  • { + 1 = { 1 (2s)
  • { + 1 + 2 = { 1 2 (3s)
  • { + 1 + 2 + 3 = {1 2 3 (4s)
  • { + 1 + 3 + } = {1 2 3} (5s)

可见每次拼接都是从头开始,上述过程的总耗时为1 + 2 + 3 + 4 + 5 = 15s
如果一个字符串的长度为n,则以上面的算法拼接字符串的时间复杂度是 O(1 + 2 + 3 + 4 +......+ n-1 + n) = O(n(n-1)/2),即O(n²)
如何让字符串拼接变得更加高效?

为了解决这个问题,Java 有一个特殊的类,称为StringBuilder. 它创建一个可变的字符串对象,因此您可以继续追加到同一个字符串对象上,而不是每次都创建一个新对象。
使用StringBuilder重写toString()方法:

public String toString() {
        StringBuilder returnSB = new StringBuilder("{");
        for (int i = 0; i < size - 1; i += 1) {
            returnSB.append(items[i].toString());
            returnSB.append(", ");
        }
        returnSB.append(items[size - 1]);
        returnSB.append("}");
        return returnSB.toString();
    }

此算法的时间复杂度是线性的,O(n)


2.equals() vs. ==

前面我们有提到 Object.equals(Object o)方法是比较两个Object的值,而Java中 == 则是比较二者的内存地址是否相同,或者说是否指向同一Object
举例:

cs61b week5 -- Object Methods_第1张图片

cs61b week5 -- Object Methods_第2张图片
因此以后如果要比较两个Object通常意义下的相等,请使用.equals()
但是事实上,Java的Object.equals()方法默认是与 == 等效的,在内置的Java.util 的Set,Map,List均Override了原本的equals(),因此我们使用起来才没问题
如果我们原封不动地使用默认的equals()方法,同样会相当于使用 == 判断两个内存地址不同的Object,从而返回false:
cs61b week5 -- Object Methods_第3张图片

因此我们的目标是Override默认的equals()方法,使之适用于我们的ArraySet
请注意 List是有序元素集合,Set是无序元素集合。因此,如果我们需要重写自定义的ArrayList的equals(),需要逐项比较两个List中的元素是否顺序相同且元素值相等
而Set是唯一元素的无序集合。因此,要将两个集合视为相等,您只需要检查它们之间是否相互包含相同的元素。
解决方案:

@Override
public boolean equals(Object other) {
        if (this == other) {
            return true;
        }
        if (other == null) {
            return false;
        }
        if (other.getClass() != this.getClass()) {
            return false;
        }
        ArraySet o = (ArraySet) other;
        if (o.size() != this.size()) {
            return false;
        }
        for (T item : this) {
            if (!o.contains(item)) {
                return false;
            }
        }
        return true;
    }

getClass()方法是返回当前Object的class type,例如this.getClass() = ArraySet.class
总结:
cs61b week5 -- Object Methods_第4张图片


3.Even Better toString() and ArraySet.of()

String.join()

实现字符串拼接还有一种方法,使用String.join()
cs61b week5 -- Object Methods_第5张图片

@Override
public String toString() {
    List lisOfItems = new ArrayList<>();
    for(T x : this) {
        lisOfItems.add(x.toString());
    }
    return "{" + String.join(",", lisOfItems) + "}";
}

.Of()

回忆一下以前做过的lab,我们以 .Of()方式创建一个List,或者Set,例如:

Set javaset = Set.of(5, 23, 42);

就能创建一个Set,其内容为{5,23,42},非常的方便
因此,我们想实现属于自己的.Of()方法,使之能够达到上面的效果
解决方案:

public static  ArraySet of(Glerp... stuff) {
    ArraySet returnSet = new ArraySet<>();
    for (Glerp x : stuff) {
        returnSet.add(x);
    }
    return returnSet;
}

语法点:

  • 泛型方法,在方法返回类型前加,前面笔记有介绍
  • Varargs: ... 可变长度参数

在 Java 5 中提供了变长参数,允许在调用方法时传入不定长度的参数。变长参数是 Java 的一个语法糖,本质上还是基于数组的实现,Java的可变参数,会被编译器转型为一个数组

void foo(String... args);
void foo(String[] args);

更多可见this link

你可能感兴趣的