File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
Win a copy of Clojure in Action this week in the Clojure forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

TreeSet & TreeMap confusion

 
Ben Pheonix
Ranch Hand
Posts: 46
1
Java Tomcat Server
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
Eclipse IDE Java Windows XP
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 46
1
Java Tomcat Server
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 1142
4
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 5575
Eclipse IDE Java Windows XP
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 82
Eclipse IDE Java Spring
  • 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 52
Eclipse IDE Java Spring
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Pie
Posts: 20187
26
MySQL Database
  • 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 52
Eclipse IDE Java Spring
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Pie
Posts: 20187
26
MySQL Database
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic