JAVA and collections question

[xhail]

I am trying to write a small program that will allow me to add a person's name plus his or her birthday.

I would like the following things to be allowed:
find(name) returns a birthday
add(name, birthday)
and finally a remind(birthday) and this will return a list of people who have this birthday.

I'm also trying to use the Java 1.5 collections library to do this.

So far, I'm thinking of using a HastTable to keep name, birthday pairs. The adding and finding methods are real easy to do using the built in methods for Hasttable. The problem I'm having is the remind method. One way to do it is to just iterate through the whole hasttable and pull out all those who have the same birthdays. Another way would be to keep another Hasttable using the birthdays as keys and an ArrayList with names as the value.

The first way of doing this would make the remind method kind of ugly. But would save the space of not having to replicate another HastTable with the same values. The second way of doing this would make all the methods real easy to implement, but would waste space with another hash table that has the exact same values.

So finally, the question. Is there a collection that will allow me to look up a value given a key and look up a key given a value all in O(log n) time?

thanks!

Disclaimer: This is a school assignment, I could probably whip this up just using arrays and my own implementation of said methods. But we have to use the libraries that Java gives us. I am not asking for code or anything, just a nudge in the right direction in terms of the data structure I should be using.

 

[xmetal2001]

I don't believe there is any collection included with Java that works like a 2-way hash table...
There shouldn't be too much of an issue with using 2 hash tables, thats the way I would do it. All it's doing is holding references, the majority of memory usage is going to be in the strings or whatever object you are storing....

 

[generelz]

The best way to do this working within the java framework is to write an object (class) to hold the name/birthday pair. Then, your program will simply store a List of these objects. If you want O(log n) time to find an object in the list, you will need to keep the list sorted and use binary search to do a find.

Both of these are easily accomplished by writing your own Comparator class to sort the list. A Comparator simply places a natural ordering on your elements (i.e. it takes two instances of your object, compares them, and tells them which is bigger).

More info on writing your own Comparator:
http://www.java2s.com/ExampleCode/Collections-Data-Structure/Comparator.htm

For adding, you will simply run Collections#binarySearch(List, Object, Comparator) and that will return the position that you need to insert the element at. More information here: http://java.sun.com/j2se/1.4.2/docs/api/java/util/Collections.html#binarySearch(java.util.List,%20java.lang.Object,%20java.util.Comparator)

Searching should also use binarySearch as mentioned above.

For finding people that have a certain birthday, you could write another comparator to sort the list in birthday order, then do another binary search to find the first instance of that birthday...then print out all those elements that match that day starting at the first instance.

Hope this helped, and I hope I didn't reveal too much about what you need to do.