Understanding the workings of equals and hashCode in a HashMap

Question

I have this test code:

import java.util.*;

class MapEQ {

  public static void main(String[] args) {
   Map<ToDos, String> m = new HashMap<ToDos, String>();
   ToDos t1 = new ToDos("Monday");
   ToDos t2 = new ToDos("Monday");
   ToDos t3 = new ToDos("Tuesday");
   m.put(t1, "doLaundry");
   m.put(t2, "payBills");
   m.put(t3, "cleanAttic");
   System.out.println(m.size());
} }

class ToDos{

  String day;

  ToDos(String d) { day = d; }

  public boolean equals(Object o) {
      return ((ToDos)o).day == this.day;
 }

// public int hashCode() { return 9; }
}

When // public int hashCode() { return 9; } is uncommented m.size() returns 2, when it's left commented it returns three. Why?

Answer 1

You have overidden equals without overriding hashCode. You must ensure that for all cases where equals returns true for two objects, hashCode returns the same value. The hash code is a code that must be equal if two objects are equal (the converse need not be true). When you put your hard-coded value of 9 in, you satisfy the contract again.

In your hash map, equality is only tested within a hash bucket. Your two Monday objects should be equal, but because they are returning different hash codes, the equals method isn't even called to determine their equality - they are put straight into different buckets, and the possibility that they are equal isn't even considered.

Answer 2

When you don't override the hashCode() method, your ToDos class inherits the default hashCode() method from Object, which gives every object a distinct hash code. This means that t1 and t2 have two different hash codes, even though were you to compare them, they would be equal. Depending on the particular hashmap implementation, the map is free to store them separately (and this is in fact what happens).

When you do correctly override the hashCode() method to ensure that equal objects get equal hash codes, the hashmap is able to find the two equal objects and place them in the same hash bucket.

A better implementation would give objects that are not equal different hash codes, like this:

public int hashCode() {
    return (day != null) ? day.hashCode() : 0;
}

Answer 3

When hashCode is uncommented, HashMap sees t1 and t2 as being the same thing; thus, t2's value clobbers that of t1. To understand how this works, note that when hashCode returns the same thing for two instances, they end up going to the same HashMap bucket. When you try to insert a second thing into the same bucket (in this case t2 is being inserted when t1 is already present), HashMap scans the bucket for another key that is equals. In your case, t1 and t2 are equals because they have the same day. At that point, "payBills" clobbers "doLaundry". As for whether t2 clobbers t1 as the key, I believe this is undefined; thus, either behavior is allowed.

There are a few important things to think about here:

1. Are two ToDos instances really equal just because they have the same day of the week?
2. Whenever you implement equals, you should implement hashCode so that any two objects that are equals also have the same hashCode values. This is a fundamental assumption that HashMap makes. This is probably also true of anything else that relies the hashCode method.
3. Design your hashCode method so that the hash codes are evenly distributed; otherwise, you won't get the performance benefits of hashing. From this perspective, returning 9 is one of the worst things you can do.

Answer 4

I cannot emphasize enough that you should read Chapter 3 in Effective Java (warning: pdf link). In that chapter you will learn everything you need to know about overriding methods in Object, and in particular, about the equals contract. Josh Bloch has a great recipe for overriding the equals method that you should follow. And it will help you understand why you should be using equals and not == in your particular implementation of the equals method.

Hope this helps. PLEASE READ IT. (At least the first couple items... and then you will want to read the rest :-).

-Tom

Answer 5

The Implementing equals and Implementing hashCode topics on javapractices.com might be helpful as well.