CODEWITHSUNDEEP
javagenerics
Ankur
Ankur

Reputation: 11739

How TreeSet checks for Duplicates

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:-

Thanks.

Upvotes: 4

Views: 11297

Answers (3)

trutheality
trutheality

Reputation: 23465

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.

Upvotes: 8

ɲeuroburɳ
ɲeuroburɳ

Reputation: 7120

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

Upvotes: 1

MeBigFatGuy
MeBigFatGuy

Reputation: 28568

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

Upvotes: 2

Related Questions