hashcode() and equals() method [duplicate]

Question

so i have a question on hashcode() and equals() method

Let's say I just write a very basic program overridng both the methodes

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;
   }

}

Then, let's say I write another class to add and iterate the elements in 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());
       }


    }

}

now the question is when i try to add Alex again with the same empid the equals() always called thee times

as there is no index n hashmap so in case if it first be checked with previously added Alex it will return true and should not be called for the other two elements (peter and martin) but equals always called 3 times

why..??

is objects within same bucket do also have the index..??

Answer 1

Equals is always called after the hashCode method in a java hashed collection while adding and removing elements. The reason being, if there is an element already at the specified bucket, then JVM checks whether it is the same element which it is trying to put. In case if the equals returns false then the element is added to the same bucket but at the end of list at the bucket. So now you just dont have a single element at the same bucket but a list of elements.

Now while retrieving the element, first hashCode will be called to reach the desired bucket and then the list will be scanned using the equals to fetch the desired element.

The ideal implemenation of hashCode will make sure the size of list at each bucket is 1. And hence the retrieval of elements is done using O(1) complexity. But if there are mulitple elements stored in the list at a bucket, then the retreival of element will be done by O(n) complexiy, where n is the size of the list.

Btw in case of HashSet there is no list created at the bucket, rather the object is simply replaced if hashcode and equals are same. The ist creation behavior is in hashmap.

Answer 2

A java.util.HashSet uses a java.util.HashMap as its storage. A java.util.HashMap uses a linked Entry object to represent the buckets in the map. If you follow through the source code you will get to the contructor of java.util.HashMap.Entry:

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

From this you can see that new items are added to the start of the bucket (the Entry n representing the first Entry of the bucket), so in your case the items in the bucket (there's only a single bucket because the hash code for each Employee is the same) will be in the order:

Martin -> Peter -> Alex

Hence when adding Alex a second time, each value is checked for equality before getting to Alex.

Answer 3

During insert the HashSet first calls the hashCode and looks in which bucket the new value belongs to. It sees that there are already three entries (all with the hashCode() 25).

So it then compares by using equals(). And because there are 3 entries it has to check all entries causing to call equals() 3 times.