CS61B 课程笔记（HW3 Hashing)

背景

哈希表是一种用于实现关联数组（即键值对映射）的数据结构。哈希表通过哈希函数将键映射到表中的特定位置，从而实现快速的数据访问。该作业旨在深入理解哈希表的实现及其性能，尤其是如何有效处理哈希冲突。

获取骨架文件

使用以下命令从版本控制系统中获取骨架代码：

1	git pull skeleton master

作业简介

本次作业将帮助我们更好地理解哈希表的工作原理。由于期中考试在作业截止日的次日，作业相对简短且集中，建议利用额外时间通过学习指南和与同学的讨论来解决问题。

简单 Oomage

在本部分作业中，您需要为 SimpleOomage 类编写 equals 和 hashCode 方法，以及为 hashCode 方法编写测试（在 TestSimpleOomage 类中）。

`SimpleOomage` 类

SimpleOomage 类有三个属性：

red：红色分量
green：绿色分量
blue：蓝色分量

每个属性的值必须是 0 到 255 之间的 5 的倍数。例如：

1	SimpleOomage ooA = new SimpleOomage(35, 90, 215); // 有效

编写 `equals` 方法

运行 TestSimpleOomage，会看到 testEquals 测试失败。原因在于 SimpleOomage 使用默认的 equals 方法，它基于对象的内存地址进行比较。为了解决这个问题，我们需要重写 equals 方法，使其遵循以下约定：

自反性：对于任何非空对象 \(x\)，\(x.equals(x)\) 必须为真。
对称性：对于任何非空对象 \(x\) 和 \(y\)，如果 \(x.equals(y)\) 为真，则 \(y.equals(x)\) 也必须为真。
传递性：如果 \(x.equals(y)\) 和 \(y.equals(z)\)，则 \(x.equals(z)\) 也必须为真。
一致性：如果不改变对象 \(x\) 和 \(y\)，则 \(x.equals(y)\) 必须返回相同的结果。
非空：对于任何非空 \(x\)，\(x.equals(null)\) 应该返回假。

以下是 equals 方法的实现示例：

@Override
public boolean equals(Object obj) {
    if (this == obj) return true; // 自反性
    if (obj == null || getClass() != obj.getClass()) return false; // 非空
    SimpleOomage other = (SimpleOomage) obj; // 类型转换
    return this.red == other.red && this.green == other.green && this.blue == other.blue; // 对称性
}

编写 `hashCode` 方法

重写 equals 方法后，必须重写 hashCode 方法，以确保 hashCode 和 equals 方法一致。运行 testHashCodeAndEqualsConsistency 测试，您会发现它失败，原因是 ooA 和 ooA2 的哈希码是默认的（基于内存地址），HashSet 无法找到相同的 Oomage。

以下是 hashCode 方法的实现示例：

@Override
public int hashCode() {
    int hash = 17; // 初始哈希值
    hash = 31 * hash + red;   // 计算红色分量的哈希
    hash = 31 * hash + green; // 计算绿色分量的哈希
    hash = 31 * hash + blue;  // 计算蓝色分量的哈希
    return hash; // 返回最终哈希值
}

完美的 `hashCode`

为了确保哈希值的分布均匀，设置 USE_PERFECT_HASH 变量为 true，并在 hashCode() 方法中实现一个完美的哈希码计算。这样可以确保两个 SimpleOomage 只有在其红、绿、蓝值完全相同时才具有相同的哈希码。

评估哈希码的分布

在 OomageTestUtility 类中，填充 haveNiceHashCodeSpread(List<Oomage> oomages, int M) 方法，确保在 M 个桶中，哈希码分布良好：

每个桶中的 Oomage 数量不少于 \(N / 50\)。
每个桶中的 Oomage 数量不超过 \(N / 2.5\)。

复杂 Oomage

ComplexOomage 类有一个整数列表（在 0 到 255 之间），而不是三个实例变量。您无需更改此类，只需编写测试以找出哈希码的缺陷。以下是 ComplexOomage 类的一个简化示例：

public class ComplexOomage extends Oomage {
    private List<Integer> params;

    public ComplexOomage(List<Integer> params) {
        this.params = params;
    }

    @Override
    public int hashCode() {
        // 计算哈希码
        int hash = 0;
        for (int param : params) {
            hash = hash * 31 + param;
        }
        return hash;
    }
}