Inconsistency in hashmap output

[raja singh kumar]

I know that when we use hashmap if there are multiple objects with the same hashcode they go to the same bucket and the bucket has a linked list structure to store those object. But when I was trying out an example, I was unable to understand the output. The hashcode method I have created returns the length of the parameter "name" defined in the Employee class. While inserting in map1 the objects have the same hashcode so when I do a get on the map with key e1, then I get the output as 2(probably because the value is overwritten instead of creating another entry in the linked list). But when I do a similiar thing in map2 with similiar key, I get the output as 1. Who and what decides if there are two objects with the same hashcode then they become a separate entry in the linked list or if the value gets overwritten for the same key?

import java.util.Map;
import java.util.HashMap;
public class MyClass {
    public static void main(String args[]) {
        Map<Employee, Integer> map1=new HashMap<Employee, Integer>();
        
        Employee e1=new Employee("Rahul",35);
        map1.put(e1,1);
        map1.put(new Employee("Rahul",45),2);
        System.out.println(map1.get(e1));
        
        
        Map<Employee, Integer> map2=new HashMap<Employee, Integer>();
        
        Employee e2=new Employee("Rahul", 40);
        map2.put(e2,1);
        map2.put(new Employee("Ricky",30),2);
        System.out.println(map2.get(e2));

    }
}

class Employee
{
    String name;
    int age;
    
    Employee(String name, int age)
    {
        this.name=name;
        this.age=age;
    }
    
    public String getName()
    {
        return name;
    }
    
    public int getAge()
    {
        return age;
    }
    
    public int hashCode()
    {
        System.out.println("Inside hashcode");
        return name.length();
    }
    
    public boolean equals(Object o)
    {
        System.out.println("Inside equals method");
        Employee e=(Employee)o;
        if(this.getName().equals(e.getName()))
        {
            return true;
        }
        return false;
    }
}

Output:
Inside hashcode
Inside hashcode
Inside equals method
Inside hashcode
2
Inside hashcode
Inside hashcode
Inside equals method
Inside hashcode
1

[Stephan van Hulst]

raja singh kumar wrote:Who and what decides if there are two objects with the same hashcode then they become a separate entry in the linked list or if the value gets overwritten for the same key?

The equals() method.

[Rob Spoor]

Which isn't correct. The equals method should never throw any exception, but yours will throw a ClassCastException if the passed object isn't an Employee. You should check first to see if it is, and return false if it isn't.

[raja singh kumar]

The equals() method.

My bad. I wrote the equals method myself and even after that I asked this question. Anyway, thanks for the answer.

[raja singh kumar]

Which isn't correct. The equals method should never throw any exception, but yours will throw a ClassCastException if the passed object isn't an Employee. You should check first to see if it is, and return false if it isn't.

Thanks for the input. I have modified the equals method as shown below. Is it fine or not?

  public boolean equals(Object o)
    {
        System.out.println("Inside equals method");
        if(o instanceof Employee)
        {
            Employee e=(Employee)o;
            if(this.getName().equals(e.getName()))
            {
                return true;
            }
        }
        return false;
    }

[Stephan van Hulst]

Yes. You can simplify it a little bit by returning the result of the name comparison directly though. I usually write the equals() method similar to this:

@Override
public boolean equals(Object obj) {
  if (!(obj instanceof Employee))
    return false;

  Employee other = (Employee) obj;

  return this.getName().equals(other.getName());
}

Or like this, if my class implements Comparable:

@Override
public boolean equals(Object obj) {
  return (obj instanceof Employee) && (this.compareTo((Employee) obj) == 0);
}

[raja singh kumar]

Ok thanks

[Campbell Ritchie]

I suggest you shou‍ld delete the print statement, since that isn't a standard part of equals(). It may also confuse you. There is no guarantee that equals() will actually be called; if you have two “K”s with different hash codes, the Map implementation is allowed to presume they are different objects, following the general contract of hashCode(). More details in the Map interface.
I also suggest you add an == check; this is one of the few places where the == operator is actually good design.

/**
 * Blahblahblah
 *@param obj ...
 *@return ...
 */
@Override
public boolean equals(Object obj)
{
   return this == obj ||
   obj instanceof Employee &&
   Objects.equals(((Employee)obj).name, this.name);
}

Note:-

1: Remember the documentation comments if you want anybody else to use your code.

2: Line 9 takes care of the circumstance where you are trying to compare an object with itself. Reflexivity: every object is equal to itself.

3: The instanceof operator will return false if you pass null to it, so a separate null test is unnecessary. This is one of the few places where instanceof is good design.

4: The Objects method takes care of the circumstance where name is null.

5: There is no need to call getName; you can access the field directly.

6: If you add more fields in subclasses and use them in overridden equals methods, you will fail to maintain the general contract for equals().

7: As you doubtless already know, you must also override hashCode.

[Campbell Ritchie]

I have had a look at the Java® Language Specification about instanceof for your other th‍read. It says that instanceof will fail to compile if a cast would be impossible. But you are declaring obj as type Object. It is therefore in theory possible to cast it to any type, because every reference type is a subtype of Object, so you never see compiler errors from instanceof in a correctly‑written equals method.

[raja singh kumar]

I also suggest you add an == check; this is one of the few places where the == operator is actually good design.

The reason I did not use a == in the equals method was because I want the hashmap to have multiple entries which are stored as linked list. If I use == I cannot have two employee objects where both of them go to the same bucket. I am aware we should ideally have a distributed hashmap instead of having multiple entries in the same bucket. What I am doing in the code is to have mutliple entries in the same bucket. Is it not true that if I add Employee objects by checking == there will be no bucket with multiple entries?

As you doubtless already know, you must also override hashCode.

I know that we need to override both equals and hashcode method. But my question is what implications are there if I override one method and do not override the other one?

[raja singh kumar]

But you are declaring obj as type Object.

Can I define the equals method as taking something else other than Object as an argument?

[Campbell Ritchie]

raja singh kumar wrote:. . . The reason I did not use a == in the equals method was because I want the hashmap to have multiple entries which are stored as linked list.

Where on earth did you get that notion from? That looks completely incorrect. The == in the equals() method is simply a shortcut for the circumstance where the object it is called on and the argument are the same object. There is then no need to make the instanceof or equality tests, because you know they will be true already.

If I use == I cannot have two employee objects where both of them go to the same bucket.

That is quite contrary to how hash based collections work, but it you insist on all your instances going into the same bucket, all you have to do is implement the hash code method always to return the same result.

. . . what implications are there if I override one method and do not override the other one?

Have you tried it? What happens if you have two objects returning true from equals() and different results from hashCode?

Foo f1 = new Foo(...);
Foo f2 = new Foo(...);
System.out.printf("%b %h %h%n", f1.equals(f2), f1, f2);
/* Prints true and two different numbers as hash codes */
myMap.put(f1, "Raja");
myMap.put(f2, "Raja");

Now try some manipulations on the Map and its key set and see what goes wrong.

[raja singh kumar]

Where on earth did you get that notion from? That looks completely incorrect. The == in the equals() method is simply a shortcut for the circumstance where the object it is called on and the argument are the same object. There is then no need to make the instanceof or equality tests, because you know they will be true already.

Yes but I dont want all entries to go to the same bucket. Otherwise I would make my hashcode method to return the same result always. Instead if suppose I want to write a hashcode method so that there are some entries stored inside each bucket as a linked list.

If I take the employee class having String name as a parameter and if I use == in the equals method, then there is no way I can have buckets with multiple entries. Can you give an example where the == in the equals allows multiple entries in the same bucket? I dont want to choose the same object to compare. Infact I want my equals method to be written such that two entries with same hashcode having the same name to be considered equal and as one entry in the bucket despite being two different objects. And  also if the names dont match consider them as two different objects and create multiple entries in the same bucket as they have the same hashcode. I am also aware that if two references are pointing to the same object then the name parameter will obviously match since they are the same object.

Correct me if I am wrong. The decision if two entries go to the same bucket depends on the hashcode being equal. And the decision if the two entries will be considered as the same and will be one entry in the bucket if the equals method considers them equal. And two entries will be created in the same bucket if they have same hashcode and are different according to equals method.

[Campbell Ritchie]

raja singh kumar wrote:. . . If I take the employee class having String name as a parameter and if I use == in the equals method . . .

You appear to have misunderstood how an equals() method is written. What is going to happen if you have a large object with lots and lots of fields, maybe some of them being million‑element arrays or Lists? Maybe you can find that two instances are different very quickly, but you are going to have to compare every element in those arrays or Lists to confirm the two instances are equal. What is going to happen if you do this?

Foo f1 = new Foo(...);
// ...
Foo f2;
// ...
f2 = f1;
// ...
if (f1.equals(f2))
{
   // ...
}

Why do you need to go through all the checking when we can tell that you are comparing two references to the same object? You can tell that equals() call is going to return true without even having to investigate the fields of either object. Remember reflexivity: every object is equal to itself. So the == test is simply an optimisation, but a useful one. Unzip the src.zip file in your Java® installation folder and read java/lang/Object.java. Look how the equals method is implemented. What you are saying with == (if it returns true) is,

My hypothetical equals() method wrote:It's the same instance. I don't need to check any more.

That is why I made sure to use the || operator (not |), so you can see I was short‑circuiting the second half of the method. The == operator is simply a way to implement the reflexivity part of the general contract for equals(). It has nothing to do with hash codes nor which bucket a KV pair goes into.

Correct me if I am wrong. The decision if two entries go to the same bucket depends on the hashcode being equal.

...What if you have a small Map with 16 buckets and there are 2³² different possible values of hash code? You are not going to be able to fit every potential hash code into its own bucket. You probably can't even create 2³² different buckets. The decision about which bucket to fit a particular pair into depends on (h % c) where h is the hash code (after any rehashing) and c is the capacity (=number of buckets). Many implementations use h & c − 1 which gives better performance and never returns a negative result, and works really well if c is an exact power of 2. The decision which bucket a pair goes into depends entirely on the hash code of the K. Implementation details of the equals method here constitute a red herring.

And the decision if the two entries will be considered as the same and will be one entry in the bucket if the equals method considers them equal. And two entries will be created in the same bucket if they have same hashcode and are different according to equals method.

Yes to both, assuming equals() and hashCode() are both correctly overridden.

[raja singh kumar]

/**
 * Blahblahblah
 *@param obj ...
 *@return ...
 */
@Override
public boolean equals(Object obj)
{
   return this == obj ||
   obj instanceof Employee &&
   Objects.equals(((Employee)obj).name, this.name);
}

The above code does not compile and gives error on line 11. Should the line 11 be (((Employee)obj).name).equals(this.name);?

Why do you need to go through all the checking when we can tell that you are comparing two references to the same object? You can tell that equals() call is going to return true without even having to investigate the fields of either object. Remember reflexivity: every object is equal to itself. So the == test is simply an optimisation, but a useful one. Unzip the src.zip file in your Java® installation folder and read java/lang/Object.java. Look how the equals method is implemented. What you are saying with == (if it returns true) is,

Ok, fine, I get the optimization point. My question is if for my Employee class if the equals method is written such that the only comparison done is == and not doing any comparison of the fields in the employee class, then we might as well use the Object class equals method which says [i]return (this == obj);[i]. Does that make sense?

[Campbell Ritchie]

raja singh kumar wrote:. . . The above code does not compile and gives error on line 11.

Please tell us the details of the compiler error. Also how did you import Objects?

Should the line 11 be (((Employee)obj).name).equals(this.name);

Only if you are absolutely sure obj.name will never be null, otherwise you will suffer an exception. The Objects method can cope with null arguments both left and right.

. . . . My question is if for my Employee class if the equals method is written such that the only comparison done is == . . . then we might as well use the Object class equals method . . . Does that make sense?

Yes. But that is different from what you seemed to be asking earlier. If you only use == then don't override equals at all. Don't say class method; that would suggest it is static.

[Frits Walraven]

Congratulations raja singh kumar, your question was selected for this month's Journal  

Have a Cow!