23

当覆盖 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?
   }
}
4

8 回答 8

29

它并不是说一个对象的哈希码必须是完全唯一的，只是说两个相等对象的哈希码返回相同的哈希码。让两个不相等的对象返回相同的哈希码是完全合法的。但是，哈希码分布在一组对象上的唯一性越强，您从 HashMap 和其他使用哈希码的操作中获得的性能就越好。

IntelliJ Idea 等 IDE 具有内置的 equals 和 hashCode 生成器，通常可以很好地为大多数对象提供“足够好”的代码（并且可能比一些手工制作的过于聪明的哈希函数更好）。

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

public int hashCode() {
    int result = name != null ? name.hashCode() : 0;
    result = 31 * result + age;
    return result;
}
于 2009-01-04T01:39:43.970 回答
9

我不会深入讨论 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没有（高度）的字段。在这种情况下，两个“等于”对象可能有不同的哈希码。

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

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

public int hashCode() {    
    return age;    
}

在这种情况下，Jane 的 30 岁不等于 Bob 的 30 岁，但它们的哈希码都是 30。虽然有效，但对于基于哈希的集合的性能而言，这是不可取的。

于 2009-01-04T01:48:43.047 回答
8

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

哈希表（注意我没有使用实际的类名）基本上是一个链表数组。要在表中查找某些内容，您首先计算该内容的哈希码，然后根据表的大小对其进行修改。这是数组的索引，您会在该索引处获得一个链表。然后遍历列表，直到找到对象。

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

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

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

一个有趣的花絮：哈希数组的大小通常基于质数，以便在您修改结果时为随机分配提供最佳机会，而不管哈希码的真正随机性如何。

根据评论编辑：

1) 链表不是表示具有相同哈希码的对象的唯一方法，尽管这是 JDK 1.5 HashMap 使用的方法。尽管内存效率比简单数组低，但可以说它在重新散列时确实会产生更少的流失（因为条目可以从一个存储桶中取消链接并重新链接到另一个存储桶）。

2) 从 JDK 1.4 开始，HashMap 类使用大小为 2 的幂的数组；在此之前，它使用 2^N+1，我认为它是 N <= 32 的质数。这本身并不能加速数组索引，但确实允许使用按位与而不是除法来计算数组索引，正如尼尔科菲所指出的那样。就个人而言，我认为这是过早的优化，但鉴于 HashMap 上的作者列表，我会假设有一些真正的好处。

于 2009-01-04T03:23:53.040 回答
1

一般来说，哈希码不能是唯一的，因为有比可能的哈希码（整数）更多的值。一个好的哈希码可以很好地将值分布在整数上。一个坏的总是可以给出相同的值并且在逻辑上仍然是正确的，它只会导致不可接受的低效哈希表。

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

在实践中，您通常会在 hashCode() 和 equals() 方法中选择要考虑的字段子集。

于 2009-01-04T08:48:43.103 回答
0

我想你误会了。哈希码不必对每个对象都是唯一的（毕竟，它是一个哈希码），尽管您显然不希望它对所有对象都相同。但是，您确实需要它与所有相等的对象相同，否则标准集合之类的东西将不起作用（例如，您会在哈希集中查找某些内容但找不到它）。

对于简单的属性，一些 IDE 具有哈希码函数构建器。

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

于 2009-01-04T01:46:50.723 回答
0

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

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

于 2009-10-18T22:33:08.093 回答
0

这就是文档告诉我们的哈希码方法

@javadoc

Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.

于 2010-01-02T15:17:24.240 回答
0

There is a notion of business key, which determines uniqueness of separate instances of the same type. Each specific type (class) that models a separate entity from the target domain (e.g. vehicle in a fleet system) should have a business key, which is represented by one or more class fields. Methods equals() and hasCode() should both be implemented using the fields, which make up a business key. This ensures that both methods consistent with each other.

于 2010-12-18T19:58:00.237 回答