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

Question

如果我覆盖一个类的任一方法,它必须确保如果A.equals(B) = true那样(A.hashCode() == B.hashCode)也必须为true.

有人能告诉我一个简单的例子,如果这被违反,会导致问题吗？我认为如果你使用该类作为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使用的方法(可能是最常见的)是bucketing.具有相同掩码hashCode的所有条目都放在某种列表中.

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

1. 计算掩码哈希码;
2. 找到合适的桶;
3. 如果它是空的,则找不到钥匙;
4. 如果is不为空​​,则遍历桶中的所有条目,检查equals().

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

你可以对此做一些观察.

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

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

Answer 2

这将在第8项中讨论:当覆盖 Joshua Bloch的Effective Java 等于时,总是覆盖hashCode:

一个常见的错误来源是无法覆盖hashCode方法.您必须覆盖覆盖等于的每个类中的hashCode.如果不这样做,将导致违反Object.hashCode的一般合同,这将阻止您的类与所有基于散列的集合(包括HashMap,HashSet和Hashtable)一起正常运行.

这是从java.lang.Object规范复制的契约:

• 每当在执行应用程序期间多次在同一对象上调用它时,hashCode方法必须始终返回相同的整数,前提是不修改对象的equals比较中使用的信息.从应用程序的一次执行到同一应用程序的另一次执行,该整数不需要保持一致.

• 如果两个对象根据equals(Object)方法相等,则对两个对象中的每一个调用hashCode方法必须生成相同的整数结果.

• 如果两个对象根据equals(Object)方法不相等则不是必需的,则对两个对象中的每一个调用hashCode方法必须产生不同的整数结果.但是,程序员应该知道为不等对象生成不同的整数结果可能会提高哈希表的性能.

当您未能覆盖hashCode时违反的密钥配置是第二个:Equal对象必须具有相同的哈希码.根据类的equals方法,两个不同的实例在逻辑上可能相等,但是对于Object类的hashCode方法,它们只是两个没有多少共同点的对象.因此,对象的hashCode方法返回两个看似随机的数字,而不是合同要求的两个相等的数字.

例如,考虑以下简单的PhoneNumber类,其equals方法是根据第7项中的配方构造的:

public final class PhoneNumber {
     private final short areaCode;
     private final short exchange;
     private final short extension;

     public PhoneNumber(int areaCode, int exchange,
                           int extension) {
         rangeCheck(areaCode,   999, "area code");
         rangeCheck(exchange,   999, "exchange");
         rangeCheck(extension, 9999, "extension");

         this.areaCode = (short) areaCode;
         this.exchange = (short) exchange;
         this.extension = (short) extension;
     }

     private static void rangeCheck(int arg, int max,
                                 String name) {
         if (arg < 0 || arg > max)
             throw new IllegalArgumentException(name +": " + arg);
     }

     public boolean equals(Object o) {
         if (o == this)
             return true;
         if (!(o instanceof PhoneNumber))
             return false;
         PhoneNumber pn = (PhoneNumber)o;
         return pn.extension == extension &&
                pn.exchange == exchange &&
                pn.areaCode == areaCode;
     }

     // No hashCode method!
    ... // Remainder omitted
}

假设您尝试将此类与HashMap一起使用:

Map m = new HashMap();
m.put(new PhoneNumber(408, 867, 5309), "Jenny");

此时,您可能希望 m.get(new PhoneNumber(408 , 867, 5309))返回"Jenny",但它会返回null.请注意,涉及两个PhoneNumber实例:一个用于插入HashMap,另一个相等的实例用于(尝试)检索.PhoneNumber类未能覆盖hashCode导致两个相等的实例具有不相等的哈希码,这违反了hashCode契约.因此,get方法在与put方法存储的散列桶不同的散列桶中查找电话号码.修复此问题就像为PhoneNumber类提供正确的hashCode方法一样简单.[...]

有关完整内容,请参阅第3章.