【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(1) O(1) 或 O ( l o g n ) O(log n) O(logn)。
在 Java 中，Set 是一个不包含重复元素的集合接口。它是 java.util 包的一部分，继承自 Collection 接口。Java 已经默认提供了多个 Set 的实现类，常用的有：
（1）HashSet
基于哈希表实现，不保证元素的顺序，允许有 null 元素，插入、删除和查找操作的时间复杂度为
O
(
1
)
O(1)
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
)
O(1)
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
)
O(log n)
O(logn)，在 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;
}
@Override
public boolean hasNext() {
return this.pos < size;
}
@Override
public 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()); // 3
for (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> {
...
@Override
public 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()); // 3
System.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); // false
System.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> {
...
@Override
public boolean equals(Object obj) {
// 判断obj是否是ArraySet的实例，如果是则将obj转换成ArraySet类型的对象arraySet
if (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); // false
System.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...
}