hashcode()和equals()方法

Question

hashcode()和equals()方法

11

我有一个关于hashCode()和equals()方法的问题。

假设我编写了一个非常基本的程序，覆盖了这两个方法。

import java.util.*;

class Employee
{
   private String name;
   private int empid;


   public Employee(String name,int empid)
   {
       this.name=name;
       this.empid=empid;
   }


   public int getEmpid()
   {
       return empid;
   }


   public String getName()
   {
       return name;
   }


   public boolean equals(Object obj)
   {
       System.out.println("equals has just been called...");
       Employee e1=(Employee)obj;
       return ((name.equals(e1.name)) && (empid==e1.empid));
   }


   public int hashCode()
   {
       System.out.println("hashcode called...");
       return empid;
   }

}

那么，假设我写了另一个类来添加和迭代HashSet中的元素

class Five
{
   public static void main(String args[])
   {
       HashSet hs1=new HashSet();
       hs1.add(new Employee("Alex",25));
       hs1.add(new Employee("Peter",25));
       hs1.add(new Employee("Martin",25));
       hs1.add(new Employee("Alex",25));


       Iterator itr=hs1.iterator();

       while(itr.hasNext())
       {
           Employee e=(Employee)itr.next();
           System.out.println(e.getEmpid()+"\t"+e.getName());
       }


    }

}

现在的问题是，当我尝试使用相同的empid再次添加Alex时，equals()方法总是被调用三次。

由于哈希表中没有索引，因此如果首先检查先前添加的Alex，则应该返回true，并且不应对其他两个元素（peter和martin）进行调用。但是equals方法总是被调用3次。

为什么会这样呢？

同一桶中的对象是否也有索引？

- sandiee

我会看一下 HashSet 的源代码。从记忆中，它实际上会将其添加到一个映射表中，所以我怀疑 indexOf 和 equals 方法在其中被多次使用。 - RNJ

安库尔·拉蒂- 抱歉，我的问题不同。 - sandiee

4个回答

3

java.util.HashSet使用java.util.HashMap作为其存储。 java.util.HashMap使用链式Entry对象来表示地图中的桶。如果您跟随源代码，您将到达java.util.HashMap.Entry的构造函数：

Entry(int h, K k, V v, Entry<K,V> n) 
{
  value = v;
  next = n;
  key = k;
  hash = h;
}

从这里可以看到，新项目被添加到桶的开头（ Entry n 代表桶中的第一个 Entry ），因此在您的情况下，桶中的项目（只有一个桶，因为每个 Employee 的哈希码都相同）将会按照以下顺序排列：

Martin -> Peter -> Alex

因此，当第二次添加Alex时，在到达Alex之前会检查每个值是否相等。

- Nick Holt

2

在插入时，HashSet会首先调用hashCode方法并查找新值属于哪个桶(bucket)。它发现已经有三个条目(所有的hashCode()都为25)。

然后，它使用equals()进行比较。由于有3个条目，因此它必须检查所有条目，导致调用equals() 3次。

- Uwe Plonus

1

我最初也认为他违反了equals()和hashCode()的契约，但它实际上如何影响任何事情呢？如果它们具有相同的empid，它们将映射到同一数组槽，然后使用equals来查看names是否匹配。我看不出有什么问题... - Steve P.

3

我认为 equals 和 hashCode 方法看起来不错 - equals 使用了 name 和 empid 字段，而 hashCode 只使用了 empid。这并没有验证合同，即“相等的对象应具有相同的哈希码，但相同的哈希码不意味着对象相等”。 - Nick Holt

其实，我认为只要 equals 返回 false，它就只需要比较条目，但是一旦 equals 返回 true，它就可以停止。所以这可能意味着第一个条目（“Alex”，25）由于某种原因在列表末尾？ - Puce

修改了答案，因为equals()和hashCode()的契约目前还是可以的。没有仔细阅读。在我看来，答案的其余部分仍然有效。 - Uwe Plonus

0

具有相同哈希值的多个对象被存储为LinkedList，并且新元素添加到HEAD。因此，在您的情况下，由于所有对象具有相同的哈希值，LinkedList 的顺序如下：

Martin->Peter->Alex。

当您添加另一个“Alex”时，列表从头开始遍历。

测试方法：

public boolean equals(Object obj)
   {
       Employee e1=(Employee)obj;
       System.out.println(this.name +  "'s equals has just been called against " + e1.name );
       return ((name.equals(e1.name)) && (empid==e1.empid));
   }

- rocketboy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Juned Ahsan · Accepted Answer

Equals方法在Java哈希集合中添加或删除元素时总是在hashCode方法之后调用。原因是，如果指定的桶中已经有一个元素，则JVM会检查它是否是要添加的相同元素。如果equals返回false，则该元素将添加到同一桶但在列表末尾。因此，您不仅在同一桶中具有单个元素，而且还有元素列表。

现在，在检索元素时，首先会调用hashCode以达到所需的桶，然后使用equals扫描列表以获取所需的元素。

hashCode的理想实现将确保每个桶中的列表大小为1。因此，元素的检索使用O(1)复杂度完成。但是，如果在桶中存储了多个元素，则元素的检索将使用O(n)复杂度完成，其中n是列表的大小。

顺便提一下，在HashSet的情况下，不会在桶中创建列表，而是只是替换对象（如果哈希码和equals相同）。HashMap才有列表创建行为。