摘要：抽象函數(shù)引發(fā)的關(guān)系是等價關(guān)系。所以當且僅當通過調(diào)用抽象數(shù)據(jù)類型的任何操作不能區(qū)分它們時，兩個對象是相等的。必須為每個抽象數(shù)據(jù)類型適當?shù)囟x操作。一般來說，在面向?qū)ο缶幊讨惺褂檬且环N陋習。

什么是等價性？為什么要討論等價性？
三種等價性的方式
==與equals（）
不可變類型的等價性
對象契約
可變類型的等價性
自動包裝和等價性

ADT上的相等操作

ADT是通過創(chuàng)建以操作為特征的類型而不是其表示的數(shù)據(jù)抽象。
對于抽象數(shù)據(jù)類型，抽象函數(shù)（AF）解釋了如何將具體表示值解釋為抽象類型的值，并且我們看到了抽象函數(shù)的選擇如何決定如何編寫實現(xiàn)每個ADT操作的代碼。
抽象函數(shù)（AF）提供了一種方法來清晰地定義ADT上的相等操作。

數(shù)據(jù)類型中值的相等性？

在物質(zhì)世界中，每個物體都是不同的 - 即使兩個雪花的區(qū)別僅僅是它們在太空中的位置，在某種程度上，即使是兩個雪花也是不同的。
所以兩個實體對象永遠不會真正“相等”。 他們只有相似的程度。
然而，在人類語言的世界中，在數(shù)學概念的世界中，對同一事物可以有多個名稱。

當兩個表達式表示相同的事物時，很自然地：1 + 2，√9和3是同一個理想數(shù)學值的替代表達式。

使用AF或使用關(guān)系

使用抽象函數(shù)。 回想一下抽象函數(shù)f：R→A將數(shù)據(jù)類型的具體實例映射到它們相應(yīng)的抽象值。 為了使用f作為等價性的定義，我們說當且僅當f（a）= f（b）時等于b。
使用關(guān)系。 等價關(guān)系是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作為等價性的定義，當且僅當E（a，b）時，我們會說a等于b。

等價關(guān)系：自反，對稱，傳遞
這兩個概念是等價的。

等價關(guān)系導(dǎo)致抽象函數(shù)（關(guān)系分區(qū)T，因此f將每個元素映射到其分區(qū)類）。

抽象函數(shù)引發(fā)的關(guān)系是等價關(guān)系。

使用觀察

我們可以談?wù)摮橄髢r值之間的等價性的第三種方式就是外部人（客戶）可以觀察他們的情況
使用觀察。 我們可以說，當兩個對象無法通過觀察進行區(qū)分時，這兩個對象是相同的 - 我們可以應(yīng)用的每個操作對兩個對象都產(chǎn)生相同的結(jié)果。站在外部觀察者角度

就ADT而言，“觀察”意味著調(diào)用對象的操作。 所以當且僅當通過調(diào)用抽象數(shù)據(jù)類型的任何操作不能區(qū)分它們時，兩個對象是相等的。

Java有兩種不同的操作，用于測試相等性，具有不同的語義。

==運算符比較引用。

它測試引用等價性。 如果它們指向內(nèi)存中的相同存儲，則兩個引用是==。 就快照圖而言，如果它們的箭頭指向相同的對象氣泡，則兩個引用是==。

equals()操作比較對象內(nèi)容

換句話說，對象等價性。

必須為每個抽象數(shù)據(jù)類型適當?shù)囟xequals操作。在自定義ADT時，需要重寫對象的equals()方法

當我們定義一個新的數(shù)據(jù)類型時，我們有責任決定數(shù)據(jù)類型值的對象相等是什么意思，并適當?shù)貙崿F(xiàn)equals()操作。

==運算符與equals方法

對于基本數(shù)據(jù)類型，您必須使用==對基本數(shù)據(jù)類型，使用==判定相等
對于對象引用類型對象類型，使用equals()

==運算符提供身份語義如果用==，是在判斷兩個對象身份標識ID是否相等(指向內(nèi)存里的同一段空間)

完全由Object.equals實現(xiàn)

即使Object.equals已被覆蓋，這很少是你想要的！

你應(yīng)該(幾乎)總是使用.equals

重寫方法的提示

如果你想覆蓋一個方法：

確保簽名匹配

使用@Override編譯器有你的背部

復(fù)制粘貼聲明(或讓IDE為你做)

equals()方法由Object定義，其默認含義與引用相等相同。在對象中實現(xiàn)的缺省equals()方法是在判斷引用等價性
對于不可變的數(shù)據(jù)類型，這幾乎總是錯誤的。
我們必須重寫equals()方法，將其替換為我們自己的實現(xiàn)。

重寫與重載

在方法簽名中犯一個錯誤很容易，并且當您打算覆蓋它時重載一個方法。
只要你的意圖是在你的超類中重寫一個方法，就應(yīng)該使用Java的批注@Override。
通過這個注解，Java編譯器將檢查超類中是否存在具有相同簽名的方法，如果簽名中出現(xiàn)錯誤，則會給出編譯器錯誤。

instanceof

instanceof運算符測試對象是否是特定類型的實例。
使用instanceof是動態(tài)類型檢查，而不是靜態(tài)類型檢查。
一般來說，在面向?qū)ο缶幊讨惺褂胕nstanceof是一種陋習。 除了實施等價性之外，任何地方都應(yīng)該禁止。
這種禁止還包括其他檢查對象運行時類型的方法。

例如，getClass()也是不允許的。

對象中equals()的契約

您重寫equals()方法時，您必須遵守其總體契約：

等于必須定義一個等價關(guān)系

即一種等價關(guān)系：自反，傳遞，對稱

equals必須一致：對方法的重復(fù)調(diào)用必須產(chǎn)生相同的結(jié)果，前提是沒有在對象的等值比較中使用的信息被修改;除非對象被修改了，否則調(diào)用多次等于應(yīng)同樣的結(jié)果

對于非空引用x，x.equals(null)應(yīng)返回false;

hashCode()必須為等于equals方法的兩個對象產(chǎn)生相同的結(jié)果。 “相等”的對象，其hashCode()的結(jié)果必須一致

Equals契約

equals方法實現(xiàn)等價關(guān)系：

自反：對于任何非空參考值x，x.equals(x)必須返回true。

對稱：對于任何非空引用值x和y，當且僅當y.equals(x)返回true時，x.equals(y)必須返回true。

傳遞：對于任何非空引用值x，y，z，如果x.equals(y)返回true并且y.equals(z)返回true，則x.equals(z)mus返回true。

一致性：對于任何非空引用值x和y，如果修改了在對象上的等值比較中沒有使用的信息，則x.equals(y)的多個調(diào)用始終返回true或始終返回false。

對于任何非空引用值x，x.equals(null)必須返回false。

equals是所有對象的全局等價關(guān)系。

打破等價關(guān)系

我們必須確保由equals()實現(xiàn)的等價性定義實際上是一個前面定義的等價關(guān)系：自反，對稱和傳遞。

如果不是，那么依賴于等價性的操作(如集合，搜索)將表現(xiàn)出不規(guī)律和不可預(yù)測的行為。

你不想用一個數(shù)據(jù)類型進行編程，其中有時等于b，但b不等于a。

會產(chǎn)生微妙而痛苦的錯誤。

打破哈希表

散列表是映射的表示：將鍵映射到值的抽象數(shù)據(jù)類型。

哈希表提供了恒定的時間查找，所以它們往往比樹或列表執(zhí)行得更好。 密鑰不必訂購，或具有任何特定的屬性，除了提供equals和hashCode。

哈希表如何工作：

它包含一個數(shù)組，該數(shù)組的初始化大小與我們希望插入的元素的數(shù)量相對應(yīng)。

當提供一個鍵和一個值用于插入時，我們計算該鍵的哈希碼，并將其轉(zhuǎn)換為數(shù)組范圍內(nèi)的索引(例如，通過模分割)。 該值然后插入該索引。

哈希表的rep不變量包含密鑰在由其哈希碼確定的時隙中的基本約束。

散列碼的設(shè)計使密鑰均勻分布在索引上。
但偶爾會發(fā)生沖突，并且兩個鍵被放置在相同的索引處。
因此，不是在索引處保存單個值，而是使用哈希表實際上包含一個鍵/值對列表，通常稱為哈希桶。
一個鍵/值對在Java中被簡單地實現(xiàn)為具有兩個字段的對象。
插入時，您將一對添加到由散列碼確定的陣列插槽中的列表中。
對于查找，您散列密鑰，找到正確的插槽，然后檢查每個對，直到找到其中的密鑰等于查詢密鑰的對。

hashCode契約

只要在應(yīng)用程序執(zhí)行過程中多次調(diào)用同一對象時，只要修改了對象的等值比較中未使用的信息，hashCode方法就必須始終返回相同的整數(shù)。

該整數(shù)不需要從應(yīng)用程序的一次執(zhí)行到同一應(yīng)用程序的另一次執(zhí)行保持一致。

如果兩個對象根據(jù)equals(Object)方法相等，則對這兩個對象中的每個對象調(diào)用hashCode方法必須產(chǎn)生相同的整數(shù)結(jié)果。等價的對象必須有相同的的hashCode

根據(jù)equals(Object)方法，如果兩個對象不相等，則不要求對兩個對象中的每一個調(diào)用hashCode方法都必須產(chǎn)生不同的整數(shù)結(jié)果。

但是，程序員應(yīng)該意識到，為不相等的對象生成不同的整數(shù)結(jié)果可能會提高散列表的性能。不相等的對象，也可以映射為同樣的的hashCode，但性能會變差

相等的對象必須具有相同的散列碼

如果你重寫equals，你必須重寫hashCode

不相等的對象應(yīng)該有不同的哈希碼

構(gòu)建時考慮所有的值域

除非對象發(fā)生變化，否則散列代碼不能更改

重寫hashCode()

確保合約滿足的一個簡單而激烈的方法是讓hashCode始終返回一些常量值，因此每個對象的散列碼都是相同的。

這符合Object合同，但是它會帶來災(zāi)難性的性能影響，因為每個密鑰都將存儲在同一個槽中，并且每個查找都會退化為沿著長列表的線性搜索。

標準是計算用于確定相等性的對象的每個組件的哈希代碼(通常通過調(diào)用每個組件的hashCode方法)，然后組合這些哈希碼，引入幾個算術(shù)運算。

打破哈希表

為什么對象合同要求相同的對象具有相同的哈希碼？

如果兩個相等的對象有不同的哈希碼，它們可能被放置在不同的槽中。

因此，如果您嘗試使用與插入值相同的鍵來查找值，則查找可能會失敗。

Object的默認hashCode()實現(xiàn)與其默認的equals()一致：

重寫hashCode()

Java的最新版本現(xiàn)在有一個實用程序方法Objects.hash()，可以更容易地實現(xiàn)涉及多個字段的哈希碼。
請注意，如果您根本不重寫hashCode()，您將從Object獲得一個Object，該Object基于對象的地址。
如果你有等價性的權(quán)利，這將意味著你幾乎肯定會違反合同

兩個相同的對象，一定要有同樣的hashcode。

一般規(guī)則：
覆蓋equals()時總是覆蓋hashCode()。

等價性：當兩個對象無法通過觀察區(qū)分時，它們是等價的。

對于可變對象，有兩種解釋方法：

當它們不能通過不改變對象狀態(tài)的觀察進行區(qū)分時，即只通過調(diào)用觀察者，生產(chǎn)者和創(chuàng)建者方法。這通常被嚴格地稱為觀察等價性，因為它在當前的程序狀態(tài)下測試兩個對象是否“看起來”是相同的。

觀察等價性：在不改變狀態(tài)的情況下，兩個可變對象是否看起來一致

當他們無法通過任何觀察來區(qū)分時，即使狀態(tài)發(fā)生變化。這個解釋允許調(diào)用兩個對象的任何方法，包括增變器。這被稱為行為等價性，因為它測試這兩個對象在這個和所有未來的狀態(tài)中是否會“表現(xiàn)”相同。

行為等價性：調(diào)用對象的任何方法都展示出一致的結(jié)果

注意：對于不可變的對象，觀察和行為的等價性是相同的，因為沒有任何變值器方法。

Java中的可變類型的等價性

對可變類型來說，往往傾向于實現(xiàn)嚴格的觀察等價性

Java對大多數(shù)可變數(shù)據(jù)類型(例如Collections)使用觀察等價性，但其他可變類(如StringBuilder)使用行為等價性。

如果兩個不同的List對象包含相同的元素序列，則equals()報告它們相等。

但是使用觀察等價性導(dǎo)致微妙的錯誤，并且事實上允許我們輕易地破壞其他集合數(shù)據(jù)結(jié)構(gòu)的代表不變量。但在有些時候，觀察等價性可能導(dǎo)致錯誤，甚至可能破壞RI

這是怎么回事？

List 是一個可變對象。 在像List這樣的集合類的標準Java實現(xiàn)中，突變會影響equals()和hashCode()的結(jié)果。
當列表第一次放入HashSet時，它將存儲在當時與其hashCode()結(jié)果相對應(yīng)的哈希桶/散列桶中。
當列表隨后發(fā)生變化時，其hashCode()會發(fā)生變化，但HashSet沒有意識到它應(yīng)該移動到不同的存儲桶中。 所以它再也找不到了。
當equals()和hashCode()可能受突變影響時，我們可以打破使用該對象作為關(guān)鍵字的哈希表的不變性。

如果可變對象用作集合元素，必須非常小心。

如果對象的值以影響等于比較的方式更改，而對象是集合中的元素，則不會指定集合的行為。 如果某個可變的對象包含在集合類中，當其發(fā)生改變后，集合類的行為不確定，務(wù)必小心
不幸的是，Java庫對于可變類的equals()的解釋并不一致。 集合使用觀察等價性，但其他可變類(如StringBuilder)使用行為等價性。 在JDK中，不同的mutable類使用不同的等價性標準...

從這個例子中學到的經(jīng)驗教訓(xùn)

equals()對可變類型，實現(xiàn)行為等價性即可

通常，這意味著兩個引用應(yīng)該是equals()當且僅當它們是同一個對象的別名。也就是說，只有指向同樣內(nèi)存空間的對象，才是相等的。
所以可變對象應(yīng)該繼承Object的equals()和hashCode()。 對可變類型來說，無需重寫這兩個函數(shù)，直接繼承Object對象的兩個方法即可。
對于需要觀察等價性概念的客戶(兩個可變對象在當前狀態(tài)下“看起來”是否相同)，最好定義一個新方法，例如similar()。

equals()和hashCode()的最終規(guī)則

對于不可變類型：

equals()應(yīng)該比較抽象值。 這與equals()應(yīng)該提供行為等價性相同。

hashCode()應(yīng)該將抽象值映射到一個整數(shù)。

所以不可變類型必須覆蓋equals()和hashCode()。

對于可變類型：

equals()應(yīng)該比較引用，就像==一樣。 同樣，這與等價性()應(yīng)該提供行為等價性一樣。

hashCode()應(yīng)該將引用映射為一個整數(shù)。

所以可變類型不應(yīng)該重寫equals()和hashCode()，而應(yīng)該簡單地使用Object提供的默認實現(xiàn)。 不幸的是，Java不遵循這個規(guī)則，導(dǎo)致我們上面看到的陷阱。

對象中的clone()

clone()創(chuàng)建并返回此對象的副本。
“拷貝復(fù)制”的確切含義可能取決于對象的類別。
一般意圖是，對于任何對象x：

x.clone() != x
x.clone().getClass() == x.getClass() 
x.clone().equals(x)

基本類型及其對象類型等價性，例如int和Integer。
如果您創(chuàng)建兩個具有相同值的Integer對象，則它們將相互為equals()。
但是如果x == y呢？
-----錯誤(因為引用等價性)
但是如果(int)x ==(int)y呢？
-----正確

等價性是實現(xiàn)抽象數(shù)據(jù)類型(ADT)的一部分。

等價性應(yīng)該是一種等價關(guān)系(反身，對稱，傳遞)。

相等和散列碼必須相互一致，以便使用散列表(如HashSet和HashMap)的數(shù)據(jù)結(jié)構(gòu)能夠正常工作。

抽象函數(shù)是不變數(shù)據(jù)類型中等式的基礎(chǔ)。

引用等價性是可變數(shù)據(jù)類型中等價性的基礎(chǔ); 這是確保隨時間的一致性并避免破壞散列表的不變式的唯一方法。

減少錯誤保證安全

使用集合數(shù)據(jù)類型(如集合和地圖)需要正確實現(xiàn)相等和散列碼。 編寫測試也是非常理想的。 由于Java中的每個對象都繼承了Object實現(xiàn)，所以不可變類型必須重寫它們。

容易明白

讀過我們規(guī)范的客戶和其他程序員會希望我們的類型實現(xiàn)適當?shù)牡葍r性操作，如果我們不這樣做，會感到驚訝和困惑。

準備好改變

為不可變類型正確實施的等價性將參考等價性與抽象價值的等價性分開，從客戶身上隱藏我們是否共享價值的決定。 選擇可變類型的行為而不是觀察等價性有助于避免意外的別名錯誤。