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

Question

I would like to know what this means when Javadocs for TreeSet says

Does this class implement the Set interface supported by the TreeMap instance?

In the example below, I have not implemented the Hashcode method and it still works as expected, that is, it is able to sort objects. Note that I have not specifically implemented a consistent implementation of Equals to test TreeSet behavior.

 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 sorting based on the compareTo method of the hashcode() method in this scenario looks insignificant. However, Treeset supported by TreeMap, so if TreeMap used for sorting, then how does the object TreeMap within TreeMap ?

Answer 1

I think you are asking two questions.

1, Why does your code work?

As Avi wrote on this topic :

If you do not override the hashCode () method, your class inherits the default hashCode () method from Object, which gives each object a separate hash code. This means that t1 and t2 have two different hash codes, even if you compared them, they would be equal. Depending on the specific implementation of the hash card, the card is free to store them separately.

This means that he does not have to store them separately, but he can. 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 as follows:

 true true true false false false false false false 

This means that some of them were there, some of them were not.

2. What does it mean when javadocs for Treeset says: "Does this class implement the Set interface supported by the TreeMap instance?

This means that the TreeSet class in java 1.7 looks like this:

 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 under the TreeSet class there is a map, and there are many methods that are delegated only to it.

Hope I can help.

Answer 2

It is true that TreeSet internally uses TreeMap. TreeMap should not have a hashCode and equals method implemented for key objects. TreeMap internally uses the Red-Black tree, which is a self-balancing binary search tree. The order in this tree is supported using the compareTo method (the key object implements the Comparable interface) or the comparison method (provided that the comparator is determined when constructing the TreeMap, in this case, for the TreeSet in fact). I hope he cleans.

Answer 3

Your ComparisonObject uses the hashCode method defined on Object . Try adding a few different ComparisonLogic with the same values ​​for both fields and see what happens.

Answer 4

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

 set.add(x); 

internally calls the put TreeMap method:

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

Now the put method internally calls either comparison, if a Comparator is provided, or in your case uses the ComparisonLogic method of the compareTo class.

It never uses equals or hashcode explicitly, instead uses compareTo (Object o1) (provided by the Comparable implementation) or compares (Object o1, object o2) (provided by the Comparator implementation) to determine if an object is in the collection.

therefore, to answer your question, you do not need to use the hashcode () method if you do not use it in the implementation of the comparison method (compare or compareTo).