在Java中，为什么equals（）和hashCode（）必须一致？ [英] In Java, why must equals() and hashCode() be consistent?

问题描述

如果我覆盖某个类的任一方法，它必须确保如果 A.equals（B）= true 然后（A.hashCode （）== B.hashCode）也必须为真。

If I override either method on a class, it must make sure that if A.equals(B) = true then (A.hashCode() == B.hashCode) must also be true.

有人可以给我一个简单的例子，如果这被违反，那么'会引起问题吗？我认为如果你使用该类作为Hashmap的键类型有什么关系？

Can someone show me a simple example where if this is violated, it'll cause a problem? I think it has something to do with if you use that class as the type of keys to Hashmap?

推荐答案

当然：

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;
  }
}

with：

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

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

Technically that should be true because m == 3 in both cases.

通常，HashMap的工作方式如下：它具有可变数量的通常称为桶的东西。桶的数量可以随着时间的推移而变化（添加和删除条目），但总是2的幂。

In general a HashMap works like this: it has a variable number of what are commonly called "buckets". The number of buckets can change over time (as entries are added and removed) but it is always a power of 2.

让我们说给定的 HashMap 有16个桶。当您调用put（）添加条目时，将计算密钥的hashCode（），然后根据存储桶的大小获取掩码。如果你（按位）和hashCode（）与15（0x0F）你将获得最后4位，等于0到15之间的数字包括：

Let's say a given HashMap has 16 buckets. When you call put() to add an entry, the hashCode() of the key is calculated and then a mask is taken depending on the size of the buckets. If you (bitwise) AND the hashCode() with 15 (0x0F) you will get the last 4 bits, equaling a number between 0 and 15 inclusive:

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的所有条目都放在某种列表中。

Now if there is already an entry in that bucket you have what's called a collision. There are multiple ways of dealing with this but the one used by HashMap (and is probably the most common overall) is bucketing. All the entries with the same masked hashCode are put in a list of some kind.

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

So to find if a given key is in the map already:

1. 计算蒙面哈希码;


2. 找到合适的桶;


3. 如果它为空，则找不到密钥;


4. 如果is不为空​​，则遍历桶中的所有条目，检查equals（）。

1. Calculate the masked hash code;
2. Find the appropriate bucket;
3. If it's empty, key not found;
4. If is isn't empty, loop through all entries in the bucket checking equals().

查看存储桶是一个线性（O（n））操作，但它只是一小部分。哈希码桶确定基本上是常数（O（1））。如果存储桶足够小，那么对HashMap的访问通常被描述为接近O（1）。

Looking through a bucket is a linear (O(n)) operation but it's on a small subset. The hashcode bucket determination is essentially constant (O(1)). If buckets are sufficiently small then access to a HashMap is usually described as "near O(1)".

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

You can make a couple of observations about this.

首先，如果你有一堆对象都返回42作为他们的哈希码，那么 HashMap 仍然有用，但它会作为一个昂贵的名单运作。访问将是O（n）（因为无论桶的数量如何，所有内容都将在同一个桶中）。我实际上在接受采访时被问过这个问题。

Firstly, if you have a bunch of objects that all return 42 as their hash code a HashMap will still work but it will operate as an expensive list. Access will be O(n) (as everything will be in the same bucket regardless of the number of buckets). I've actually been asked this in an interview.

其次，如果两个对象相等（意味着a。等于），则返回原点。 （b）== b.equals（a）== true ）但是有不同的哈希码，那么 HashMap 将会查找（可能）错误的存储桶导致不可预测和未定义的行为。

Secondly, returning to your original point, if two objects are equal (meaning a.equals(b) == b.equals(a) == true) but have different hash codes then the HashMap will go looking in (probably) the wrong bucket resulting in unpredictable and undefined behaviour.

这篇关于在Java中，为什么equals（）和hashCode（）必须一致？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！