java之hashCode() 方法和 equals(Object obj) 方法之间的关系

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

在Java中，hashCode() 方法和 equals(Object obj) 方法之间的关系是紧密相连的，特别是在使用基于哈希的集合（如 HashSet、HashMap、HashTable 等）时。这两个方法共同决定了对象在哈希表中的存储和检索行为。

hashCode() 方法

• hashCode() 方法用于获取对象的哈希码。
• 哈希码是一个整数，由对象的内部地址或根据对象的字段通过某种算法计算得到。
• 哈希码的主要目的是在哈希表中减少碰撞（即不同的对象具有相同的哈希码）的概率，从而提高查找效率。

equals(Object obj) 方法

• equals(Object obj) 方法用于比较两个对象是否相等。
• 在没有重写 equals 方法的情况下，equals 方法比较的是对象的引用（即内存地址）。
• 重写 equals 方法时，通常也会重写 hashCode 方法，以保持它们之间的一致性关系。

hashCode() 和 equals(Object obj) 之间的关系

• 一致性（Consistency）：对于任何非null的引用值x和y，当且仅当 x.equals(y) 为 true 时，x.hashCode() 必须等于 y.hashCode()。
• 不同对象可以有相同的哈希码：两个不相等的对象（即 equals(Object obj) 返回 false）可以有相同的哈希码。
• 如果两个对象相等：根据 equals(Object obj) 方法的定义，如果两个对象相等（即 equals(Object obj) 返回 true），那么对这两个对象中的每一个调用 hashCode() 方法都必须产生相同的整数结果。

为什么需要保持一致性

在基于哈希的集合中，当你尝试添加、查找或删除一个对象时，集合首先会计算该对象的哈希码，以决定它在哈希表中的哪个桶（bucket）中。然后，它会在该桶中遍历所有对象，使用 equals() 方法来查找确切的对象。

如果 hashCode() 方法没有与 equals() 方法保持一致，那么即使两个对象通过 equals() 方法被认为是相等的，它们也可能被放置在哈希表的不同桶中，导致无法正确找到对象，或者导致哈希表无法正确管理对象的存储和检索。

因此，当你重写 equals() 方法时，通常也需要重写 hashCode() 方法，以确保这两个方法之间的一致性。

2、不同对象可以有相同的哈希码的原因

在哈希表中，不同对象可以有相同的哈希码（也称为哈希冲突或哈希碰撞）的原因主要归结为哈希函数的有限性和对象的无限性之间的矛盾。

1. 哈希函数的有限性：哈希函数的设计目标是将任意长度的输入（比如对象的状态或关键属性）映射到固定长度的输出（即哈希码，通常是整数）。由于输出空间是固定的，因此哈希函数只能产生有限数量的不同哈希码。

2. 对象的无限性：在理论上，可以创建的对象数量是无限的，因为对象的属性可以有无限多种组合方式。即使只考虑有限的几个属性，这些属性的不同组合也会导致理论上无限多种不同的对象。

3. 概率性：由于哈希函数的输出空间有限，而输入空间（即可能的对象集合）无限，因此必然存在多个不同的对象映射到同一个哈希码的情况。这是概率上的必然结果，尤其是在处理大量数据时。

4. 性能与空间的权衡：哈希表的设计需要在性能（查找、插入和删除操作的平均时间复杂度）和空间（哈希表所需的内存）之间做出权衡。使用更复杂、输出范围更大的哈希函数可以减少哈希冲突，但会增加计算哈希码所需的时间和空间成本。相反，使用更简单、输出范围较小的哈希函数可以提高性能，但会增加哈希冲突的概率。

5. 解决哈希冲突：为了处理哈希冲突，哈希表通常使用各种策略，如开放寻址法（open addressing）和链地址法（chaining，也称为分离链接法）。在链地址法中，每个桶（bucket）实际上是一个链表，所有具有相同哈希码的对象都被添加到同一个链表中。这样，即使不同对象具有相同的哈希码，它们也可以被正确地存储和检索。

因此，不同对象可以有相同的哈希码是哈希表设计中的一个固有特性，需要通过合理的哈希函数和冲突解决策略来管理。

3、介绍开放寻址法（open addressing）和链地址法（chaining，也称为分离链接法）

开放寻址法（Open Addressing）和链地址法（Chaining，也称为分离链接法）是两种解决哈希表中哈希冲突的主要方法。下面分别介绍这两种方法：

1. 开放寻址法（Open Addressing）

定义与原理：

• 开放寻址法是一种哈希表的冲突解决方法，它要求所有的元素都存储在哈希表的数组中。当发生冲突时，即两个不同的元素通过哈希函数计算得到的哈希值相同时，开放寻址法会寻找数组中的下一个空闲位置，直到找到一个空槽或遍历整个表为止。

实现方式：

• 线性探测（Linear Probing）：当发生冲突时，依次检查下一个位置，直到找到一个空槽或者遍历整个表。公式为 hash(key, i) = (hash(key) + i) % tableSize。
• 二次探测（Quadratic Probing）：根据一个二次方程的形式探测下一个位置，公式为 hash(key, i) = (hash(key) + c1 * i + c2 * i^2) % tableSize。
• 双重哈希（Double Hashing）：使用两个哈希函数，第一个哈希函数计算出位置，如果发生冲突，则通过第二个哈希函数计算一个步长，再次寻找下一个位置。公式为 hash(key, i) = (hash1(key) + i * hash2(key)) % tableSize。

优势与劣势：

• 优势：不需要额外的数据结构来存储相同哈希值的元素，节省空间。
• 劣势：可能导致聚集（clustering）问题，即相邻的位置可能会被频繁占用，导致查找效率下降。同时，扩容和重新哈希的成本较高。

2. 链地址法（Chaining，分离链接法）

定义与原理：

• 链地址法是一种通过链表解决哈希冲突的方法。在哈希表的每个槽位上，不直接存储数据元素，而是存储一个指向链表的指针。所有映射到该槽位的数据元素都存储在链表中。

实现方式：

• 当哈希函数计算出的槽位已有元素时，将新元素添加到该槽位对应链表的末尾。
• 查找、插入和删除操作都首先定位到槽位，然后在链表中进行。

优势与劣势：

• 优势：处理冲突简单，只需在链表末尾添加新元素。同时，链表的长度可以动态变化，适应不同数量的元素。
• 劣势：在极端情况下，某些槽位的链表可能非常长，导致查找效率下降。此外，链表需要额外的空间来存储指针。

装填因子：

• 在链地址法中，装填因子α定义为哈希表中关键字记录总数N与哈希表大小M的比值，即α=N/M。它反映了哈希表的填充程度，对哈希表的性能有重要影响。

综上所述，开放寻址法和链地址法各有优缺点，选择哪种方法取决于具体的应用场景和需求。