如何确保hashCode()与equals()方法一致性？

Question

在覆盖java.lang.Object的equals() 函数时，javadocs建议，

通常情况下需要覆盖hashCode方法，以便维护hashCode方法的一般契约，该契约规定相等的对象必须具有相等的哈希码。

hashCode()方法必须为每个对象返回一个唯一的整数(当基于内存位置比较对象时，这很容易做到，只需返回对象的唯一整数地址)

如何覆盖hashCode()方法，使之仅基于该对象的属性返回唯一的整数？

public class People{
   public String name;
   public int age;

   public int hashCode(){
      // How to get a unique integer based on name and age?
   }
}
/*******************************/
public class App{
   public static void main( String args[] ){
       People mike = new People();
       People melissa = new People();
       mike.name = "mike";
       mike.age = 23;
       melissa.name = "melissa";
       melissa.age = 24;
       System.out.println( mike.hasCode() );  // output?
       System.out.println( melissa.hashCode(); // output?
   }
}

- ForYouOwnGood

Answer 1

对象的哈希码不必完全唯一，只需要对于两个相等的对象返回相同的哈希码即可。有两个不相等的对象返回相同的哈希码是完全合法的。然而，哈希码在一组对象中的分布越独特，就能获得更好的HashMap性能和其他使用hashCode的操作性能。

像IntelliJ IDEA这样的IDE具有内置生成器，用于生成equals和hashCode方法，通常可以为大多数对象生成“足够好”的代码（可能比某些手工编写的过度聪明的哈希函数还要好）。

例如，下面是Idea为您的People类生成的hashCode函数：

public int hashCode() {
    int result = name != null ? name.hashCode() : 0;
    result = 31 * result + age;
    return result;
}

- Marc Novakowski

---

有效但不理想。这被称为哈希冲突。一个好的哈希算法可以最小化冲突，但不需要保证它们不会发生。 - slim

需要澄清的是："相等的对象 => 相等的哈希码"并不等同于"相等的哈希码 => 相等的对象"。不过真正成立的是"不等的哈希码 => 不等的对象"。这意味着，对于任何对象总是返回42的哈希码方法，从定义上来说是一个有效的哈希码方法；只是一个非常糟糕的方法。 - Zach Scrivena

如果您使用集成开发环境计算哈希函数，值得“感性检查”其功能。乘以31（或某些其他质数）通常是可以的，但是如果您有一个字段（例如位字段）可能由2的幂次组成，则不好（因为这会在乘法时将零移位到低位！）。 - Neil Coffey

顺便说一下，Java的哈希表（HashMap等）会重新哈希传入的哈希值以更均匀地分布。因此，尽管努力使值更加唯一有助于防止冲突，但通常不值得花费太多精力使它们分布良好。 - Alex Miller

@Marc，如何告诉Idea生成一个hashcode()实现？命令是什么？ - Geek

Answer 2

另一个问题问是否有一些基本的低级东西所有程序员都应该知道，我认为哈希查找是其中之一。所以这里就开始吧。

哈希表（请注意我没有使用实际的类名）基本上是一个链表数组。要在表中查找某个东西，首先计算该东西的哈希码，然后对表的大小进行取模。这是数组的索引，您会在该索引处得到一个链接列表。接下来遍历该列表，直到找到您的对象。

由于数组检索是O(1)，而链表遍历是O(n)，因此您需要一个创建尽可能随机分布的哈希函数，以便将对象散列到不同的列表中。每个对象都可以返回值0作为其哈希码，并且哈希表仍将起作用，但它基本上是数组元素0的长链接列表。

您通常还希望数组很大，这增加了对象在长度为1的列表中的机会。例如，Java HashMap在映射中的条目数>数组大小的75%时增加数组的大小。这里有一个权衡：您可以拥有具有非常少的条目的巨大数组并浪费内存，或者拥有较小的数组，其中数组中的每个元素都是具有> 1个条目的列表，并浪费时间遍历。完美的哈希将使每个对象分配到数组中的唯一位置，没有浪费空间。

“完美哈希”是一个真正的术语，在某些情况下，您可以创建一个哈希函数，为每个对象提供唯一的数字。只有当您知道所有可能值的集合时才有可能实现这一点。在一般情况下，您无法实现这一点，并且将返回相同的哈希码的一些值。这是简单的数学：如果您有一个长度超过4个字节的字符串，则无法创建唯一的4字节哈希码。

有趣的小事情：哈希数组通常基于质数调整大小，以便在对结果进行取模时获得最佳的随机分配机会，而不管哈希码实际上有多随机。

根据评论进行编辑：

1）链表不是表示具有相同哈希码的对象的唯一方法，尽管这是JDK 1.5 HashMap使用的方法。虽然比简单数组效率低，但在重新哈希时它确实创建了较少的翻转（因为条目可以从一个桶中取消链接并重新链接到另一个桶中）。

2）截至JDK 1.4，HashMap类使用大小为2的幂的数组；在此之前，它使用2^N+1，我认为对于N <= 32是质数。这并不直接加速数组索引，但确实允许使用按位与而不是除法计算数组索引，如Neil Coffey所指出的那样。就个人而言，我会将其视为过早优化，但考虑到HashMap作者列表，我会假设有一些真正的好处。

- kdgregory

---

桶不一定非得是链表，也可以是数组或树等其他数据结构。如果哈希码好（可能需要重新计算），那么使用质数大小的数组并没有太大优势。而使用2的幂次方大小的数组则更容易计算下一个大小，并且索引速度更快。 - Tom Hawtin - tackline

还有探测数组（例如在Sun版本的ThreadLocal和IdentityHashMap中使用）。与桶不同，发生冲突后，使用某些算法来探测数组中的其他条目。 - Tom Hawtin - tackline

在这两个方面都是正确的。实现“桶列表”的方法有很多种，我觉得链表最容易理解。至于非质数数组，关键在于“好的哈希码”，这在通用编程环境中并不一定成立。 - kdgregory

Java的哈希映射不使用质数作为桶的数量：它们使用2的幂，允许在计算桶编号时进行AND操作而不是除法。通过将哈希码的高位与低位混合来弥补具有非随机低位的哈希码的危险。 - Neil Coffey

值得注意的是，“随机分布”在这里是有歧义的；如果您的分布仅在{0}上有支持（例如，离散点分布、连续Dirac分布），那么总返回0的哈希函数确实会产生“随机分布”的值。您所寻找的是一个函数，其值在可能的32位整数范围内尽可能“均匀地”随机分布。 - kbolino

Answer 3

我不会详细介绍hashCode的唯一性，因为Marc已经解决了这个问题。对于你的People类，你首先需要确定一个人的相等意味着什么。也许相等仅基于他们的姓名，也许基于姓名和年龄。这将是特定于领域的。假设相等基于姓名和年龄。你重写的equals看起来像这样：

public boolean equals(Object obj) {
    if (this==obj) return true;
    if (obj==null) return false;
    if (!(getClass().equals(obj.getClass())) return false;
    Person other = (Person)obj;
    return (name==null ? other.name==null : name.equals(other.name)) &&
        age==other.age;
}

任何时候你重写equals方法，都必须重写hashCode方法。此外，hashCode方法在计算时不能使用比equals方法更多的字段。大多数情况下，你需要添加或异或各个字段的哈希码（hashCode应该计算速度快）。因此，一个有效的hashCode方法可能如下所示：

public int hashCode() {
    return (name==null ? 17 : name.hashCode()) ^ age;
}

请注意，以下代码无效，因为它使用了一个equals没有使用的字段（height）。在这种情况下，两个“equals”对象可能具有不同的哈希码。

public int hashCode() {
    return (name==null ? 17 : name.hashCode()) ^ age ^ height;
}

此外，两个不相等的对象具有相同的哈希码也是完全有效的：

public int hashCode() {    
    return age;    
}

在这种情况下，30岁的简不等于30岁的鲍勃，但他们的哈希码都是30。虽然有效，但在基于哈希的集合中，这是性能不佳的。

- Steve Kuo

Answer 4

通常情况下，哈希码不可能是唯一的，因为值的数量比可能的哈希码（整数）要多。 一个良好的哈希码能够很好地分布在整数上。 一个糟糕的哈希码总是可以给出相同的值，并且仍然在逻辑上是正确的，只是会导致效率低下的哈希表。

相等的值必须具有相同的哈希值才能使哈希表正常工作。 否则，您可能会将一个键添加到哈希表中，然后尝试通过具有不同哈希码但相等值的值进行查找，但是找不到该键。 或者您可以使用具有不同哈希码但相等值的值来放置一个相等值，并在哈希表的不同位置上拥有两个相等的值。

实际上，您通常会选择选定字段的子集来考虑hashCode()和equals()方法。

- starblue

Answer 5

这是文档告诉我们关于哈希码方法的内容

@ javadoc

在 Java 应用程序执行期间，如果对同一对象多次调用 hashCode 方法，则只要 equals 比较中使用的信息未修改，hashCode 方法就必须始终返回相同的整数。此整数不需要在应用程序的一个执行到另一个执行之间保持一致。

- M. Atif Riaz

Answer 6

有一个业务键的概念，它确定了相同类型的单独实例的唯一性。每个特定类型（类）都应该有一个业务键，它代表一个或多个类字段，用于模拟目标域中的单独实体（例如车队系统中的车辆）。equals()和hasCode()方法都应该使用组成业务键的字段来实现。这样可以确保两种方法彼此一致。

- 01es

Answer 7

我认为你误解了它。哈希码不必对每个对象都唯一（毕竟，它是一个哈希码），但显然你不希望它对所有对象相同。但是，对于所有相等的对象，您需要使其相同，否则标准集合等内容将无法正常工作（例如，您在哈希集中查找某些内容但却找不到它）。

对于简单属性，一些IDE具有哈希码函数生成器。

如果您不使用IDE，请考虑使用Apache Commons和HashCodeBuilder类。

- Uri

Answer 8

hashCode 的唯一合同义务是保持一致性。用于创建 hashCode 值的字段必须与用于 equals 方法的字段相同或是其子集。这意味着对所有值返回 0 是有效的，尽管不是高效的。

可以通过单元测试来检查 hashCode 是否一致。我编写了一个名为 EqualityTestCase 的抽象类，它执行了一些 hashCode 检查。只需扩展测试用例并实现两个或三个工厂方法即可。该测试会粗略地测试 hashCode 是否高效。

- brianegge