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

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

hashCode() 方法

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

equals(Object obj) 方法

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

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

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

為什么需要保持一致性

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

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

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

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

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

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

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

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

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

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

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

3、介紹開(kāi)放尋址法（open addressing）和鏈地址法（chaining，也稱(chēng)為分離鏈接法）

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

1. 開(kāi)放尋址法（Open Addressing）

定義與原理：

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

實(shí)現(xiàn)方式：

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

優(yōu)勢(shì)與劣勢(shì)：

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

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

定義與原理：

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

實(shí)現(xiàn)方式：

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

優(yōu)勢(shì)與劣勢(shì)：

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

裝填因子：

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

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