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、不同对象可以有相同的哈希码的原因
在哈希表中,不同对象可以有相同的哈希码(也称为哈希冲突或哈希碰撞)的原因主要归结为哈希函数的有限性和对象的无限性之间的矛盾。
哈希函数的有限性:哈希函数的设计目标是将任意长度的输入(比如对象的状态或关键属性)映射到固定长度的输出(即哈希码,通常是整数)。由于输出空间是固定的,因此哈希函数只能产生有限数量的不同哈希码。
对象的无限性:在理论上,可以创建的对象数量是无限的,因为对象的属性可以有无限多种组合方式。即使只考虑有限的几个属性,这些属性的不同组合也会导致理论上无限多种不同的对象。
概率性:由于哈希函数的输出空间有限,而输入空间(即可能的对象集合)无限,因此必然存在多个不同的对象映射到同一个哈希码的情况。这是概率上的必然结果,尤其是在处理大量数据时。
性能与空间的权衡:哈希表的设计需要在性能(查找、插入和删除操作的平均时间复杂度)和空间(哈希表所需的内存)之间做出权衡。使用更复杂、输出范围更大的哈希函数可以减少哈希冲突,但会增加计算哈希码所需的时间和空间成本。相反,使用更简单、输出范围较小的哈希函数可以提高性能,但会增加哈希冲突的概率。
解决哈希冲突:为了处理哈希冲突,哈希表通常使用各种策略,如开放寻址法(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。它反映了哈希表的填充程度,对哈希表的性能有重要影响。
综上所述,开放寻址法和链地址法各有优缺点,选择哪种方法取决于具体的应用场景和需求。