Data structure with two way O(1) lookup. Hashtable

Question

I'm implementing a system where I have a list of names and each person has 1 phone number. I need to be able to take a name and look up the phone number, or take a phone number and look up a name.

I know I could do this by having two hashtables - one which goes from names to phone numbers and one which goes from phone numbers to names. Then I can look up in either direction in O(1) time. However this seems like I am storing too much data - every name and every phone number is stored twice.

Is there any way to do this more efficiently? What data structure should I use to store the names and phone numbers?

I am coding in Java if that is relevant.

Many thanks!

Answer 1

Java does not provide a two-way hash table out-of-the-box. Your solution that relies on two hash tables is as good as it gets, unless you are willing to go with third-party libraries (which would hide the two hash tables for you) or re-implement a significant portion of HashMap<K,V>.

Then I can look up in either direction in O(1) time. However this seems like I am storing too much data - every name and every phone number is stored twice.

Not necessarily: you can use the same object that represents the phone number, in which case there would be a single object for the phone number, with two references to it stored from two hash tables.

Answer 2

1. Remember that the object itself is stored only once, and not in both maps. You only need double number of references - so it might not be that bad.
2. You can use Gauva BiMap that offers that functionality (and its interface HashBiMap)

Answer 3

Consider using Guava's HashBiMap, which is basically two HashMaps linked together behind the scenes. See also the BiMap interface and its related article.