Lab 8：HashMap¶
介绍¶
在本实验中，你会完成 MyHashMap，它是 Map61B 接口的一种实现，表示一个哈希映射。本实验与 Lab 7 非常相似，不过这一次我们构建的是 Hash Map，而不是 Tree Map。
完成实现后，你会把自己的实现性能与基于列表的 Map 实现 ULLMap 以及 Java 内置的 HashMap 类（它也使用哈希表）进行比较。我们还会比较 MyHashMap 使用不同数据结构作为桶时的性能。
MyHashMap¶
概览¶
我们已经在 MyHashMap.java 中创建了一个 MyHashMap 类，只提供了非常少的起始代码。你的目标是实现 MyHashMap 从 Map61B 接口继承的所有方法，remove 除外。对于 remove，应当抛出 UnsupportedOperationException。请注意，这一次你应实现 keySet 和 iterator；其中 iterator 返回一个遍历所存储键的 Iterator。这两个函数都可以按任意顺序返回键。
对于这些方法，我们建议你简单地创建一个 HashSet 实例变量，用它保存所有键。
请注意，在你实现 Map61B 的所有方法之前，代码无法编译。你可以一次实现一个方法：先写出所有必需方法的方法签名，但在实现中抛出 UnsupportedOperationException；等轮到实际编写某个方法时，再完成它。
起始代码¶
你可能还记得讲座中的内容：构建哈希表时，可以选择多种不同的数据结构作为桶。经典方法是选择 LinkedList。但我们也可以选择 ArrayList、TreeSet，甚至其他更疯狂的数据结构，例如 PriorityQueue，乃至另一个 HashSet！
在本实验中，我们会尝试为哈希表中的每个桶使用不同的数据结构，并通过实验观察：把不同数据结构用作哈希表的桶，是否会产生渐近意义上的差异。
你或许可以想象，如果我们在实现 MyHashMap 时完全不加考虑，那么要把桶类型替换成另一种桶类型，就需要做大量的“查找 + 替换”。例如，如果想把所有 ArrayList 桶换成 LinkedList 桶，就必须查找所有出现的 ArrayList 并替换成 LinkedList。这并不理想。
起始代码的目的，是提供一种更简单的方法，让我们能够在 MyHashMap 中试用不同的桶类型。它通过本学期前面学过的多态和继承实现这一点。它还使用了工厂方法；工厂方法用于创建对象。我们会使用工厂方法创建桶。起始文件的继承结构如下：
Map61B.java
└── MyHashMap.java
├── MyHashMapALBuckets.java
├── MyHashMapHSBuckets.java
├── MyHashMapLLBuckets.java
├── MyHashMapPQBuckets.java
└── MyHashMapTSBuckets.java
MyHashMap 使用哈希表实现 Map61B 接口。在起始代码中，我们给出了实例变量 private Collection<Node>[] buckets，它是哈希表的底层数据结构。让我们拆解一下这段代码的含义：
buckets是MyHashMap类中的一个private变量。- 它是一个由
Collection<Node>对象组成的数组（或表）；其中，每一个由Node组成的Collection都表示哈希表中的一个桶。 Node是我们提供的私有辅助类，用于存储单个键值映射。这个类的起始代码应当很容易理解，也不应当需要任何修改。java.util.Collection是大多数数据结构所实现的接口，表示一组对象。Collection接口支持向组中add、从组中remove，以及在组上iterate等方法。java.util中的许多数据结构都实现了Collection，包括ArrayList、LinkedList、TreeSet、HashSet、PriorityQueue等许多类型。
请注意，因为这些数据结构实现了 Collection，所以借助多态，我们可以把它们赋给静态类型为 Collection 的变量。
- 因此，我们由
Collection<Node>对象组成的数组，可以使用许多不同类型的数据结构实例化，例如LinkedList<Node>或ArrayList<Node>。 - 在创建新的
Collection<Node>[]并把它存入buckets变量时，请注意：在 Java 中，不能创建参数化类型的数组。Collection<Node>是参数化类型，因为我们使用Node类对Collection类进行了参数化。因此，对于任何给定的size，表达式new Collection<Node>[size]都是非法的。要绕过这一限制，应改为创建new Collection[size]，其中size是所需大小。
Collection[] 的元素可以是任意类型的集合，例如 Collection<Integer> 或 Collection<Node>。对于本实验，我们只会向 Collection[] 中添加 Collection<Node> 类型的元素。
每个 MyHashMap*Buckets 类都会使用一种不同的数据结构实例化 buckets。例如，MyHashMapLLBuckets 使用 new LinkedList<Node>() 实例化 buckets。实现这一点的机制，是工厂方法 protected Collection<Node> createBucket()；它只是返回一个实现了 Collection 的数据结构。对于 MyHashMap.java，你可以选择任何喜欢的数据结构。
例如，如果选择 LinkedList，createBucket 的方法体就是：
创建新的桶数据结构时，不得使用 new 运算符，而必须使用 createBucket 方法。起初这可能显得毫无用处，但它允许 MyHashMap*Buckets.java 类重写 createBucket 方法，从而为每一个桶提供不同的数据结构。
这样，我们最终会得到多个不同的类（MyHashMapTSBuckets.java、MyHashMapPQBuckets.java 等）；它们都使用你在 MyHashMap 中编写的实现，但为桶提供不同的类型（TreeSet、PQ 等）。我们甚至可以拥有一个桶本身也是另一个哈希表的哈希表（MyHashMapHSBuckets.java）！随后，我们可以在类似 Lab 7 中所见的速度测试中，直接比较各个 MyHashMap*Buckets.java 类。
我们还提供了额外的工厂方法：createTable 用于创建哈希表的底层数组，createNode 用于创建新的 Node 对象。使用 new 运算符而不是工厂方法来创建底层数组和 Node 对象也没有问题；我们只是为了统一而添加了这些方法。
实现要求¶
你应当实现以下构造函数：
public MyHashMap();
public MyHashMap(int initialSize);
public MyHashMap(int initialSize, double loadFactor);
下面是 MyHashMap 的一些额外要求：
- 你的哈希映射最初应当拥有等于
initialSize的桶数量。当负载因子超过所设置的loadFactor时，应增加MyHashMap的大小。回忆一下，负载因子可以计算为loadFactor = N / M，其中N是映射中的元素数量，M是桶的数量。负载因子表示平均每个桶中的元素数量。
如果没有给出 initialSize 和 loadFactor，应设置默认值 initialSize = 16 和 loadFactor = 0.75（与 Java 的内置 HashMap相同）。
- 应使用拉链法（separate chaining）处理冲突。除
ArrayList、LinkedList、Collection、HashSet、Iterator和Set外，不得导入任何库。这意味着对于MyHashMap.java，你应当使用ArrayList、LinkedList或HashSet之一作为桶类型。有关应如何实现拉链法的更多细节，请参阅上面的“起始代码”一节。 - 因为我们使用
Collection<Node>[]作为buckets，所以实现MyHashMap时，只能使用Collection接口所支持的方法。你唯一需要的方法是add、remove和iterator。在Collection中搜索Node时，只需遍历Collection，找到其key与所搜索键.equals()的Node。 - 调整大小时，务必进行乘法式扩容，而不是加法式扩容。不要求缩小容量。
- 假定插入对象的
hashCode能够很好地分散元素，你的所有MyHashMap操作都应当具有摊还常数时间（回忆：Java 中每个Object都有自己的hashCode()方法）。注意：hashCode()可能返回负值！编写代码时请考虑这一点。有关如何干净地处理这种情况的提示，请查看下面链接的讲座幻灯片。 - 如果多次插入同一个键，每次都应更新其值。你可以假定永远不会插入
null键。
测试¶
可以使用 TestMyHashMap.java 测试实现。如果选择实现额外的 remove 方法，我们在 TestHashMapExtra.java 中提供了测试。如果你正确实现了泛型 Collection 桶，还应当能够通过 TestMyHashMapBuckets.java 中的测试。TestHashMapBuckets.java 文件只是针对每个使用不同桶数据结构的 Map 子类，调用 TestMyHashMap.java 中的方法。
离开本节之前，确保你能够通过 TestMyHashMap.java 和 TestMyHashMapBuckets.java 中的测试。
资源¶
下面这些资源可能会有帮助：
- 课程参考资料页面中《Data Structures Into Java》第 136 页和第 137 页的 HashMap 代码。
- 可选《Algorithms》教材的第 3.4 章。
- 可选教材中的 HashTable 代码。
ULLMap.java（已提供）：一个能够正常工作的、基于无序链表的Map61B实现。- 关于 HashMaps、继承和子类型多态的讲座幻灯片。
HashMap 速度测试¶
InsertRandomSpeedTest.java 和 InsertInOrderSpeedTest.java 中提供了两个交互式速度测试。在完成 MyHashMap 之前，不要尝试运行这些测试。准备好后，可以在 IntelliJ 中运行它们。
InsertRandomSpeedTest 类会测试你的 MyHashMap、已提供的 ULLMap 和 Java 内置 HashMap 在插入元素时的速度。它会询问用户输入规模 N，然后生成 N 个长度为 10 的 String，并将它们作为 <String, Integer> 对插入映射中。
尝试运行它，看看随着 N 增大，你的数据结构与朴素实现和工业级实现相比如何扩展。把结果记录在所提供的 lab8/speedTestResults.txt 文件中。结果没有规定的标准格式，也没有规定所需的数据点数量。
现在尝试运行 InsertInOrderSpeedTest。它的行为与 InsertRandomSpeedTest 类似，但这一次，<String, Integer> 键值对中的 String 会按照字典序递增顺序插入。请注意，与 Lab 7 不同，你的代码性能应当大致接近 Java 的内置解答——例如控制在大约 10 倍以内。这告诉我们，与最先进的 TreeMap 相比，最先进的 HashMap 相对容易实现。
什么时候使用 BSTMap/TreeMap 会比使用 HashMap 更好？与你的实验同伴讨论这个问题，并把答案添加到 speedTestResults.txt。
更换桶类型：速度测试¶
如果你正确实现了泛型 Collection 桶，大部分工作就已经完成了！我们可以直接比较不同的数据结构 MyHashMap*Buckets.java。我们提供了 speed/BucketsSpeedTest.java，它是一个交互式测试：首先询问用户一个整数 L，表示后续操作中所使用 String 的长度；然后在循环中询问用户一个整数 N，并对以下五种数据结构分别进行速度测试：
MyHashMapALBuckets，使用ArrayList桶。MyHashMapLLBuckets，使用LinkedList桶。MyHashMapTSBuckets，使用TreeSet桶。MyHashMapPQBuckets，使用PriorityQueue桶。MyHashMapHSBuckets，使用HashSet桶。
尝试运行它，比较不同实现如何随 N 扩展。与你的实验同伴讨论结果，并把回答记录在 speedTestResults.txt 中。
你可能会注意到，我们的 MyHashMapTSBuckets 和 MyHashMapHSBuckets 实现通过遍历整个数据结构来搜索 Node。但根据我们已经掌握的知识，树和哈希表支持比这更高效的查找。
如果能够在 TreeSet 上使用对数时间搜索，或者在 HashSet 上使用常数时间搜索，我们的哈希表会加速吗？这里不需要实现任何新内容，只需与实验同伴讨论，并把想法记录在 speedTestResults.txt 中。
可选练习¶
这一部分不会评分，但你仍然可以从自动评分器获得反馈。
在 MyHashMap 类中实现 remove(K key) 和 remove(K key, V value)。作为额外挑战，请在不使用第二个实例变量存储键集合的情况下实现 keySet() 和 iterator。
对于 remove，如果参数键在 MyHashMap 中不存在，应返回 null。否则，删除键值对 (key, value) 并返回 value。
实验总结与提交¶
实验结束时，你的 TA 会讲解参考解答。如果你尚未完成实验，这会很有帮助，因为我们不希望你在实验课之外被这个实验困住太久。（这也是鼓励你参加实验课的一个理由！）
确保提交完成的 MyHashMap.java 和 speedTestResults.txt，并像往常一样通过 Git 和 Gradescope 提交。