Strange behavior of java.util.Set.contains (Object o)

Question

doc about java.util.Set.contains(Object o) says:

Returns true if and only if this collection contains an element e such that (o == null? E == null: o.equals (e)).

However, there is a POJO here (as you can see, I rewrote its equals method):

 public class MonthAndDay { private int month; private int day; public MonthAndDay(int month, int day) { this.month = month; this.day = day; } @Override public boolean equals(Object obj) { MonthAndDay monthAndDay = (MonthAndDay) obj; return monthAndDay.month == month && monthAndDay.day == day; } } 

So please, why does the following code print false instead of true ?

 Set<MonthAndDay> set = new HashSet<MonthAndDay>(); set.add(new MonthAndDay(5, 1)); System.out.println(set.contains(new MonthAndDay(5, 1))); // prints false 

The solution is to rewrite the contains(Object o) method, but the original one should be (almost) exactly the same, am I mistaken?

 Set<MonthAndDay> set = new HashSet<MonthAndDay>() { private static final long serialVersionUID = 1L; @Override public boolean contains(Object obj) { MonthAndDay monthAndDay = (MonthAndDay) obj; for (MonthAndDay mad : this) { if (mad.equals(monthAndDay)) { return true; } } return false; } }; set.add(new MonthAndDay(5, 1)); System.out.println(set.contains(new MonthAndDay(5, 1))); // prints true 

Answer 1

When overriding equals(Object) you also need to override hashcode() .

In particular, methods should be implemented so that if a.equals(b) is true , then a.hashcode() == b.hashcode() is all true . If this invariant is not respected, then HashMap , HashSet and Hashtable will not work properly.

Specifications for how hashcode() and equals(Object) should behave are specified in the Object API.

---

So why hash-based data structures collapse if you are mistaken? Good, because the hash table works by using the value of the hash function to narrow down the set of values ​​that need to be compared with the “candidate”. If the hash code for the candidate is different from the hash code for some object in the table, then the likelihood that the search algorithm will not be compared with the object in the table ... even if the objects are equal.

Answer 2

HashSet will only use equals() if the elements have the same hashCode() , so you need to override both. Here's the relevant piece of code that is used by HashSet#contains() (note that HashSet supported by HashMap ):

  355 /** 356 * Returns the entry associated with the specified key in the 357 * HashMap. Returns null if the HashMap contains no mapping 358 * for the key. 359 */ 360 final Entry<K,V> getEntry(Object key) { 361 int hash = (key == null) ? 0 : hash(key.hashCode()); 362 for (Entry<K,V> e = table[indexFor(hash, table.length)]; 363 e != null; 364 e = e.next) { 365 Object k; 366 if (e.hash == hash && 367 ((k = e.key) == key || (key != null && key.equals(k)))) 368 return e; 369 } 370 return null; 371 } 

Does not do this, violates the Object#hashCode() contract, which states that:

If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects should have the same integer result.