【UCB CS 61B SP24】Lecture 11 - Inheritance 4: Iterators, Object Methods学习笔记

本文内容为集合（Set）的介绍与使用，并通过数组手动实现集合，接着介绍了迭代器，使用迭代器我们能够更方便地遍历集合中的元素。

1. Set

1.1 Set介绍与Java实现类的使用

集合（Set）是一种常见的数据结构，用于存储一组唯一的、不重复的元素。集合的核心特点是不允许重复元素，并且通常不保证元素的顺序。其核心特性如下：

唯一性：集合中的元素是唯一的，不允许重复。如果尝试添加一个已经存在的元素，集合不会发生改变。
无序性：集合通常不保证元素的顺序（除非使用有序集合实现，如 Java 中的 TreeSet 或 LinkedHashSet）。
动态性：集合的大小可以动态调整，支持添加、删除和查找操作。
高效性：集合的实现通常基于哈希表或平衡树，因此添加、删除和查找操作的时间复杂度通常为 $O (1)$ 或 $O (l o g n)$ 。

在 Java 中，Set 是一个不包含重复元素的集合接口。它是 java.util 包的一部分，继承自 Collection 接口。Java 已经默认提供了多个 Set 的实现类，常用的有：

（1）HashSet

基于哈希表实现，不保证元素的顺序，允许有 null 元素，插入、删除和查找操作的时间复杂度为 $O (1)$ ，在 java.util.HashSet 包中：

Set<String> hashSet = new HashSet<>();
hashSet.add("Apple");
hashSet.add("Banana");
hashSet.add("Cherry");
System.out.println(hashSet);  // 输出可能是[Apple, Cherry, Banana]，不保证顺序

（2）LinkedHashSet

继承自 HashSet，基于哈希表和链表实现，能够维护元素的插入顺序，允许有 null 元素，插入、删除和查找操作的时间复杂度为 $O (1)$ ，在 java.util.LinkedHashSet 包中：

Set<String> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add("Apple");
linkedHashSet.add("Banana");
linkedHashSet.add("Cherry");
System.out.println(linkedHashSet);  // 输出一定是[Apple, Banana, Cherry]

（3）TreeSet

基于红黑树实现，元素按照自然顺序或指定的比较器进行排序，不允许有 null 元素，插入、删除和查找操作的时间复杂度为 $O (l o g n)$ ，在 java.util.TreeSet 包中：

Set<String> treeSet = new TreeSet<>();
treeSet.add("Cherry");
treeSet.add("Banana");
treeSet.add("Apple");
System.out.println(treeSet);  // [Apple, Banana, Cherry]

Set 接口继承了 Collection 接口的所有方法，以下是一些常用的方法：

add(T item)：将指定的元素添加到集合中（如果尚未存在）。
remove(T item)：从集合中移除指定的元素（如果存在）。
contains(T item)：判断集合中是否包含指定的元素。
size()：返回集合中的元素数量。
isEmpty()：判断集合是否为空。
clear()：移除集合中的所有元素。
iterator()：返回一个迭代器，用于遍历集合中的元素。

package CS61B.Lecture11;import java.util.HashSet;
import java.util.Set;public class SetExample {public static void main(String[] args) {Set<String> fruits = new HashSet<>();fruits.add("Apple");fruits.add("Banana");fruits.add("Cherry");// 尝试添加重复元素boolean isAdded = fruits.add("Apple");System.out.println(isAdded);  // false// 遍历集合for (String fruit : fruits)System.out.println(fruit);// 检查元素是否存在System.out.println(fruits.contains("Banana"));  // true// 移除元素fruits.remove("Cherry");System.out.println(fruits);  // [Apple, Banana]}
}

1.2 手动实现ArraySet

现在我们尝试用数组自己实现一个集合，代码类似之前实现的 AList：

package CS61B.Lecture11;public class ArraySet<T> {private T[] items;private int size;private int capacity;private void expandCapacity() {this.capacity *= 2;T[] newItems = (T[]) new Object[this.capacity];System.arraycopy(this.items, 0, newItems, 0, this.size);this.items = newItems;}public ArraySet() {this.capacity = 2;this.items = (T[]) new Object[this.capacity];this.size = 0;}public int size() {return this.size;}public boolean contains(T item) {for (int i = 0; i < this.size; i++)if (this.items[i].equals(item)) return true;return false;}public void add(T item) {if (this.contains(item)) return;if (this.size == this.capacity) this.expandCapacity();this.items[this.size++] = item;}public static void main(String[] args) {ArraySet<String> fruits = new ArraySet<>();fruits.add("Apple");fruits.add("Banana");fruits.add("Cherry");fruits.add("Apple");System.out.println(fruits.size());  // 3}
}

2. 迭代器

2.1 增强型For循环

在前面使用 Java 的 Set 实现类的例子中我们用的遍历方法是这样的：

for (String fruit : fruits)

这被称为增强型 For 循环，我们手动实现的 ArraySet 并不能这样遍历，这是怎么实现的？其实这种循环是由以下代码组成的：

Iterator<String> it = fruits.iterator();
while (it.hasNext()) {String fruit = it.next();// Do something ...
}

2.2 Iterator & Iterable

上面这段代码中的 Iterator 称为迭代器，在 java.util.Iterator 中定义，是一个用于遍历集合（如 List、Set、Map 等）中元素的接口，它提供了两个核心方法：hasNext() 和 next()。

boolean hasNext()：检查集合中是否还有更多的元素可以遍历。若集合中还有未遍历的元素则返回 true，已经遍历完所有元素则返回 false。
T next()：返回集合中的下一个元素，每次调用 next() 都会自动将迭代器的指针移动到下一个元素。如果集合中没有更多的元素（即 hasNext() 返回 false），调用 next() 会抛出 NoSuchElementException 异常。因此在调用 next() 之前，通常需要先调用 hasNext() 进行检查。

因此我们的 ArraySet 中必须能够通过 iterator() 方法创建并返回一个自己的 Iterator 对象，并且这个对象具有 hasNext() 和 next() 方法，此外还需要让我们的 ArraySet 实现 Iterable 接口（该接口具有 forEach() 方法），这样才能让 Java 知道我们这个类的对象是可以用迭代器遍历的：

package CS61B.Lecture11;import org.jetbrains.annotations.NotNull;import java.util.Iterator;public class ArraySet<T> implements Iterable<T> {private T[] items;private int size;private int capacity;private void expandCapacity() {this.capacity *= 2;T[] newItems = (T[]) new Object[this.capacity];System.arraycopy(this.items, 0, newItems, 0, this.size);this.items = newItems;}public ArraySet() {this.capacity = 2;this.items = (T[]) new Object[this.capacity];this.size = 0;}public int size() {return this.size;}public boolean contains(T item) {for (int i = 0; i < this.size; i++)if (this.items[i].equals(item)) return true;return false;}public void add(T item) {if (this.contains(item)) return;if (this.size == this.capacity) this.expandCapacity();this.items[this.size++] = item;}private class ArraySetIterator implements Iterator<T> {private int pos;public ArraySetIterator() {this.pos = 0;}@Overridepublic boolean hasNext() {return this.pos < size;}@Overridepublic T next() {T item = items[this.pos];this.pos++;return item;}}public @NotNull Iterator<T> iterator() {return new ArraySetIterator();}public static void main(String[] args) {ArraySet<String> fruits = new ArraySet<>();fruits.add("Apple");fruits.add("Banana");fruits.add("Cherry");fruits.add("Apple");System.out.println(fruits.size());  // 3for (String fruit : fruits)System.out.print(fruit + " ");  // Apple Banana Cherry}
}

3. 优化ArraySet

3.1 toString()

toString() 方法在之前的例子中我们已经重写过了，该方法提供对象的字符串表示形式，当我们要输出某个对象时 System.out.println(Object obj)，这时会调用 obj.toString() 方法，如果没有重写这个方法那么默认返回的是 类名@地址 的形式。现在我们再重写一遍 toString()：

package CS61B.Lecture11;import org.jetbrains.annotations.NotNull;import java.util.Iterator;public class ArraySet<T> implements Iterable<T> {...@Overridepublic String toString() {StringBuilder sb = new StringBuilder("[");for (T item : this) sb.append(item + ", ");if (sb.length() > 1) sb.delete(sb.length() - 2, sb.length());sb.append("]");return sb.toString();}public static void main(String[] args) {ArraySet<String> fruits = new ArraySet<>();fruits.add("Apple");fruits.add("Banana");fruits.add("Cherry");fruits.add("Apple");System.out.println(fruits.size());  // 3System.out.println(fruits);  // [Apple, Banana, Cherry]}
}

3.2 equals()

Java 中的 == 是按比特位比较两个变量的数值，而不会比较两个地址所分别指向的两个对象中的内容是否相等，先看下面这段代码：

package CS61B.Lecture11;import java.util.ArrayList;
import java.util.Arrays;public class EqualsExample {public static void main(String[] args) {ArrayList<Integer> l1 = new ArrayList<>(Arrays.asList(1, 2, 3));ArrayList<Integer> l2 = new ArrayList<>(Arrays.asList(1, 2, 3));System.out.println(l1 == l2);  // falseSystem.out.println(l1.equals(l2));  // true}
}

因为 l1 与 l2 是两个不同列表对象的引用地址，如下图所示，因此用 == 去比较这两个引用那肯定是不相等的：

在这里插入图片描述

如果想要比较自定义类的两个对象的内容是否相等，需要重写 equals(Object obj) 方法，该方法也是所有类从 Object 那边继承过来的：

package CS61B.Lecture11;import org.jetbrains.annotations.NotNull;import java.util.Iterator;public class ArraySet<T> implements Iterable<T> {...@Overridepublic boolean equals(Object obj) {// 判断obj是否是ArraySet的实例，如果是则将obj转换成ArraySet类型的对象arraySetif (obj instanceof ArraySet arraySet) {if (this.size() != arraySet.size()) return false;for (T item : this)if (!arraySet.contains(item)) return false;return true;}return false;}public static void main(String[] args) {ArraySet<Integer> s1 = new ArraySet<>();ArraySet<Integer> s2 = new ArraySet<>();for (int i = 1; i <= 3; i++) {s1.add(i);s2.add(i);}System.out.println(s1 == s2);  // falseSystem.out.println(s1.equals(s2));  // true}
}

注意我们用到了 obj instanceof ArraySet arraySet，这是 instanceof 关键字在 Java 14 中引入的新特性，该特性在 Java 16 中正式成为标准特性，被称为模式匹配（Pattern Matching），能够避免手动类型转换可能导致的错误（如忘记转换或转换错误）。

在 Java 14 之前，如果你想检查一个对象是否是某个类的实例，并对其进行类型转换，通常需要写两行代码：

if (obj instanceof ArraySet) {ArraySet arraySet = (ArraySet) obj;  // 显式类型转换// 使用arraySet...
}

从 Java 14 开始，你可以将 instanceof 检查和类型转换合并为一行代码：

if (obj instanceof ArraySet arraySet) {// 直接使用arraySet...
}