在Java中,为什么equals()和hashCode()必须一致？

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(),然后根据存储区的大小获取掩码.如果您(按位)和hashCode()与15(0x0F),您将获得最后4位,等于0到15之间的数字(包括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使用的方法(可能是最常见的)是bucketing.具有相同掩码hashCode的所有条目都放在某种列表中.

因此,要查找给定键是否已在地图中：

>计算屏蔽的哈希码;
>找到合适的水桶;
>如果它是空的,则找不到钥匙;
>如果is不为空??,则遍历存储桶中的所有条目,检查equals().

查看存储桶是一个线性(O(n))操作,但它只是一个小子集.哈希码桶确定基本上是常数(O(1)).如果存储桶足够小,则通常将对HashMap的访问描述为“接近O(1)”.

你可以对此做一些观察.

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

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