3-5ADT和OOP中的“等价性”
本次课程的目的
▪ 理解等价关系的性质。
▪ 理解根据抽象函数和观察定义的不可变类型的相等性。
▪ 区分引用相等和对象相等。
▪ 区分不同类型的严格观察和行为平等。
▪ 理解对象协定，并能够正确地为可变和不可变类型实现Equals
大纲
▪ 等价关系
▪ 不可变类型的相等性
▪ ==对等于（）
▪ 不可变类型的相等性
▪ The Object Contract
▪ 可变类型的相等性
▪ 自动装箱与平等
在很多场景下，需要判定两个对象是否 “相等”，例如：判断某个 Collection中是否包含特定元素。
==和equals()有何区别？如何为自定 义ADT正确实现equals()？
1等价关系
数据类型中的值相等吗？
▪ 在物质世界里，每一个物体都是不同的——在某种程度上，即使是两片雪花也是不同的，即使这种区别只是它们在空间中所占据的位置。
▪ 因此，两个物理物体从来就不是真正的“相等”的，它们只有相似的程度。
▪ 然而，在人类语言的世界里，在数学概念的世界里，同一事物可以有多个名称。–因此，当两个表达式表示同一事物时，很自然地会认为：1+2、√9和3是相同理想数学值的可选表达式。
等价关系
▪ 一个等价关系E⊆T x T，即：
–自反的：E（T，T）∀T∈T
–对称的：E（T，u）？.E（u，T）
–传递的：E（T，u）∧E（u，v）？.E（T，v）
–要使用E作为等式的定义，我们可以说a等于b当且仅当E（a，b）。
▪ 对于像或equals（）这样的布尔值二进制操作，等价E是操作返回true的对（x，y）的集合。
▪ 因此，对于，这些性质也可以写成：
–自反的：tt，∀t∈t
–对称的：tu··ut
–传递的：tu··uv··tv
▪ 对于equals（）方法也是如此。
2三种相等的方式
ADT上的等式运算
▪ ADT是通过创建以其操作而不是其表示为特征的类型来进行的数据抽象。
▪ 对于抽象数据类型，抽象函数（AF）解释了如何将具体表示值解释为抽象类型的值，并且我们看到了抽象函数的选择如何决定如何编写实现ADT的每个操作的代码。
▪ 抽象函数（AF）提供了一种在ADT上清晰定义相等操作的方法。
使用AF定义等式
▪ 使用抽象函数（AF）。
–回想一下，抽象函数AF:R→A将数据类型的具体实例映射到它们相应的抽象值。
–要使用AF作为等式的定义，我们说a等于b，如果且仅当AF（a）=AF（b）。
▪ 使用AF和使用关系定义equityare等价项。
–等价关系产生一个抽象函数（关系划分T，因此AF将每个元素映射到其分区类）。
–抽象函数引起的关系是等价关系
用观察定义等式
▪ 我们谈论抽象价值之间平等的另一种方式是，根据外部人（客户）对抽象价值的观察
▪ 利用观察。我们可以说，当两个物体无法通过观察区分时，它们是相等的——我们可以应用的每一个操作都会对两个物体产生相同的结果。
–考虑集合表达式{1,2}和{2,1}。
• |{1,2}| = 2 and |{2,1}| = 2
• 1 ∈ {1,2} is true, and 1 ∈ {2,1} is true
• 2 ∈ {1,2} is true, and 2 ∈ {2,1} is true
• 3 ∈ {1,2} is false, and 3 ∈ {2,1} is false
▪ 就ADT而言，“观察”意味着调用对象上的操作。所以只有当两个对象不能通过调用抽象数据类型的任何操作来区分时，它们才是相等的
接下来是一个简单ADT的例子
其中下面哪个值应该被看做相等？
因为除了构造器没有任何操作，我们不能使用观测等式
怎么判断哪些点在线上？
保证所有点构成的斜率一致即可
3 == vs. equals()
▪ Java有两种不同的操作来测试相等性，它们具有不同的语义。
–运算符比较引用。它测试引用相等性。如果两个引用指向内存中的同一个存储，则它们是的。
在快照关系图中，如果两个引用的箭头指向同一个对象，则这两个引用是==的。
–equals（）操作比较对象内容
–换句话说，对象相等。
▪ 必须为每个抽象数据类型适当地定义equals操作。——当我们定义一个新的数据类型时，我们有责任决定对象相等对数据类型的值意味着什么，并适当地实现equals（）操作。
▪ 对基本数据类型，使用判定相等
▪ 对对象类型，使用equals() – The ==
如果用，是在判断两个对象身份 标识 ID是否相等（指向内存里的同一段空间）
– 使用实现 判断
应该总是使用 equals()判断相等(如 果判断逻辑是内存地址相等，则不需要重写Object.equals()，此时equals()等价 于；如果判断逻辑是特定的，则需要重写Object.equals()，则equals()调用 的是期望的判断逻辑。无论哪种情况，使用equals()都能达到期望的目的)
▪ 在对象引用上使用==在代码中是一个坏习惯
4实现equals（）
不可变类型的相等性
▪ equals（）方法由Object定义，其默认实现如下： ▪ equals（）的默认含义与引用相等相同。
▪ 对于不可变的数据类型，这几乎总是错误的，不是 程序员所期望的
▪ 我们必须重写equals（）方法，用我们自己的实现替换它
即使d2和o2最终引用的是内存中的同一个对象，但从equals（）中仍然可以得到不同的结果
发生了什么？
▪ 类Duration已重载equals（）方法，因为方法签名与对象的签名不同。
▪ 实际上，Duration中有两个equals（）方法：–一个从Object继承的隐式equals（对象）–新的equals（Duration）。
▪ Java编译器使用参数的编译时类型在重载操作之间进行选择。静态类型检查
▪ 如果我们传递一个对象引用，如d1.equals（o2），我们最终调用equals（Object）实现。
▪ 如果我们传递一个Duration引用，如d1.equals（d2），我们最终调用equals（Duration）版本。
▪ 即使o2和d2在运行时都指向同一个对象，也会发生这种情况！Equals变得不一致
. 即使运行时o2和d2是 一个对象，但是在编译阶段，已经确定了调用的方法不同
Override Overload
▪ 很容易在方法签名中出错，并在打算重写方法时重载该方法。
▪ 当您打算重写超类中的方法时，应该使用Java的[email protected]。
▪ 使用这个注释，Java编译器将检查超类中是否确实存在具有相同签名的方法，如果您在签名中犯了错误，则会给出编译器错误。
▪ instance of运算符测试对象是否是特定类型的实例。
▪ 使用instanceof是动态类型检查，而不是静态类型检查。
▪ 一般来说，在面向对象编程中使用instanceof是一种糟糕的做法。除了实现equals之外，任何地方都不允许使用它。
▪ 此禁止还包括检查对象运行时类型的其他方法。
–例如，getClass（）也不允许。
5 The Object contract
对象中equals（）的约定
▪ 当重写equals（）方法时，必须遵守它的一般约定：
–equals必须定义等价关系
–即自反、对称和传递的关系；
–equals必须一致：对该方法的重复调用必须产生相同的结果，前提是在对象的equals比较中没有使用任何信息is modified；
–对于非空引用x，x.equals（null）应返回false；
–hashCode（）必须为equals方法认为相等的两个对象生成相同的结果。
▪ 自反-每个物体都等于它自己
▪ 对称–如果a.equals（b），那么b.equals（a）
▪ 可传递-如果a.equals（b）和b.equals（c），则a.equals（c）
▪ 一致-相等的对象保持相等，除非发生变异
▪ “Non-null”–a.equals（null）返回false
▪ 综合这些确保equals是所有对象的全局等价关系
打破等价关系
▪ 我们必须确保equals（）实现的等式定义实际上是前面定义的等价关系：自反、对称和传递。
–如果不是，那么依赖于等式的操作（如集合、搜索）将表现出不稳定和不可预测的行为。
–您不希望使用有时a等于b但b不等于a的数据类型进行编程。
–会导致微妙和痛苦的bug
Breaking哈希表
▪ 哈希表是映射的表示形式：将键映射到值的抽象数据类型。
–哈希表提供恒定的时间查找，因此它们的性能往往优于树或列表。除了提供equals和hashCode之外，不必对键进行排序或具有任何特定属性。
▪ 哈希表的工作原理：–它包含一个数组，该数组的初始化大小与我们希望插入的元素数相对应。
–当一个键和一个值被呈现出来进行插入时，我们计算该键的哈希码，并将其转换为数组范围内的索引（例如，通过模除法）。然后在该索引处插入值。
▪ 哈希表的rep不变量包含一个基本约束，即键位于由其哈希码决定的槽中
hashCode contract
▪ 每当在应用程序执行期间多次对同一对象调用hashCode方法时，只要在对象的equals比较中使用的信息没有被修改，hashCode方法就必须一致地返回相同的整数。
–从一个应用程序的一次执行到同一应用程序的另一次执行，此整数不必保持一致。
▪ 如果根据equals（Object）方法，两个对象相等，那么对两个对象中的每个对象调用hashCode方法必须产生相同的整数结果。
–根据equals（Object）方法，如果两个对象不相等，则对这两个对象中的每一个调用hashCode方法都必须产生不同的整数结果。
–但是，程序员应该知道，为不相等的对象生成不同的整数结果可能会提高哈希表的性能。
不相等的对象，也可以映射为同样的hashCode，但性能会变差
▪ Equal对象必须具有相等的哈希代码-如果重写equals，则必须重写哈希代码
▪ 不相等的对象应该有不同的哈希代码-在构造时考虑所有值字段
▪ 除非对象发生变异，否则哈希代码不能更改
▪ 为什么对象契约要求相同的对象具有相同的hashcode？
–如果两个相等的对象具有不同的哈希代码，则它们可能被放置在不同的插槽中。
–因此，如果尝试使用与插入值相等的键查找值，则查找可能会失败。
▪ 对象的默认hashCode（）实现与其默认的equals（）一致：
在我们的例子中…
▪ 在Duration中，由于我们还没有覆盖默认的hashCode（），因此我们当前正在破坏对象协定：
▪ d1和d2是相等的，但是它们有不同的散列码。
▪ 怎么解决？
重写哈希代码（）
▪ 一个简单而极端的方法来确保契约得到满足，就是hash code总是返回一些常量值，因此每个对象的hash代码都是相同的。
–这满足了对象契约，但会带来灾难性的性能影响，因为每个键都将存储在同一个槽中，并且每个查找都将退化为沿长列表的线性搜索。
▪ 标准是为用于确定相等性的对象的每个组件计算一个哈希代码（通常通过调用每个组件的哈希代码方法），然后将这些代码组合起来，再进行一些算术运算。
▪ 对于Duration，这很简单，因为类的抽象值已经是一个整数值：
▪ Java的最新版本现在有了一个实用方法Objects.hash（），它使得实现包含多个字段的哈希代码更加容易。
▪ 注意，如果根本不重写hashCode（），那么将从对象中获取一个，它基于对象的地址。
▪ 如果你Overriden Equals，这就意味着你几乎肯定违反了合同。
▪ 一般规则：
重写equals（）时始终重写hashCode（）
除非你能保证你的ADT不会被放入到Hash类型的集合类中
6可变类型的相等性
可变类型的相等性
▪ 相等：两个物体不能通过观察区分时是相等的。
▪ 对于可变对象，有两种方法可以解释这一点：当它们不能通过不改变对象状态的观察来区分时，即只调用观察者、生产者和创建者方法。这通常被严格地称为服务相等，因为它测试两个对象在程序的当前状态下是否“看起来”相同。
–当它们无法被任何观察区分时，甚至是状态变化
这被称为行为平等，因为它测试这两个对象在这个和所有未来状态下是否“行为”相同。
▪ 注：对于不变的物体，观察和行为上的平等是一样的，因为没有任何mutator的方法。
一个例子
▪ 假设我们列出一个列表，然后将其放入一个集合： ▪ 我们可以检查集合是否包含我们放入其中的列表，它确实包含：
▪ 但现在我们改变了列表：
▪ 它不再出现在场景中！
▪ 事实上，更糟糕的是：当我们遍历集合的成员时，仍然会在其中找到列表，但contains（）表示它不在那里。
▪ List是一个可变对象。在List等集合类的标准Java实现中，突变会影响equals（）和hashCode（）的结果。
▪ 当列表第一次放入HashSet时，它存储在hashCode（）结果对应的hash bucket中。
▪ 当列表随后发生变异时，它的hashCode（）会发生变化，但是HashSet没有意识到应该将它移到另一个bucket中。所以再也找不到了。
▪ 当equals（）和hashCode（）可能受到变异的影响时，我们可以破坏使用该对象作为键的哈希表的rep不变量
如果可变对象用作集合元素，则必须非常小心。
▪ 如果在对象是集合中的元素时，以影响等于比较的方式更改对象的值，则不指定集合的行为。
▪ 不幸的是，Java库对可变类的equals（）的解释不一致。 ▪ 集合使用观察等式，但其他可变类（如StringBuilder）使用behavioralequality。
两个例子
▪ Date equals（）规范：“如果且仅当getTime方法为两者返回相同的长值时，两个日期对象才相等。“
▪ List equals（）spec:“如果且仅当指定对象也是列表时，返回true，两个列表的大小相同，并且两个列表中的所有对应元素对都相等。“–如果两个列表以相同的顺序包含相同的元素，则它们被定义为相等。
从这个例子中吸取的教训
▪ equals（）应该实现行为平等。
▪ 一般来说，这意味着如果两个引用是同一对象的别名，则它们应该是equals（）。
▪ 所以可变对象应该只继承对象的equals（）和hashCode（）。
▪ 对于需要观测相等概念的客户（在当前状态下两个可变对象是否“看起来”相同），最好定义一个新方法，例如similar（）。
equals（）和hashCode（）的最终规则
▪ 对于不可变类型：
–equals（）应该比较抽象值。这和equals（）应该提供行为上的平等一样。
–hashCode（）应将抽象值映射为整数。
–因此不可变类型必须同时重写equals（）和hashCode（）。
▪ 对于可变类型：–equals（）应该比较引用，就像==。同样，这与equals（）应该提供行为平等一样。
–hashCode（）应将引用映射为整数。
–因此可变类型根本不应该重写equals（）和hashCode（），而应该只使用Object提供的默认实现。不幸的是，Java的集合并没有遵循这个规则，这导致了我们在上面看到的陷阱。
Bag是一个可变的ADT，表示通常称为multiset的对象的无序集合，其中一个对象可以出现多次。它具有以下操作：
对象中的clone（）
▪ clone（）创建并返回此对象的副本。
▪ “复制”的确切含义可能取决于对象的类别。
▪ 一般意图是，对于任何对象x：
**7自动装箱和Equals
**
▪ 基类型及其等效对象类型，例如int和Integer。
▪ 如果创建两个具有相同值的整数对象，它们将彼此相等。 ▪ 但如果xy呢？-----False（因为引用相等）
▪ 但如果（int）x（int）y呢？----真的
▪ 这段代码的结果是什么？
摘要
▪ 等式是实现抽象数据类型（ADT）的一部分。
–相等应该是等价关系（自反的、对称的、传递的）。
–等式和散列代码必须彼此一致，这样使用散列表（如HashSet和HashMap）的数据结构才能正常工作
–抽象函数是不可变数据类型中相等的基础。
–引用相等是可变数据类型中相等的基础；这是确保随时间保持一致性和避免破坏哈希表的rep不变量的唯一方法。
▪ Safe from bug——对于集合和映射之类的集合数据类型，必须正确实现相等和哈希代码。它对于编写测试也是非常理想的。因为Java中的每个对象都继承了对象实现，所以不可变类型必须覆盖它们。
▪ 很容易理解——阅读我们规范的客户和其他程序员会期望我们的类型实现适当的平等操作，如果我们不这样做，他们会感到惊讶和困惑。
▪ 随时可更改—正确实现的不可变类型的相等性将引用的相等性与抽象值的相等性分开，向客户端隐藏有关是否共享值的决定。为可变类型选择行为相等而不是观察相等有助于避免意外的别名错误。