How TreeSet checks for Duplicates

Question

I am checking how TreeSet checks for duplicate elements and have the following code

  import java.util.*;

  public class TreeDemo{

    public static void main(String[] args)
        {
            new TreeDemo().go();
        }

    public void go()
    {
        Song s1 = new Song("song1","artist1");
        Song s2 = new Song("song2","artist2");
        Song s3 = new Song("song3","artist3");
        Song s4 = new Song("song3","artist3");

        Set<Song> tree = new TreeSet<Song>();

        tree.add(s1);
        tree.add(s2);
        tree.add(s3);
        tree.add(s4);

        System.out.println(tree);

    }
}

class Song implements Comparable<Song>{
    private String title;
    private String artist;

    public Song(String t, String a)
    {
        title=t;
        artist=a;
    }

    public String getTitle(){
        return title; 
    }

    public int compareTo(Song s){
        //Song s = (Song)o;
        return title.compareTo(s.getTitle());
    }

public String toString(){
    return title;
}

}

When I execute this code, I get the following output

[song1, song2, song3]

My question is:-

• Even if I haven't implemented hashCode and equals method (I did implement the Comparable interface since its mandatory and needed to keep the Set sorted), how did TreeSet determine the duplicates?
• Did it use Object class default implementation? It looks like it used "title" field for this check since when I add treats it as duplicate but when I add it doesn't treats it as duplicate.

Thanks.

Solution 1

TreeSet (or technically, the TreeMap that backs it) only uses the compareTo() function to compare the elements. It does not use Object's .equals() or .hashCode(). Moreover, if it had used any of them, your output would have been

[song1, song2, song3, song3]

because Object's default implementation uses memory addresses to test object equality, not their members.

Solution 2

a comparator return < 0, 0 or > 0... So equals is implemented by compareTo returning 0. Thus

if (node1.compareTo(node2) == 0) 

then the node is already in the set

Solution 3

TreeSet implements a balanced binary search tree based upon ordering of its members (via the Comparable or Comparator interfaces), not on hashing.

http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

Comments

[TL36]

Yes, I realized it a bit later that TreeSet used only compareTo (implements Comparable) or compare (implements Comparator) for sorting and duplicate checks. It is Hashset that uses equals and hashCode.