TreeSet internally uses TreeMap, so is it required to implement Hashcode method when using Treeset?

Question

I would like to know what it means when javadocs for TreeSet says

This class implements the Set interface, backed by a TreeMap instance?

In the below example, I haven't implemented the Hashcode method and still it is working as per expectation i.e it is able to sort the objects. Notice that I have purposely not implemented a consistent Equals implementation to check the TreeSet behaviour.

import java.util.TreeSet;


public class ComparisonLogic implements Comparable<ComparisonLogic>{

String field1;
String field2;

public String toString(){
    return field1+" "+field2;
}

ComparisonLogic(String field1,String field2){
    this.field1= field1;
    this.field2= field2;

}
public boolean equal(Object arg0){
    ComparisonLogic obj = (ComparisonLogic) arg0; 

    if(this.field1.equals(obj.field1))
        return true;
    else
        return false;
}

public int compareTo(ComparisonLogic arg0){
    ComparisonLogic obj = (ComparisonLogic) arg0;   
    return this.field2.compareToIgnoreCase(obj.field2);
}

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub

    ComparisonLogic x = new ComparisonLogic("Tom", "jon");
    ComparisonLogic y = new ComparisonLogic("Tom", "Ben");
    ComparisonLogic z = new ComparisonLogic("Tom", "Wik");

    TreeSet<ComparisonLogic> set = new TreeSet<ComparisonLogic>();
    set.add(x);
    set.add(y);
    set.add(z);
    System.out.println(set);
}

}

This example prints [Tom Ben, Tom jon, Tom Wik]. So it is sorting based on the compareTo method and hashcode() method looks insignificant in this scenario. However, Treeset is backed by TreeMap, so internally if TreeMap is used for sorting, how is TreeMap hashing the object?

Answer 1

It is true that TreeSet internally uses TreeMap. TreeMap doesn't need to have hashCode and equals method implemented for key objects. TreeMap internally uses Red-Black tree which is a self balancing binary search tree. Order in this tree is maintained by using either compareTo method (key object implements Comparable interface) or compare method (provided comparator is defined while constructing TreeMap, in this case for TreeSet actually). Hope it clears.

Answer 2

I think you are posing two questions.

1, Why is your code working?

As Avi wrote at this topic:

When you don't override the hashCode() method, your 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.

This means it doesn't have to store them separately but it might. Try this code:

TreeSet<ComparisonLogic> set = new TreeSet<ComparisonLogic>();
    set.add(new ComparisonLogic("A", "A"));
    set.add(new ComparisonLogic("A", "B"));
    set.add(new ComparisonLogic("A", "C"));
    set.add(new ComparisonLogic("B", "A"));
    set.add(new ComparisonLogic("B", "B"));
    set.add(new ComparisonLogic("B", "C"));
    set.add(new ComparisonLogic("C", "A"));
    set.add(new ComparisonLogic("C", "B"));
    set.add(new ComparisonLogic("C", "C"));
    set.add(new ComparisonLogic("A", "A"));

    System.out.println(set.remove(new ComparisonLogic("A", "A")));
    System.out.println(set.remove(new ComparisonLogic("A", "B")));
    System.out.println(set.remove(new ComparisonLogic("A", "C")));
    System.out.println(set.remove(new ComparisonLogic("B", "A")));
    System.out.println(set.remove(new ComparisonLogic("B", "B")));
    System.out.println(set.remove(new ComparisonLogic("B", "C")));
    System.out.println(set.remove(new ComparisonLogic("C", "A")));
    System.out.println(set.remove(new ComparisonLogic("C", "B")));
    System.out.println(set.remove(new ComparisonLogic("C", "C")));

The output for me was the following:

true
true
true
false
false
false
false
false
false

That means some of them were there some of them not.

2, What it means when javadocs for Treeset says 'This class implements the Set interface, backed by a TreeMap instance'?

It means that the TreeSet class in java 1.7 looks like the following:

public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
/**
 * The backing map.
 */
private transient NavigableMap<E,Object> m;

 TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}

... (lots of other code)     

public boolean contains(Object o) {
    return m.containsKey(o);
}

etc.

This means that there is a map underneath the TreeSet class and there is a lot of methods which is only delegated to it.

I hope I could help.

Answer 3

TreeSet internally uses TreeMap object 'm' to store objects as key-value pair which implies that the call

set.add(x);

internally calls put method of TreeMap:

public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}

Now put method internally calls either compare if Comparator is provided or in your case uses ComparisonLogic class "compareTo" method.

It never uses equals or hashcode explicitly instead uses compareTo(Object o1) (provided while implementing Comparable) or compare(Object o1, object o2) (provided while implementing Comparator) method to determine the presence of Object in the set.

so to answer your question it is not required to implement hashcode() method unless you are using it in your comparison (compare or compareTo) method implementation.