在Java中，为什么equals（）和hashCode（）必须一致？

Question

如果我重写一个类两种方法，它必须确保，如果A.equals(B) == true那么A.hashCode() == B.hashCode也必须是真实的。

有人可以告诉我一个简单的示例，如果违反了该示例，将会引起问题吗？我认为这与您使用该类作为Hashmap的键类型有关吗？

Answer 1

当然：

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使用的方法（可能是最常见的方法）是存储 桶
。具有相同被屏蔽的hashCode的所有条目都放在某种列表中。

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

1. 计算被屏蔽的哈希码；
2. 找到合适的桶；
3. 如果为空，则找不到密钥；
4. 如果不为空，则循环遍历存储桶中的所有条目，检查equals（）。

通过存储桶查看是线性（O（n））操作，但它位于较小的子集上。哈希码桶确定基本上是常数（O（1））。如果存储桶足够小，则通常将对HashMap的访问描述为“在O（1）附近”。

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

首先，如果您有一堆全部返回42作为其哈希码的对象，a
HashMap仍然可以工作，但它将作为昂贵的列表运行。访问将是O（n）（因为所有内容都将在同一个存储桶中，而不管存储桶的数量如何）。实际上在面试中有人问过我。

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