CS61B 课程笔记（Lecture 13 Generics, Autoboxing）

自动转换

自动装箱与拆箱

如上一章所述，我们可以使用 <> 语法定义带有泛型类型变量的类，例如 LinkedListDeque<Item> 和 ArrayDeque<Item>。实例化一个使用泛型的类时，必须用具体类替代泛型，以指定放入该类的项的类型。

Java 有 8 种基本类型，所有其他类型都是引用类型。一个特点是，我们不能将基本类型作为泛型的实际类型参数。例如，ArrayDeque<int> 是语法错误，应该使用 ArrayDeque<Integer>。每种基本类型都有相应的引用类型，如下表所示。这些引用类型被称为“包装类”。

基本类型 包装类
boolean Boolean
byte Byte
char Character
short Short
int Integer
long Long
float Float
double Double

手动转换示例

假设我们需要在使用泛型数据结构时手动转换基本类型与引用类型：

1
2
3
4
5
6
7
8
public class BasicArrayList {
    public static void main(String[] args) {
        ArrayList<Integer> L = new ArrayList<Integer>();
        L.add(new Integer(5));
        L.add(new Integer(6));
        int first = L.get(0).valueOf(); // 手动转换
    }
}

这样的代码会比较繁琐。幸运的是，Java 可以隐式地在基本类型和包装类型之间进行转换，因此下面的代码可以正常工作：

1
2
3
4
5
6
7
8
public class BasicArrayList {
    public static void main(String[] args) {
        ArrayList<Integer> L = new ArrayList<Integer>();
        L.add(5); // 自动装箱
        L.add(6);
        int first = L.get(0); // 自动拆箱
    }
}

Java 会自动“装箱”和“拆箱”基本类型与其对应的引用类型之间的值。例如，如果我们有以下函数：

1
2
3
public static void blah(Integer x) {
    System.out.println(x);
}

并用以下方式调用它：

1
2
int x = 20;
blah(x); // 自动装箱

Java 会隐式创建一个值为 20 的新 Integer，这等同于 blah(new Integer(20))。

同样，如果 Java 期望基本类型：

1
2
3
public static void blahPrimitive(int x) {
    System.out.println(x);
}

但你提供了对应的包装类型的值：

1
2
Integer x = new Integer(20);
blahPrimitive(x); // 自动拆箱

Java 将自动拆箱该整数，相当于调用 Integer 类的 valueOf 方法。

注意事项

关于自动装箱和拆箱，有几个要点需要注意：

  1. 数组从不自动装箱或拆箱。例如，如果你有一个整数数组 int[] x，并尝试将其地址放入一个类型为 Integer[] 的变量中，编译器将不允许。
  2. 自动装箱和拆箱对性能有可测量的影响。依赖于自动装箱和拆箱的代码会比不使用这种自动转换的代码慢。
  3. 包装类型使用的内存比基本类型多。在大多数现代计算机上，代码必须保存对对象的 64 位引用，每个对象还需要 64 位的开销来存储动态类型等信息。

自动装箱与相等性

Java 也会在需要时自动扩展基本类型。如果程序期望类型为 T2 的基本类型，而给定的变量类型为 T1，且 T2 可以接受比 T1 更宽的值范围，则该变量将被隐式转换为类型 T2。

例如，Java 中的 double 比 int 更宽。假设有如下函数：

1
2
3
public static void blahDouble(double x) {
    System.out.println("double: " + x);
}

我们可以用 int 参数调用它：

1
2
int x = 20;
blahDouble(x); // 自动扩展

这相当于 blahDouble((double) x)。

如果想从更宽的类型转换到更窄的类型，则必须手动转换。例如：

1
2
3
public static void blahInt(int x) {
    System.out.println("int: " + x);
}

如果用 double 值调用此方法，就需要强制转换：

1
2
double x = 20;
blahInt((int) x); // 强制转换

有关扩展的更多细节，请参阅官方 Java 文档。

不可变性

不可变性是一个概念，可能你之前没有意识到，但一旦意识到它的存在，会大大简化你的生活。不可变数据类型指其实例在实例化后无法以任何可观察的方式改变。例如，Java 中的 String 对象是不可变的。调用 String 的任何方法都不会修改原始的 String，而是返回一个全新的 String 对象。

可变数据类型包括像 ArrayDeque 和 Planet 这样的对象，这些对象可以添加或删除项，或随着时间变化其状态。

任何具有非私有变量的数据类型都是可变的，除非那些变量被声明为 final。final 关键字用于防止变量在首次赋值后被更改。例如：

1
2
3
4
5
6
7
8
9
public class Date {
    public final int month;
    public final int day;
    public final int year;

    public Date(int m, int d, int y) {
        month = m; day = d; year = y;
    }
}

该类是不可变的，实例化后无法更改其属性的值。

不可变数据类型的优点：

  • 防止错误并简化调试，因为属性永远不会改变。
  • 可以依赖对象具有某种行为/特征。

缺点：

  • 更改属性时需要创建新对象。

注意事项：

  • 将引用声明为 final 不会使所指向的对象不可变。例如：
1
public final ArrayDeque<String> deque = new ArrayDeque<String>();

deque 变量是 final，无法重新赋值，但它指向的 ArrayDeque 对象可以被改变，因为 ArrayDeque 始终是可变的。

创建另一个泛型类

现在我们已经创建了泛型列表，例如 DLLists 和 ALists，接下来我们将转向另一种数据类型：映射。映射允许将键与值关联，比如“Josh 在考试中的分数是 0”可以存储在一个将学生与他们的考试分数关联的映射中。映射相当于 Python 中的字典。

我们将创建 ArrayMap 类，实现 Map61B 接口，这是 Java 内置映射接口的一个受限版本。ArrayMap 将具有以下方法：

  1. put(key, value)：将键与值关联。
  2. containsKey(key)：确定是否存在给定键。
  3. get(key)：如果给定键存在，返回相应的值，否则返回 null。
  4. remove(key)：删除给定键及其关联的值。

首先，我们创建一个私有 Node 类，表示映射的每个键值对：

1
2
3
4
5
6
7
8
9
10
11
private class Node {
    String key;
    Integer value;
    Node next;

    public Node(String key, Integer value) {
        this.key = key;
        this.value = value;
        this.next = null;
    }
}

现在我们的 ArrayMap 实现将是：

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
public class ArrayMap {
    private Node[] buckets;
    private int size;

    public ArrayMap() {
        buckets = new Node[10]; // 初始化数组，大小为 10
        size = 0;
    }

    public void put(String key, Integer value) {
        int index = hash(key);
        Node newNode = new Node(key, value);
        newNode.next = buckets[index];
        buckets[index] = newNode;
        size++;
    }

    public boolean containsKey(String key) {
        int index = hash(key);
        Node current = buckets[index];
        while (current != null) {
            if (current.key.equals(key)) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    public Integer get(String key) {
        int index = hash(key);
        Node current = buckets[index];
        while (current != null) {
            if (current.key.equals(key)) {
                return current.value;
            }
            current = current.next;
        }
        return null;
   

 }

    public void remove(String key) {
        int index = hash(key);
        Node current = buckets[index];
        Node previous = null;
        while (current != null) {
            if (current.key.equals(key)) {
                if (previous == null) {
                    buckets[index] = current.next; // 删除头节点
                } else {
                    previous.next = current.next; // 删除中间或尾节点
                }
                size--;
                return;
            }
            previous = current;
            current = current.next;
        }
    }

    private int hash(String key) {
        return Math.abs(key.hashCode() % buckets.length); // 哈希函数
    }
}

详细解释：

1. 类和成员变量

1
2
3
public class ArrayMap {
    private Node[] buckets;  // 用于存储键值对的数组（桶）
    private int size;        // 当前映射中键值对的数量
  • ArrayMap 类: 这是一个自定义的映射类，实现了将键（字符串）与值（整数）关联的功能。
  • buckets: 一个数组，存储每个键值对的链表。每个数组元素称为一个“桶”，可以处理哈希冲突。
  • size: 当前存储的键值对数量，用于跟踪映射的大小。

2. 构造函数

1
2
3
4
public ArrayMap() {
    buckets = new Node[10]; // 初始化数组，大小为 10
    size = 0;
}
  • 构造函数: 初始化 buckets 数组，大小为 10，并将 size 设置为 0。这样，在创建 ArrayMap 对象时，系统会为桶分配空间。

3. put 方法

1
2
3
4
5
6
7
public void put(String key, Integer value) {
    int index = hash(key);  // 计算键的哈希值，获取数组索引
    Node newNode = new Node(key, value);  // 创建新的节点
    newNode.next = buckets[index];  // 将新节点添加到链表的头部
    buckets[index] = newNode;  // 更新桶
    size++;  // 增加大小
}
  • put 方法: 用于将键值对添加到映射中。
    • 通过哈希函数获取键的索引。
    • 创建新的节点并将其插入到对应桶的链表头部。
    • 增加映射的大小。

4. containsKey 方法

1
2
3
4
5
6
7
8
9
10
11
public boolean containsKey(String key) {
    int index = hash(key);  // 获取哈希值索引
    Node current = buckets[index];  // 从相应桶开始查找
    while (current != null) {
        if (current.key.equals(key)) {
            return true;  // 找到键
        }
        current = current.next;  // 移动到下一个节点
    }
    return false;  // 未找到
}
  • containsKey 方法: 检查映射中是否存在指定的键。
    • 通过哈希函数计算索引，从对应的桶开始查找。
    • 遍历链表，直到找到匹配的键或链表结束。

5. get 方法

1
2
3
4
5
6
7
8
9
10
11
public Integer get(String key) {
    int index = hash(key);  // 获取哈希值索引
    Node current = buckets[index];  // 从相应桶开始查找
    while (current != null) {
        if (current.key.equals(key)) {
            return current.value;  // 找到键，返回对应的值
        }
        current = current.next;  // 移动到下一个节点
    }
    return null;  // 未找到，返回 null
}
  • get 方法: 根据键获取对应的值。
    • 类似于 containsKey，首先获取哈希值索引，然后遍历链表查找匹配的键。

6. remove 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void remove(String key) {
    int index = hash(key);  // 获取哈希值索引
    Node current = buckets[index];  // 从相应桶开始查找
    Node previous = null;  // 用于跟踪前一个节点
    while (current != null) {
        if (current.key.equals(key)) {
            if (previous == null) {
                buckets[index] = current.next; // 删除头节点
            } else {
                previous.next = current.next; // 删除中间或尾节点
            }
            size--;  // 减少大小
            return;  // 返回
        }
        previous = current;  // 更新前一个节点
        current = current.next;  // 移动到下一个节点
    }
}
  • remove 方法: 从映射中删除指定的键值对。
    • 查找键的位置，若是头节点，则直接修改桶指向下一个节点；否则更新前一个节点的 next 指针以移除当前节点。
    • 减少映射的大小。

7. hash 方法

1
2
3
private int hash(String key) {
    return Math.abs(key.hashCode() % buckets.length); // 哈希函数
}
  • hash 方法: 用于计算给定键的哈希值并映射到桶的索引。
    • 使用 hashCode() 方法生成哈希值，然后通过取模操作确保索引在数组范围内。

总结

整体来看，ArrayMap 类通过数组和链表的结合实现了一个简单的键值对映射，支持基本的添加、查找和删除操作。哈希表的设计使得这些操作在平均情况下可以达到常数时间复杂度 (O(1))，但在最坏情况下（如发生大量哈希冲突）会退化为线性时间复杂度 (O(n))。