gpt4 book ai didi

java - 在Java中,为什么equals()和hashCode()必须保持一致?

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:39:43 27 4
gpt4 key购买 nike

如果我重写类中的任何一个方法,它必须确保如果A.equals(B) == true then A.hashCode() == B.hashCode 也必须为真。

谁能告诉我一个简单的例子,如果违反了这一点,它会导致问题吗?我觉得跟你用那个class作为Hashmap的key类型有关系吗?

最佳答案

当然:

public class Test {
private final int m, n;

public Test(int m, int n) {
this.m = m;
this.n = n;
}

public int hashCode() { return n * m; }

public boolean equals(Object ob) {
if (ob.getClass() != Test.class) return false;
Test other = (Test)ob;
return m == other.m;
}
}

与:

Set<Test> set = new HashSet<Test>();
set.put(new Test(3,4));
boolean b = set.contains(new Test(3, 10)); // false

从技术上讲,这应该是正确的,因为在这两种情况下 m == 3。

一般来说,HashMap 是这样工作的:它有数量可变的通常称为“桶”的东西。桶的数量会随时间变化(随着条目的添加和删除),但它始终是 2 的幂。

假设给定的 HashMap 有 16 个桶。当您调用 put() 添加条目时,会计算键的 hashCode(),然后根据桶的大小采用掩码。如果您(按位)AND hashCode() 与 15 (0x0F),您将获得最后 4 位,等于 0 到 15 之间的数字:

int factor = 4;
int buckets = 1 << (factor-1) - 1; // 16
int mask = buckets - 1; // 15
int code = key.hashCode();
int dest = code & mask; // a number from 0 to 15 inclusive

现在,如果该存储桶中已经有一个条目,您就会遇到所谓的碰撞。有多种方法可以处理此问题,但 HashMap 使用的方法(并且可能是最常见的一种)是分桶。所有具有相同掩码哈希码的条目都放在某种列表中。

所以要查找给定的键是否已经在映射中:

  1. 计算掩码哈希码;
  2. 找到合适的桶;
  3. 如果为空,则没有找到key;
  4. 如果 is 不为空,则遍历存储桶中的所有条目以检查 equals()。

查看桶是一个线性 (O(n)) 操作,但它在一个小子集上。哈希码桶的确定本质上是恒定的 (O(1))。如果桶足够小,那么访问 HashMap 通常被描述为“接近 O(1)”。

您可以对此进行一些观察。

首先,如果您有一堆对象都返回 42 作为它们的哈希码,HashMap 仍然可以工作,但它将作为一个昂贵的列表运行。访问将是 O(n)(因为无论桶的数量如何,所有内容都将在同一个桶中)。事实上,我在一次采访中被问到过这个问题。

其次,回到你原来的观点,如果两个对象相等(意思是 a.equals(b) == b.equals(a) == true)但是有不同的哈希码然后HashMap 将(可能)查找错误的存储桶,从而导致不可预测和未定义的行为。

关于java - 在Java中,为什么equals()和hashCode()必须保持一致?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1678205/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com