?
Solved

TreeSet and HashSet

Posted on 2006-04-30
17
Medium Priority
?
925 Views
Last Modified: 2008-01-09
I have a class, SortedHashSet.

It is supposed to incorporate both TreeSet and HashSet. The class is as below:

import java.io.*;
import java.lang.*;
import java.util.*;

class SortedHashSet<T> extends TreeSet<T>
{
      
}

I have to override the add function such that it will maintain a TreeSet and a HashSet.

Can anyone advise me how it can be done?
For HashSet, I will need to declare a variable of type, HashSet. How about TreeSet?

Thanks in advance.

Regards


0
Comment
Question by:yiyi83
  • 4
  • 4
  • 4
  • +4
16 Comments
 
LVL 14

Expert Comment

by:hoomanv
ID: 16571377
Im not sure if you can have both HashSet and TreeSet behavior in one class
hash set does not guarantees the order of iteration
on the other hand adding an elemnet to TreeSet is O(log n) but HashSet is O(1) (Constant time)
how is it possible to have a sorted hash set ?

if you want to be able to iterate through the set in ascending order, try
Set sortedSet= new TreeSet( yourHashSet );
0
 
LVL 3

Expert Comment

by:Kanti
ID: 16571764
This link will give you how to  use all three HASHSET, LINKEDHASHSET, AND TREESET. You
can see the add methods of all three

http://java.sun.com/developer/JDCTechTips/2002/tt1105.html
0
 

Author Comment

by:yiyi83
ID: 16571898
Hi,

Just a general idea.

I will be maintaining one HashSet and one TreeSet. During iteration, I will call the TreeSet. During searching, I will call the HashSet.

However, I am just wondering if anyone can tell me given that I extends TreeSet and contains HashSet, how do I program for the add(Object e) to add an item to both TreeSet and HashSet?

Hope that will give a fair idea.

Thanks.
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 86

Expert Comment

by:CEHJ
ID: 16571904
>>I will be maintaining one HashSet and one TreeSet.

Why?
0
 
LVL 14

Assisted Solution

by:hoomanv
hoomanv earned 400 total points
ID: 16572023
> how do I program for the add(Object e) to add an item to both TreeSet and HashSet?

class SortedHashSet<T> extends TreeSet<T>
{
      HashSet<T> hs;

      public boolean add(T o) {
            boolean b;
            b = super.add(o);
            b = hs.add(o) & b;
            return b;
      }
}
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 16572030
Why would you extend TreeSet and not simply use one? A TreeSet is *already* a SortedSet
0
 
LVL 30

Expert Comment

by:Mayank S
ID: 16572034
You can of course, have your own class that maintains a HashSet and a TreeSet, both pointing to the same objects (so the same objects will have 2 references, one in the TreeSet and one in the HashSet). But what's the use?
0
 

Author Comment

by:yiyi83
ID: 16572080
Purpose:

So that it will optimize the search and iteration of items in the TreeSet or HashSet.

Hi Hoomany,

I want to overrides the add function of both TreeSet and HashSet. Hence, within my own add function, I cannot make use of that of theirs.

Regards
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 16572102
>>So that it will optimize the search ...

When you say 'search' what do you mean? The entries are accessed by key ...
0
 
LVL 14

Expert Comment

by:hoomanv
ID: 16572109
> I want to overrides the add function of both TreeSet and HashSet

so you need to inherit your own class from HashSet and override the default add method
then use that derived class instead of HashSet within SortedHashSet class
and call when you call add, the overridden method will be invoked

public boolean add(T o) {
    return super.add(o) & derivedHashSet.add(o);
}

0
 
LVL 14

Expert Comment

by:hoomanv
ID: 16572125
>>So that it will optimize the search ...

I think he/she wants both optimized insertion and ordered iteration
0
 

Author Comment

by:yiyi83
ID: 16572165
Hi,

Search referring to finding out if an item exists within the HashSet.

Basically, I want to achieve O(1) searching and O(n) sorted iteration.

O(1) searching is achieved through HashSet.
O(n) sorted iteration is achieved through TreeSet.

My class is inheriting from TreeSet. Hence, I am containing the HashSet.
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 16572226
You might find

http://javolution.org/api/index.html

interesting
0
 
LVL 92

Assisted Solution

by:objects
objects earned 300 total points
ID: 16574621
> I want to overrides the add function of both TreeSet and HashSet. Hence, within my own add function, I cannot make use of that of theirs.

From what you've said you would appear to only need to override the add() method of TreeSet as hoomanv has posted above.

> O(1) searching is achieved through HashSet.

You'll also need to override contains in that case

public boolean contains(Object o)
{
   return hs.contains(o);
}

You'll also need to override all of TreeSet's methods that modify the TreeSet's content to update both the TreeSet *and* the HashSet similiar to how hoomanv showed for the add() method.
0
 

Accepted Solution

by:
birthstar earned 300 total points
ID: 16582036
If you really do want to do this then I think you would want to agregate the treeset and the hash set into a third class that does not extend either of them but does implement the correct interfaces, I think that this is what objects is saying in their post. This method of agregation should give you the greatest flexibility in your code.
 
As a very rough outline the following might be useful

import java.util.*;

public class SortedHashSet implements SortedSet {

private TreeSet myInternalTree;
private HashSet myInternalHashSet;

// Constructors make sure that both internal sets are initialised by every constructor that you implement

// Methods make sure that each method that modifies the SortedHashSet in any way is directed to both internal sets

// for example addAll might be as follows. The general contract for the method is to return true if the set has changed therefore if either of the internal sets return that they have changed then this method will return true. (Since they are both sets they should always both return true together you might want to test for this)

public boolean addAll (Collection c) {

boolean b1 = myInternalTree.addAll(c);
boolean b2 =  myInternalHashSet.addAll(c);

return b1 || b2;
}

}

You would need to perform a similar operation for each of the methods from the Collection, Set and SortedSet interfaces  
Then make sure that the method that you want to have O(1) performace for is directed only at the hash set and make sure that the iterator method is sent only to the treeset

It should be simple to do unless you want to start modifying the data using Iterators (using remove()).

I hope that this helps.
0
 

Author Comment

by:yiyi83
ID: 16757775
Hi,

Thanks all for the responses. I been busy trying out the different suggestions. They are all helpful.

Sorry for the lateness in awarding the points. Thank you.

Regards
0

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

For beginner Java programmers or at least those new to the Eclipse IDE, the following tutorial will show some (four) ways in which you can import your Java projects to your Eclipse workbench. Introduction While learning Java can be done with…
Java Flight Recorder and Java Mission Control together create a complete tool chain to continuously collect low level and detailed runtime information enabling after-the-fact incident analysis. Java Flight Recorder is a profiling and event collectio…
Viewers learn about the scanner class in this video and are introduced to receiving user input for their programs. Additionally, objects, conditional statements, and loops are used to help reinforce the concepts. Introduce Scanner class: Importing…
Viewers will learn one way to get user input in Java. Introduce the Scanner object: Declare the variable that stores the user input: An example prompting the user for input: Methods you need to invoke in order to properly get  user input:
Suggested Courses
Course of the Month9 days, 19 hours left to enroll

571 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question