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

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

Marc Novakow.. 28

它没有说对象的哈希码必须是完全唯一的,只是两个相等对象的哈希码返回相同的哈希码.让两个不相等的对象返回相同的哈希码是完全合法的.但是,哈希码分布在一组对象上越独特,您将从HashMaps和使用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;
}

顺便说一句,Java哈希表(HashMap等)重新哈希传入的哈希值以更均匀地分布.因此,尽管努力使价值更加独特对于防止碰撞是有用的,但通常不值得花费太多精力来使它们分布均匀. (5认同)

只是为了澄清:"equal objects => equal hashcode"与"equal hashcode => equal object"不同.但真实的是"不等的hashcode => nonequal objects".这意味着根据定义,总是为任何对象返回42的哈希码方法是有效的哈希码; 这只是一个非常糟糕的. (4认同)

有效但不受欢迎.这称为哈希冲突.良好的散列算法可以最大限度地减少冲突,但不需要保证它们不会发生. (2认同)

---

Steve Kuo.. 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.虽然有效,但这对于基于散列的集合中的性能是不合需要的.

1> Marc Novakow..：

---

它没有说对象的哈希码必须是完全唯一的,只是两个相等对象的哈希码返回相同的哈希码.让两个不相等的对象返回相同的哈希码是完全合法的.但是,哈希码分布在一组对象上越独特,您将从HashMaps和使用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;
}

---

顺便说一句,Java哈希表(HashMap等)重新哈希传入的哈希值以更均匀地分布.因此,尽管努力使价值更加独特对于防止碰撞是有用的,但通常不值得花费太多精力来使它们分布均匀.

---

只是为了澄清:"equal objects => equal hashcode"与"equal hashcode => equal object"不同.但真实的是"不等的hashcode => nonequal objects".这意味着根据定义,总是为任何对象返回42的哈希码方法是有效的哈希码; 这只是一个非常糟糕的.

---

有效但不受欢迎.这称为哈希冲突.良好的散列算法可以最大限度地减少冲突,但不需要保证它们不会发生.

2> Steve Kuo..：

---

我不会详细介绍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.虽然有效,但这对于基于散列的集合中的性能是不合需要的.

3> kdgregory..：

---

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

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

由于数组检索是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的素数.这不会加速数组索引本身,但允许使用按位AND而不是除法来计算数组索引,正如Neil Coffey所说.就个人而言,我认为这是过早的优化,但考虑到HashMap的作者列表,我会假设有一些真正的好处.