MIT_6.031之Equality

Equality

目标

  • 理解通过抽象函数、等价关系和观察定义的“相等”。
  • 区分引用相等和对象相等。
  • 区分可变类型中的观察相等和行为相等。
  • 理解“对象契约”（Object contract），并能够正确为可变/不可变类型设计相等。

介绍

如何定义抽象数据类型 (ADT)

  • 抽象数据类型（ADT）是由其操作而非内部表示决定的。
  • ADT中的抽象函数解释了如何将内部表示映射为用户理解的抽象数据。
  • 抽象函数决定了我们应该如何实现 ADT 的各个操作。
  • 如何定义 ADT 的相等：抽象函数会给我们对相等操作一个清晰的定义。

在现实世界中，任何物体都是不相等的，它们仅在某些方面相似。而在语言和数学中，可以有许多完全相同的对象。

等价关系 (Equivalence Relation)

可以从三个角度定义相等：

  1. 抽象函数：
    这是一个封闭的二元关系运算 $ R: A A $，若 $ R(a) == R(b) $，则认为 $ a, b $ 相等。

  2. 等价关系：
    对于关系 $ E T T $，若满足：

    • 自反性： $ E(t,t) t T $
    • 对称性： $ E(t,u) E(u,t) $
    • 传递性： $ E(t,u) E(u,v) E(t,v) $

    则认为 $ a == b $ 当且仅当 $ E(a,b) $。

  3. 使用者角度：
    两个对象相等当且仅当它们的所有观察操作（根据 ADT 的规格说明规定）返回相同的结果。例如，集合 \(\{1,2\}\) 和 \(\{2,1\}\) 是相等的，因为无法观察到不同。

== vs. equals()

Java中有两种判断相等的操作：

  • ==：
    • 比较的是索引。
    • 测试的是引用相等（referential equality）。
    • 如果两个索引指向同一块存储区域，则它们相等。
  • equals()：
    • 比较的是对象的内容。
    • 测试的是对象值相等（object equality）。
    • 在每个 ADT 中，equals 操作必须合理定义。
Language Referential Equality Object Equality
Java == equals()
Python is ==
JavaScript == n/a

在 Java 中，== 总是判断引用是否相等。

当定义新的 ADT 时，需要判断对于该 ADT 对象值相等意味着什么，以及如何实现 equals() 操作。

不可变类型的相等

equals() 在 Object 中的默认实现方式如下：

1
2
3
4
5
6
public class Object {
    ...
    public boolean equals(Object that) {
        return this == that;
    }
}

对于不可变类型的对象，默认实现几乎总是错误的。因此需要覆盖 equals() 方法。

错误的 equals() 实现示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Duration {
    ...   
    public boolean equals(Duration that) {
        return this.getLength() == that.getLength();        
    }
}

// 测试
Duration d1 = new Duration (1, 2);
Duration d2 = new Duration (1, 2);
Object o2 = d2;
d1.equals(d2) → true
d1.equals(o2) → false

正确的 equals() 实现：

1
2
3
4
5
6
7
8
9
@Override
public boolean equals(Object that) {
    return that instanceof Duration && this.sameValue((Duration)that);
}

// 返回true当且仅当this和that表示相同的抽象值
private boolean sameValue(Duration that) {
    return this.getLength() == that.getLength();
}
  • instanceof 用于测试传入的 that 是否是 Duration 或其子类。

对象契约 (Object Contract)

由于 Object 的规格说明非常重要，有时也称其为“对象契约”（the Object Contract）。

主要研究 equals 的规格说明：

  1. 等价关系：equals 必须定义一个等价关系，满足自反性、对称性和传递性。
  2. 确定性：equals 的结果在连续调用时应保持一致。
  3. 不为 null：对于不是 null 的索引 $ x $， $ x.equals(null) $ 应返回 false。
  4. 哈希一致性：如果两个对象通过 equals 操作比较结果为 true，则它们各自的 hashCode 也应相同。

破坏等价关系

如果 equals() 操作未满足自反性、对称性和传递性，相关操作（如集合、搜索）将变得不可预测。

例如，以下实现存在传递性问题：

1
2
3
4
5
private static final int CLOCK_SKEW = 5; // seconds

private boolean sameValue(Duration that) {
    return Math.abs(this.getLength() - that.getLength()) <= CLOCK_SKEW;
}

在这种情况下，d_0_57 和 d_1_00 可能相等，但 d_0_57 不等于 d_1_03，导致不满足传递性。

破坏哈希表

ADT 必须同时提供 equals 和 hashCode 两个方法。相同对象的 hashCode 必须相同，否则无法在哈希表中找到相同的对象。

1
2
3
4
5
public class Object {
  ...
  public boolean equals(Object that) { return this == that; }
  public int hashCode() { return /* the memory address of this */; }
}

对于不可变对象，必须重新实现 hashCode()。

1
2
3
4
5
Duration d1 = new Duration(1, 2);
Duration d2 = new Duration(1, 2);
d1.equals(d2) → true
d1.hashCode() → 2392
d2.hashCode() → 4823

在此情况下，d1 和 d2 的 equals() 返回 true，但 hashCode 不相同，因此需要修复。

确保相等的对象产生相同的 hashCode，无论其实现如何，只要遵守这一点，代码都是正确的。

可变类型的相等

对于可变对象，Java 通常实现的是观察相等。即两个索引在不改变各自对象状态的前提下相等。

例如，两个不同的 List 对象包含相同的序列元素，则 equals() 操作返回 true。

但观察相等可能导致隐秘的 bug：

1
2
3
for (List<String> l : set) { 
    set.contains(l) → false!  // 迭代器循环时，集合仍然存在，但 contains() 返回 false
}

解决方案

java.util.Set 规格说明中指出：当可变对象作为集合的元素时要特别小心。如果对象内容改变而影响相等比较，集合的行为将是不确定的。

因此，可变类型的 equals() 应实现为行为相等。即在任何情况下都相等，即使调用了改造者。

对于需要观察相等操作的可变类型，最好设计一个新的操作，如 similar() 或 sameValue()。

equals() 和 hashCode() 的总结

不可变类型：

  • equals() 应比较抽象值是否相等。
  • hashCode() 应将抽象值映射为整数。

因此，不可变类型应同时覆盖 equals() 和 hashCode()。

可变类型：

  • equals() 应比较索引，类似于 ==。
  • hashCode() 应将索引映射为整数。

因此，可变类型通常不应覆盖 equals() 和 hashCode()，而应直接继承 Object 中的方法。

自动装箱与相等

包装类型的 equals() 比较两个对象的值：

1
2
3
4
5
Integer x = new Integer(3);
Integer y = new Integer(3);
x.equals(y) → true // 值相等
x == y // 返回 false // 这是引用相等
(int)x == (int)y // 返回 true // 这是行为相等

在使用 Map 时，值会自动装箱：

1
2
3
4
Map<String, Integer> a = new HashMap(), b = new HashMap();
a.put("c", 130);
b.put("c", 130);
a.get("c") == b.get("c") → ?? // 返回什么？
  • 表达式 `

a.get("c") == b.get("c")的结果是值比较的结果，而不是引用比较的结果，因此返回true`。

练习

  1. 试着实现 equals() 和 hashCode() 的不当实现，并思考其后果。
  2. 讨论可变与不可变类型之间的差异，特别是在如何设计相等的理解上。
  3. 探讨在不同上下文中使用 == 和 equals() 的影响，尤其是在处理集合时。

练习答案

1. 实现 equals() 和 hashCode() 的不当实现，并思考其后果

不当实现示例：

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
public class Person {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public boolean equals(Object obj) {
        // 错误的实现：未检查类型
        if (obj instanceof Person) {
            Person other = (Person) obj;
            return name.equals(other.name);
        }
        return false;
    }

    @Override
    public int hashCode() {
        // 错误的实现：只基于 name
        return name.hashCode();
    }
}

后果：

  • 不满足自反性、对称性和传递性：如果两个 Person 对象具有相同的名字，但年龄不同，equals() 返回 true，导致违反相等关系的基本属性。
  • 哈希表破坏：如果使用 Person 对象作为 HashSet 或 HashMap 的键，由于 hashCode() 只考虑 name，两个不同年龄的 Person 可能会被认为是相等的，导致不可预测的行为，如无法正确检索对象。

2. 讨论可变与不可变类型之间的差异，特别是在如何设计相等的理解上

  • 不可变类型：
    • 定义清晰的相等标准：不可变对象的状态在创建后不会改变，因此其相等性可以稳定地基于对象的值。
    • 实现 equals() 时，通常需要比较对象的所有属性值，并在 hashCode() 中使用相同的属性。
    • 例子：String 类型，两个字符串内容相同则认为相等。
  • 可变类型：
    • 状态可能会变化：可变对象的属性可以在生命周期内被修改，导致相等性变得不稳定。
    • 设计时需要小心：通常建议不覆盖 equals() 和 hashCode()，或在设计时明确如何处理变化，避免在集合中使用可变对象。
    • 例子：ArrayList 的两个实例，如果内容不同，则它们不应被视为相等，但在状态变化后，它们的比较可能会引入错误。

3. 探讨在不同上下文中使用 == 和 equals() 的影响，尤其是在处理集合时

  • 使用 ==：
    • 测试引用相等：适用于检查对象是否是同一实例，适合于性能敏感的场合。
    • 在集合中：如果集合中需要判断唯一性，使用 == 可能会导致错误，因为不同的实例即使内容相同也不会被视为相等。
  • 使用 equals()：
    • 测试对象内容相等：适用于比较对象的逻辑等价性。
    • 在集合中：Set 和 Map 等数据结构依赖于 equals() 和 hashCode() 的正确实现来判断元素的相等性。如果未正确实现这些方法，可能导致无法正确存储、查找或删除元素。

例子：

1
2
3
Set<Person> people = new HashSet<>();
people.add(new Person("Alice", 30));
people.add(new Person("Alice", 30)); // 如果 equals() 未正确实现，第二个 Alice 将被添加到集合中

总结：

  • 在设计相等性时需考虑对象的特性（可变或不可变），并明确使用 == 或 equals() 的场景，以确保代码的正确性和可维护性。