use of hashCode() and equals() in TreeSet and TreeMap

Question

From the following code, I understand that, there is no need of overriding equals() and hashCode() method for TreeSet and TreeMap, neither for sorting, nor searching.

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);

        System.out.println("The position of First name is = " + ts.contains(new ComparableTest("First name")));//works fine

        //using the cloned collection in TreeMap
        TreeMap<ComparableTest, String> tMap = new TreeMap<>();
        for(ComparableTest ct: comparableTestsList2) {
            tMap.put(ct, "anushree");
        }       
        System.out.println("The value in Tree Map is = " + tMap);
        System.out.println(tMap.get(new ComparableTest("First name")));//works fine
    }
}

this goes perfectly fine with what's there in javadoc http://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html a TreeSet instance 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 set, equal. The behavior of a set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.

there is also written: Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface.

how equals() and hashCode() comes into picture for TreeSet and TreeMap? Can I get a code sample. Thanks!

Solution 1

You just said it:

a TreeSet instance performs all element comparisons using its compareTo (or compare) method

equals() and hashCode do not come into the picture when dealing when TreeSet and TreeMap. However, it is a good practice to override them properly, should you use this object as a key for HashMap (for example) in the future.

Solution 2

Agreed with your @Tunaki's input. hashCode and equals method are not required for TreeSet and TreeMap as the sorting depends on either the compareTo or compare method as been provided by the client. I think thats the reason why the containsKey method of both of these DS and get(key) method of the TreeMap runs in log(n) time and not in O(1) time as these are not hash based data structures like HashMap or HashTable where the location of an element can be found in O(1) time by applying hash function on the key. In case of TreeSet and TreeMap binary search is applied to locate an element.