cs61b week5 -- Object Methods java

(在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 sizepublic 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); }

【cs61b week5 -- Object Methods】解决方案:

@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(n2)
如何让字符串拼接变得更加高效？
为了解决这个问题，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
举例:

文章图片

文章图片

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

文章图片

因此我们的目标是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
总结:

文章图片

3.Even Better toString() and ArraySet.of()
String.join() 实现字符串拼接还有一种方法，使用String.join()

文章图片

@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，例如: