aspose file tools*
The moose likes Beginning Java and the fly likes TreeSet uses compareTo Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "TreeSet uses compareTo " Watch "TreeSet uses compareTo " New topic
Author

TreeSet uses compareTo

Akanksha Joy
Greenhorn

Joined: Jun 05, 2009
Posts: 17
In the code, TreeSet collection is used. TreeSet uses equals() to determine whether an object can be added or not in the set (as Set maintains collection of unique objects) and comparable/ Comparator to determine the order in which the objects are to be added as it uses Binary Search tree to keep the elements in sorted order. I think I am right....I have gone through the concepts...
In the code below, when we add two different objects, only first object is being added? I have not understood this?
Is this the reason- when compareTo() return 0 on second object(two) then I think this means that the element is equal to the first object which is already added in the tree and because two equal objects cannot exists, so discarded the second object...??


Output:
Coffee

Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24187
    
  34

Yes, that's the reason. TreeSet doesn't use equals(); compareTo() == 0 is used to mean equality.


[Jess in Action][AskingGoodQuestions]
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39436
    
  28
You need to read the documentation for java.lang.Comparable, I think. You are supposed to return the same value when you consider the two objects "the same." By always returning 0 you indicate that every object of that class is "the same as" every other object.
Akanksha Joy
Greenhorn

Joined: Jun 05, 2009
Posts: 17

You are supposed to return the same value when you consider the two objects "the same." By always returning 0 you indicate that every object of that class is "the same as" every other object.

I am sorry, I am not asking this. I have prob in the concept. I have gone through the API's and read kathy Sierra. what I have understood is that:
List implementation classes uses equals() when we need to search a given item in the list. So we need to override equals() of Object class.
In Set implementation classes, equals() is used when the the items are added in the collection to maintain unique elements.
In Treebased collection, we need to provide some sorting logic through comparable or comparartor.
In hashing based collection we need to override hashcode() of object class as every object has unique hashcode but two equal objects must have same hashcode().

So TreeSet class is a Set as well as tree based collection, So I think that we need to override both compareTo() (By implementing Comparable)and equals(). But in the code above, I have observed that while adding the elements in the collection (TreeSet), it is using compareTo() and when searching a element it is using same compareTo() and not equals()!!

In nutshell, in TreeBased collection when we add and search elements we need to give the comparing logic onlu\y (either through the comparable or comparator)? So when do we need to override equals() in Tree based collection? in khalid Mughal book its given that in Tree based collection two methods are used:
equals(Object) and
comapreTo(Object) (or compare(Object,Object)).
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39436
    
  28
You will have to read about the different interfaces: here is SortedMap and here is SortedSet. Look at those interfaces and their superinterfaces (eg Set, Map) and it should tell you what they use to order or select their elements.
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24187
    
  34

It is not OK to make these kinds of assumptions. Rather, all you should say is "Objects of this class need to be held in collections, and compared for equality, and therefore I need to override BOTH hashCode() and equals()," OR, "Objects of this class need to be sorted, and therefore I need to implement Comparable." For a sorting collection like TreeSet, you need to do both. You can never pick and choose. All three should be consistent, or you'll get strange behavior.
Akanksha Joy
Greenhorn

Joined: Jun 05, 2009
Posts: 17
It is not OK to make these kinds of assumptions. Rather, all you should say is "Objects of this class need to be held in collections, and compared for equality, and therefore I need to override BOTH hashCode() and equals()," OR, "Objects of this class need to be sorted, and therefore I need to implement Comparable."


Ok then I am going through the comcepts thoroughly and posting details of collection one by one with reasons....correct me if I am wrong.......

Rules-
1. Object class hashcode() returns different hashcode for every object.
2. Two equal objects should have same hashcode (so that hash to same bucket). This is so because at the time of searching a particular element in the collection, it is searched only in the bucket determined by the hashcode().
3. At the time of storing, firstly calculate the hashcode to determine the bucket, then if the element is not already present in the bucket (determine with equals()) store the element in the bucket else reject. In this way, map will not have duplicate keys.

HashMap-

which methods should be overriden?

Hashcode()-If we don’t override the hashcode() then all the elements of the collection will go to different hash buckets. This will result in failure of searching the elements as the hashcode of both the elements - element which is stored and element which is searched- will have different hashcode and searching will occur in two different buckets. Yet no compilation error and no Runtime exception will be thrown.

equals()- This method will be useful only if we override the hashcode() otherwise not. This method will be called to compare the equality of the elements while storing the elements in the hash table so that no two equal objects are stored in the hashtable and also while searching the element in the hash table using contains().



Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39436
    
  28
Two objects which return true from their equals() methods are regarded as the same object by the Collections Framework classes. They must return the same hashcode and also (if Comparable or a Comparator is used) return 0 from compare() or compareTo().
Akanksha Joy
Greenhorn

Joined: Jun 05, 2009
Posts: 17
HashSet:

We have to override hashcode(),as on the basis of this method, all the elements are stored.
I am not sure about one thing. Please confirm this: The java.util.Set API says:
A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element

In HashSet, if two elements are added having same hashcode then, since set does not allow duplicate values, so in HashSet duplicate elements are judged on the basis of hashcode() and not equals(). For example:
String s=new String("hello");
String s1=new String("hello");

Both the string will have same hashcode and therefore if we try to add them in HashSet then only 's' can be added, as 's1' will be considered as duplicate on the basis of hashcode. Am I right?




Daniel Chemko
Ranch Hand

Joined: Feb 27, 2008
Posts: 32
Both the string will have same hashcode and therefore if we try to add them in HashSet then only 's' can be added, as 's1' will be considered as duplicate on the basis of hashcode. Am I right?


Nope. The first step the HashSet will do is use the hashcode() result to find the correct bucket to find where to drop in the new string. If you don't know the concept of buckets, try http://en.wikipedia.org/wiki/Hash_table. Once in that bucket, the hashset will .equals() every object currently found within that bucket for equality. If and only if the .equals() of every object within that bucket returns false does the new object get inserted.
Akanksha Joy
Greenhorn

Joined: Jun 05, 2009
Posts: 17
No, I know the concept of hashing.
So that means in every bucket, no two elements will be equal according to equals(). Its the equals() that determines the equality of the objects.
Akanksha Joy
Greenhorn

Joined: Jun 05, 2009
Posts: 17
TreeSet:

While storing the elements in the TreeSet, we have to provide the sorting logic as TreeSet maintains the elements in the sorted order using Binary search tree. The sorting logic can be provided in two ways: either through Comparable or Comparator.
If the sorting logic is not provided then ClassCastException will be thrown and the elements will not be stored as they cannot be compared while storing.
As TreeSet maintians Collection of unique elements, this is determined the compareTo() or compare() and not through equals method. If the compareTo method returns 0 or true, the element is considered to be in the list and so discarded as duplicate element. Am I right?

Searching:

While searching the elements in the TreeSet using the contains(Object o), it is the compareTo() (or compare()) which determines whether the element is present in the list. while in HashSet, it is the hashcode and equals method which searches the elements (first hashcode and if the bucket found then equals method). In ArrayList, it the equals method which searches the element.
Akanksha Joy
Greenhorn

Joined: Jun 05, 2009
Posts: 17
Can anyone please tell whether the explaination of TreeSet is accurate or not..
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19722
    
  20

If you replace "to be in the list" with "to be in the set" then yes, you're spot on.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Akanksha Joy
Greenhorn

Joined: Jun 05, 2009
Posts: 17
If the compareTo method returns 0 or true, the element is considered to be in the list and so discarded as duplicate element. Am I right?

Are you talking about this quote. Ya I have mistakenly written "list". It should be set.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: TreeSet uses compareTo