aspose file tools*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes TreeSet & TreeMap confusion Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "TreeSet & TreeMap confusion" Watch "TreeSet & TreeMap confusion" New topic
Author

TreeSet & TreeMap confusion

Ben Pheonix
Ranch Hand

Joined: Dec 11, 2012
Posts: 46
    
    1

Hello,
I am preparing for OCPJP7 and for that first sitting for OCPJP6 exam. I want to know in the javadocs, it is written that TreeSet is implemented using TreeMap
instance. What does it mean?
Thanks,
Ben


Twitter:ben_pheonix
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

Welcome to CodeRanch

from source code of java.util.TreeSet :

So, TreeSet HAS-A TreeMap data structure(Red-Black tree) to store their objects
Ben Pheonix
Ranch Hand

Joined: Dec 11, 2012
Posts: 46
    
    1

Dear Seetha,

Thanks a ton for your prompt response. The confusion is, it says the TreeSet implementation is based on TreeMap. How is that?
I can see that TreeSet is composed of TreeMap. It means that, whatever the added functionality TreeMap provides like navigation
and searching is implicitly done in TreeSet via TreeMap. Am i am understanding it correct?

Thanks,
Himai Minh
Ranch Hand

Joined: Jul 29, 2012
Posts: 775
TreeSet data structure HAS-A TreeMap. In TreeMap, there is a key-value pair.
In TreeSet, there is a key-value pair as well. But in TreeSet, the value is always null. In TreeMap, the value is whatever value you declare.
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

Himai Minh wrote:But in TreeSet, the value is always null.

One minor correction(nit picking)
in TreeSet , Value is not null but almost like null(you cant access this in your code) as in
Don Redd
Ranch Hand

Joined: Jan 05, 2012
Posts: 82

it is written that TreeSet is implemented using TreeMap
instance. What does it mean?


its simple

as per definition Set does not allow duplicates
and its implemented using Map as map doesn't allow duplicate keys.

here elements of set are same as keys of map inside set.

as similar to TreeSet and TreeMap combination you can check Hashset and HashMap combination

Regards,
Don..Red
Abhineet Kapil
Ranch Hand

Joined: Feb 08, 2010
Posts: 52

I am wondering why would one consume extra memory in java.lang.TreeSet by using a java.lang.TreeMap underneath and assigning dummy objects for each key.
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18657
    
    8

What is the alternative implementation you have in mind which doesn't use extra memory, and what advantages and deficiencies does it have compared to Oracle's implementation?
Abhineet Kapil
Ranch Hand

Joined: Feb 08, 2010
Posts: 52

Array could have been used as a backing structure in a HashSet.
My point is, one doesnt need K,V pair for HashSet. We only need to store values.


But I think Oracle wanted to reuse HashMap for HashSet.
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18657
    
    8

Abhineet Kapil wrote:Array could have been used as a backing structure in a HashSet.


That's true, but then you wouldn't have O(1) access for the set.

My point is, one doesnt need K,V pair for HashSet. We only need to store values.


That's also true, but you could describe it as only storing keys. Personally I think that would be more accurate.

But I think Oracle wanted to reuse HashMap for HashSet.


That's probably true too. It's definitely a plus; the code for HashMap was already written. One other consideration is that without delegating to HashMap, the code for HashSet would have looked very much like the code for HashMap, only not quite the same. You'd have more testing to do (with delegating, a lot of your HashMap tests can work as HashSet tests as well) and you'd have duplicate maintenance to do when fixing bugs.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: TreeSet & TreeMap confusion