1、 hashCode() 方法和 equals(Object obj)

在Java中，hashCode() 方法和 equals(Object obj) 方法之間的關(guān)系是緊密相連的，特別是在使用基于哈希的集合（如 HashSet、HashMap、HashTable 等）時。這兩個方法共同決定了對象在哈希表中的存儲和檢索行為。

hashCode() 方法

• hashCode() 方法用于獲取對象的哈希碼。
• 哈希碼是一個整數(shù)，由對象的內(nèi)部地址或根據(jù)對象的字段通過某種算法計算得到。
• 哈希碼的主要目的是在哈希表中減少碰撞（即不同的對象具有相同的哈希碼）的概率，從而提高查找效率。

equals(Object obj) 方法

• equals(Object obj) 方法用于比較兩個對象是否相等。
• 在沒有重寫 equals 方法的情況下，equals 方法比較的是對象的引用（即內(nèi)存地址）。
• 重寫 equals 方法時，通常也會重寫 hashCode 方法，以保持它們之間的一致性關(guān)系。

hashCode() 和 equals(Object obj) 之間的關(guān)系

• 一致性（Consistency）：對于任何非null的引用值x和y，當(dāng)且僅當(dāng) x.equals(y) 為 true 時，x.hashCode() 必須等于 y.hashCode()。
• 不同對象可以有相同的哈希碼：兩個不相等的對象（即 equals(Object obj) 返回 false）可以有相同的哈希碼。
• 如果兩個對象相等：根據(jù) equals(Object obj) 方法的定義，如果兩個對象相等（即 equals(Object obj) 返回 true），那么對這兩個對象中的每一個調(diào)用 hashCode() 方法都必須產(chǎn)生相同的整數(shù)結(jié)果。

為什么需要保持一致性

在基于哈希的集合中，當(dāng)你嘗試添加、查找或刪除一個對象時，集合首先會計算該對象的哈希碼，以決定它在哈希表中的哪個桶（bucket）中。然后，它會在該桶中遍歷所有對象，使用 equals() 方法來查找確切的對象。

如果 hashCode() 方法沒有與 equals() 方法保持一致，那么即使兩個對象通過 equals() 方法被認(rèn)為是相等的，它們也可能被放置在哈希表的不同桶中，導(dǎo)致無法正確找到對象，或者導(dǎo)致哈希表無法正確管理對象的存儲和檢索。

因此，當(dāng)你重寫 equals() 方法時，通常也需要重寫 hashCode() 方法，以確保這兩個方法之間的一致性。

2、不同對象可以有相同的哈希碼的原因

在哈希表中，不同對象可以有相同的哈希碼（也稱為哈希沖突或哈希碰撞）的原因主要歸結(jié)為哈希函數(shù)的有限性和對象的無限性之間的矛盾。

1. 哈希函數(shù)的有限性：哈希函數(shù)的設(shè)計目標(biāo)是將任意長度的輸入（比如對象的狀態(tài)或關(guān)鍵屬性）映射到固定長度的輸出（即哈希碼，通常是整數(shù)）。由于輸出空間是固定的，因此哈希函數(shù)只能產(chǎn)生有限數(shù)量的不同哈希碼。

2. 對象的無限性：在理論上，可以創(chuàng)建的對象數(shù)量是無限的，因為對象的屬性可以有無限多種組合方式。即使只考慮有限的幾個屬性，這些屬性的不同組合也會導(dǎo)致理論上無限多種不同的對象。

3. 概率性：由于哈希函數(shù)的輸出空間有限，而輸入空間（即可能的對象集合）無限，因此必然存在多個不同的對象映射到同一個哈希碼的情況。這是概率上的必然結(jié)果，尤其是在處理大量數(shù)據(jù)時。

4. 性能與空間的權(quán)衡：哈希表的設(shè)計需要在性能（查找、插入和刪除操作的平均時間復(fù)雜度）和空間（哈希表所需的內(nèi)存）之間做出權(quán)衡。使用更復(fù)雜、輸出范圍更大的哈希函數(shù)可以減少哈希沖突，但會增加計算哈希碼所需的時間和空間成本。相反，使用更簡單、輸出范圍較小的哈希函數(shù)可以提高性能，但會增加哈希沖突的概率。

5. 解決哈希沖突：為了處理哈希沖突，哈希表通常使用各種策略，如開放尋址法（open addressing）和鏈地址法（chaining，也稱為分離鏈接法）。在鏈地址法中，每個桶（bucket）實際上是一個鏈表，所有具有相同哈希碼的對象都被添加到同一個鏈表中。這樣，即使不同對象具有相同的哈希碼，它們也可以被正確地存儲和檢索。

因此，不同對象可以有相同的哈希碼是哈希表設(shè)計中的一個固有特性，需要通過合理的哈希函數(shù)和沖突解決策略來管理。

3、介紹開放尋址法（open addressing）和鏈地址法（chaining，也稱為分離鏈接法）

開放尋址法（Open Addressing）和鏈地址法（Chaining，也稱為分離鏈接法）是兩種解決哈希表中哈希沖突的主要方法。下面分別介紹這兩種方法：

1. 開放尋址法（Open Addressing）

定義與原理：

• 開放尋址法是一種哈希表的沖突解決方法，它要求所有的元素都存儲在哈希表的數(shù)組中。當(dāng)發(fā)生沖突時，即兩個不同的元素通過哈希函數(shù)計算得到的哈希值相同時，開放尋址法會尋找數(shù)組中的下一個空閑位置，直到找到一個空槽或遍歷整個表為止。

實現(xiàn)方式：

• 線性探測（Linear Probing）：當(dāng)發(fā)生沖突時，依次檢查下一個位置，直到找到一個空槽或者遍歷整個表。公式為 hash(key, i) = (hash(key) + i) % tableSize。
• 二次探測（Quadratic Probing）：根據(jù)一個二次方程的形式探測下一個位置，公式為 hash(key, i) = (hash(key) + c1 * i + c2 * i^2) % tableSize。
• 雙重哈希（Double Hashing）：使用兩個哈希函數(shù)，第一個哈希函數(shù)計算出位置，如果發(fā)生沖突，則通過第二個哈希函數(shù)計算一個步長，再次尋找下一個位置。公式為 hash(key, i) = (hash1(key) + i * hash2(key)) % tableSize。

優(yōu)勢與劣勢：

• 優(yōu)勢：不需要額外的數(shù)據(jù)結(jié)構(gòu)來存儲相同哈希值的元素，節(jié)省空間。
• 劣勢：可能導(dǎo)致聚集（clustering）問題，即相鄰的位置可能會被頻繁占用，導(dǎo)致查找效率下降。同時，擴容和重新哈希的成本較高。

2. 鏈地址法（Chaining，分離鏈接法）

定義與原理：

• 鏈地址法是一種通過鏈表解決哈希沖突的方法。在哈希表的每個槽位上，不直接存儲數(shù)據(jù)元素，而是存儲一個指向鏈表的指針。所有映射到該槽位的數(shù)據(jù)元素都存儲在鏈表中。

實現(xiàn)方式：

• 當(dāng)哈希函數(shù)計算出的槽位已有元素時，將新元素添加到該槽位對應(yīng)鏈表的末尾。
• 查找、插入和刪除操作都首先定位到槽位，然后在鏈表中進行。

優(yōu)勢與劣勢：

• 優(yōu)勢：處理沖突簡單，只需在鏈表末尾添加新元素。同時，鏈表的長度可以動態(tài)變化，適應(yīng)不同數(shù)量的元素。
• 劣勢：在極端情況下，某些槽位的鏈表可能非常長，導(dǎo)致查找效率下降。此外，鏈表需要額外的空間來存儲指針。

裝填因子：

• 在鏈地址法中，裝填因子α定義為哈希表中關(guān)鍵字記錄總數(shù)N與哈希表大小M的比值，即α=N/M。它反映了哈希表的填充程度，對哈希表的性能有重要影響。

綜上所述，開放尋址法和鏈地址法各有優(yōu)缺點，選擇哪種方法取決于具體的應(yīng)用場景和需求。