confusion about comparator, comparable and hashcode

[Fritz Guerilus]

Hi,
Can anyone clear this up for me:

The point of using the comparator & comparable interface is to sort objects in collections. Right?

Don't the hashcode/equals methods play a role in sorting in generic collections?

Do you still need to override the hashcode/equals method for the class which implements the comparator/comparable interfaces?

Sometimes I see classes which implement these interfaces, override the appropriate compareTo/compare methods.
Then I see the those classes which implement these interfaces put in as generic types for collections such as TreeSet.
But I don't see where it indicates overriding the hashcode and equals methods.

Thank You

[Ankit Garg]

Equals and hashCode cannot play a role in sorting. This is because they don't tell in any way whether an object is greater or smaller than the other. If you are using a comparable object in a TreeSet or TreeMap, then you don't need to override the equals or hashCode method. The TreeSet and TreeMap uses the compareTo/compare method to check equality (i.e. if compareTo/compare method returns 0, then objects are considered equal)...

[Salil Vverma]

Hey Fritz ,

The point of using the comparator & comparable interface is to sort objects in collections. Right?

This is correct.

Don't the hashcode/equals methods play a role in sorting in generic collections

nope, hash code and equals play role in searching not in sorting. As you can see in the below code, equals and hash code has not been overridden still is sorts the ArrayList well.

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.TreeSet;

public class ComparableTest implements Comparable<ComparableTest> {

	private String username;

	public ComparableTest(String name) {
		this.username = name;
	}

	public String getUsername() {
		return username;
	}

	public void setUsername(String username) {
		this.username = username;
	}

	public int compareTo(ComparableTest o) {
		return username.compareTo(o.getUsername());
	}

	@Override
	public String toString() {
		return this.getUsername();
	}

	@SuppressWarnings("unchecked")
	public static void main(String[] args) {

		ArrayList<ComparableTest> comparableTestsList = new ArrayList<ComparableTest>();
		ArrayList<ComparableTest> comparableTestsList2;

		comparableTestsList.add(new ComparableTest("Second Name"));
		comparableTestsList.add(new ComparableTest("First name"));
		System.out.println("Orignal Array List  = " + comparableTestsList);

		// making a clone to test this list in Treeset
		comparableTestsList2 = (ArrayList<ComparableTest>) comparableTestsList
				.clone();
		// Sorting the first arraylist which works
		Collections.sort(comparableTestsList);
		System.out.println("Sorted Array List  = " + comparableTestsList);

		// searching the first array which does not work as equals method has
		// not been overriden
		int position = comparableTestsList.indexOf(new ComparableTest(
				"First name"));
		System.out.println("The position of First name is = " + position);

		//using the cloned collection in TreeSet
		TreeSet<ComparableTest> ts = new TreeSet<ComparableTest>(
				comparableTestsList2);
		System.out.println("The value in Tree Set is = " + ts);

	}
}


   

Do you still need to override the hashcode/equals method for the class which implements the comparator/comparable interfaces?

- You need not to implement hascode and equals if you only want to do sorting not seraching (by verifying logical equal comparision). As you can see the above code it does not find the position of "First name" in the collection because we have not overridden equals method.

Sometimes I see classes which implement these interfaces, override the appropriate compareTo/compare methods.
Then I see the those classes which implement these interfaces put in as generic types for collections such as TreeSet.
But I don't see where it indicates overriding the hashcode and equals methods.

For any collection to be in tree set, it must implement comparable interface so that TreeSet could maintiain its property by keeping the elements in sorted order. It does not matter whether equals and hash code has been implemented or not. (As mentioned in the above code)

I hope this would be help full.

Regards
Salil Verma

[Anushree Acharjee]

Thanks Salil for the great explanation. But the following code makes me wonder whats happening

System.out.println("The position of First name is = " + ts.contains(new ComparableTest("First name"))); //prints True, but should not be able to find the element, as we have not overriden equals() and hashcode
 
        //using the cloned collection in TreeMap
        TreeMap<ComparableTest, String> tMap = new TreeMap<>();
        for(ComparableTest ct: comparableTestsList2) {
        	tMap.put(ct, "abc");
        }       
        System.out.println("The value in Tree Map is = " + tMap);
        System.out.println(tMap.get(new ComparableTest("First name")));//prints "abc", but should not be able to find the element, as we have not overriden equals() and hashcode

[Roel De Nijs]

Anushree Acharjee wrote:But the following code makes me wonder whats happening

A TreeSet IS-A SortedSet. This section from the SortedSet javadoc will explain what's happening:

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

The same applies to a TreeMap (which is a SortedMap).

Hope it helpds!
Kind regards,
Roel

[Anushree Acharjee]

Thanks Roel.

So it means,contrary to as Salil explained, we need not to override equals() an hashCode() methods even when we are searching TreeSet or TreeMap. For sorting we need compareTo/compare method implementation. equals() and hashCode() do not come into the picture at all when dealing with TreeSet and TreeMap.

[Roel De Nijs]

Anushree Acharjee wrote:So it means,contrary to as Salil explained, we need not to override equals() an hashCode() methods even when we are searching TreeSet or TreeMap. For sorting we need compareTo/compare method implementation. equals() and hashCode() do not come into the picture at all when dealing with TreeSet and TreeMap.

If you want to sort, you can't do anything with the equals method. Why? For the very simple reason: the return type of the equals method is boolean, so you can only return true (both objects equal) or false (both objects not equal). So you can only determine if 2 objects are equal, not if one object is greater than the other one. It's just like with 2 int values: if you only could use the equality operator (==), you could only know if 2 int values are equal, but not which is the smallest/greatest value.

If you add items to a Set (a collection of unique elements), you need to implement equals and hashCode methods. Otherwise you will have duplicate elements in your set (which sould only contain unique elements). A TreeSet doesn't use the equals/hashCode method, but the compareTo-method (or compare-method). Because this method defines sorting, it's also capable of telling when 2 objects are equal (when compareTo returns 0).
So there's a very important implication as you don't know to which kind of collections your elements will be added (HashSet, LinkedHashSet, TreeSet): to be consistent with the Set interface, the implementation of the equals-method and compareTo-method must be consistent with each other. Otherwise you'll get a different outcome if you add the same items to a HashSet and a TreeSet. Therefore you could implement the compareTo-method as you like and implement the equals method like:

public boolean equals(Object o) {
    return (o instanceof ComparableTest) && this.compareTo((ComparableTest) o) == 0;
}

With this code you are guaranteed equals and compareTo will return consistent values. And if you add your items to an ArrayList, you'll only get correct return values from methods like contains and indexOf if you implemented the equals method correctly.

Hope it helps!
Kind regards,
Roel