As per Joshua Bloch Effective Java Second Edition, Item 9 Always override hashCode when you override equals.

“You must override hashCode in every class that overrides equals. Failure to do so
will result in a violation of the general contract for Object.hashCode, which will
prevent your class from functioning properly in conjunction with all hash-based
collections, including HashMap, HashSet, and Hashtable.”

Another Important Line from the Effective Java “In hashCode method you must exclude any fields that are not used in equals comparisons,
or you risk violating the second provision of the hashCode contract”(To refer to contract look into Object.java (javadoc))

I want to add to this and say :

Always compareTo method should reflect same logic as you have in equals.

Why so ?

If you will override hashCode then true your hash-based collections will work but what about collections which are not hash-based (you will ask are there any.).Yes collections like TreeSet(This class implements the Set interface, backed by a TreeMap instance),TreeMap(Red-Black tree based implementation of the SortedMap interface) are not hash-based.

How do they Work then ?

These collections depend on compareTo method which is available in Comparable Interface or compare Method which is available in Comparator Interface. So either these collections can be given Comparator instance or the objects being added in these collections implement Comparable Interface.

Why do the need compareTo or compare ?

Remember First Lecture on Binary Trees.There is a root node and it has child which can be either left of it or right of it. Now how is it decided in TreeMap, well you might have guessed it by now.These compareTo and compare methods are used for it.In Order to decide whether new element has to be added (seacrhed for) in left of or right of the root node depends on the outcome of  compareTo, if outcome is negative integer then in left otherwise in right.(Or if they are equal then change the value of that node, as set doesnt allow duplicates)

What will happen if i screw up this method ?

Lots of bad things will happen:

You will never find your Object which you put in the Collection ?

Well its dangerous can you explain it in more detail. Here is the case you have a equals method which is not in sync with compareTo method then contains() method invoked with the equal object will return false. So one contract is the if two objects are equal then compareTo must return “Zero”.

From the Javadoc of compareTo

“It is generally the case, but not strictly required that (compare(x, y)==0) == (x.equals(y)). Generally speaking, any comparator that violates this condition should clearly indicate this fact. The recommended language is “Note: this comparator imposes orderings that are inconsistent with equals.”

I dont know why they didnt make it required. It should have been a required condition as otherwise contains() operation will be screwed on collection. You are not always going to do contains check with the same object which is already in Collection.You might have the Equal object (The Object  for which equals() return true.) and you want to check if this exist in collection and want to find the object which exists.Typical use case can be in Hibernate you have a transient object and you want to find persistent instance from the collection and then sync the properties from transient to persistent object.

How should we implement compareTo then ?

Well you need to satisfy this condition (compare(x, y)==0) == (x.equals(y)) at any cost. One way is you can use CompareToBuilder and append all the fields which are in equals.

Out of Curiosity if equals condition you mentioned is satisfied but for all others results are biased i mean i am always growing tree in one direction say always compareTo returns greater Then Zero for every object. Will it screw up Performance ?

Nice , so you have finally data structures running in mind. Well it has been affected had it been just a Binary Tree.But its smarter than that, its a Red-Black Tree.

“The constraints of Red Black tree enforce a critical property of red-black trees: that the longest path from the root to any leaf is no more than twice as long as the shortest path from the root to any other leaf in that tree. The result is that the tree is roughly balanced. Since operations such as inserting, deleting, and finding values require worst-case time proportional to the height of the tree, this theoretical upper bound on the height allows red-black trees to be efficient in the worst-case, unlike ordinary binary search trees.”

As per javadoc of TreeMap

“This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest’s Introduction to Algorithms.”

Still didnt understand ? But How remeber you said that it will keep adding in one direction ?

Well enough of spoon feeding. Open TreeMap. java and look into put method. You will find some method like fixAfterInsertion().It will keep balancing the tree after every insert.So it will be invoked after every Insert.

Dude You are driving me crazy.Do you think I am dumb.Isn’t fixAfterInsertion method take time ?

Well that’s beauty of Red-Black Tree.fixAfterInsertion takes O(log(n)), but as it happens after insertion so total time will be O(log(n)) +O(log(n)) which is O(2log(n)) which is anyway O(log(n)).The rotateRight and rotateLeft are constant time operations.You understand constant means O(1).

Never mind coming back to original topic ,another important para which mandates requirment of compareTo and equals to be consistent.

“Note that the ordering maintained by a sorted map (whether or not an explicit comparator is provided) must be consistent with equals if this sorted map is to correctly implement the Map interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Map interface is defined in terms of the equals operation, but a map performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this method are, from the standpoint of the sorted map, equal. The behavior of a sorted map is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Map interface.”

I want to see from my own Eyes ?

Download the Test Project from here.

Thanks. Hope you enjoyed reading and learnt some thing.