:::info
<a href="/@TFA101/CherryJava" target="_self">< :notebook_with_decorative_cover: [共享目錄] Java 2 學習筆記
</a>
:::

# 模組19 集合物件唯一性（hashCode()、equals()）

Set 集合相關的類別，雖然在順序性上並不是所有類別都能保證，但可以確定的是它們全都有**保證不重複**（唯一）的特性：

* Set（不保證順序）
* SortedSet（介面）
* **TreeSet**（保證順序）
* HashSet（不保證順序）
* **LinkedHashSet**（保證順序，依加入先後）

## Set 相關集合判斷元素不重複的依據

**繼承自 Object** 的 2 個方法，能讓 Set 集合比對「準備存入的元素，是否和已經存在集合內的元素」重複：

1. `hashCode()`：模糊比對
2. `equals()` ：明確比對

:::warning
:mega: <font color="red">**比對絕對會依照此先後順序！**</font>

`hashCode()` 若**相同**，才會再用 `equals()` 檢驗。一開始就用 `equals()` 太消耗資源了。
:::

Object 的 `equals()` 方法，為了讓所有物件都可以適用，只簡單的比較位址是否相同（`==`）的條件，因為位址相同的兩個物件必然相同。

但位址不同的物件，無法單就這個條件判斷是否重複，所以必須 Override 掉這兩個方法，才能定義什麼叫做「重複的物件」。

## 模糊比對：`hashCode()` 雜湊碼比較

每個 Java **物件**都擁有繼承自 Object 的 `HashCode()` 方法，可以藉由它取得一個整數的資料。

基本型別就用它們自己的值，和一個質數一起做乘法運算：數字相關的型別用數值，char 用 unicode 的 byte 值、boolean 是 1 與 0。API 已有的單一物件類別通常已經也已經幫你 override 好，如 String 類別。

有多個屬性的物件，則通常必須拿每個屬性的 `hashCode()` ，和一個質數一起做累積的相乘，以避免因為乘出公倍數的關係得到相同的結果（共用雜湊桶，後述）；做乘法運算的原因則是讓數字變大（不然桶子太少了很可能重複裝到）。

### 雜湊桶（Hash Bucket）

Java 在將集合加入元素前，就會呼叫這個預計要加入的物件的 `hashCode()` 方法，取得該物件運算完的整數資料。

這個整數資料，可以找到一個對應編號的雜湊桶（Hash Bucket）：

1. **如果雜湊桶裡面是空的**：代表前面沒有物件和打算加入物件的屬性是相同的，這時候就可以直接加入這個集合，不需要再去呼叫 `equals()` 方法做明確比對。
2. **如果雜湊桶裡面已經有物件**：Java 會進一步去呼叫 `equals()` 方法檢查裡面的物件和打算加入的物件完全相同，這樣就可以確定重複了，不允許存入。

理由其實很簡單：

> 所有屬性相同 → 所有屬性的 `hashCode()` 相同
> → 所有屬性的 `hashCode()` 乘以質數後算出相同的整數資料
> → 才有可能通往同一個雜湊桶

### 應該覆寫些什麼？

依照前面的敘述，`hashCode()` 就是在幫你檢查物件裡面的屬性是不是和別人完全一樣，找雜湊桶時，雜湊桶變多、不產生公倍數也需要考量。所以大致上流程如下：

1. **決定好要比較的物件屬性**：
要和Override `equals()` 方法的屬性相同；如果不多，全放就對了。
<div style="margin-bottom:16px;" title="保持間距用"></div>

2. **選擇一個質數，與選擇的屬性作累積相乘**：
擴大運算結果，雜湊桶變多了，就可以避免撞雜湊桶。
<div style="margin-bottom:16px;" title="保持間距用"></div>

3. **回傳累積相乘的結果**：
讓 Java 去檢查這個數值對應的雜湊桶裡面有沒有東西，決定要不要呼叫 `equals()`。

### Override `hashCode()` 的範例

// 前略...
@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + dest.hashCode();
    result = prime * result + number;
    result = prime * result + (int)price;
    result = prime * result + start.hashCode();
    result = prime * result + type.hashCode();
    return result;
}

計算應該比逐一條件比對更加節能，所以先在模糊比對階段確定沒有重複，直接存進來，可省下不少比對的效能。

## 明確比對：`equals()` 相等比較

但所有屬性相同的物件是不是同一個物件？不一定！假設我 new 出了兩個屬性完全一模一樣的物件，就是一樣的嗎？它們光位址就不一樣了啊！

所以才要靠 `equals()` 做進一步的檢測。

### Override `equals()` 的範例

`equals()` 的覆寫應該就不用講那麼多，直接來就對了。

// 前略...
@Override
public boolean equals(Object obj) {
    if (this == obj)
        return true;
		
    if (obj != null  && getClass() == obj.getClass() ) {
        Train train = (Train) obj;
        
        if (this.number == train.number && this.type == train.type && this.start == train.start && this.dest == train.dest && this.price == train.price) 
            return true;
            
    }
    return false;
}
	

:::warning
:mega: <font color="red">**強制轉型的理由**</font>：
1. **與 Object 設計方法有關**：
* 為了讓所有物件都可以傳進來，參數才會是`Object obj`，override 必須和父類別完全一致，但不轉型又沒有比較基礎（先求進來，再求轉回原本型別）。
* Object 不支援泛型，沒有先限制型別這種事情。

2. 集合什麼物件都可以存，傳入當作參數的物件，來源可能不同。但在這邊先放了 if 做條件檢測，如果檢查出兩者類別相同，就可以放心的強制轉型，**使傳入參數從多型 Object 轉回原來的型別**。來源相同，比較才有意義（來源的類別不同就直接跳出去回傳 false 就好，類別不同哪可能是同個物件啦）。
:::

## 參考資料

補充一些不錯的參考資料：
1. [Effective Java Item11 - 覆蓋equals時總要覆蓋hashCode](https://www.jyt0532.com/2018/06/23/always-override-hashcode-when-you-override-equals/)
2. [物件相等性](https://openhome.cc/Gossip/JavaEssence/ObjectEquality.html)