Reputation: 16143
I wish to retrieve values from a Java Key/Value pair (Map with one-to-many mapping) having only one corresponding key without looping over all the values in the Map and turning it into a O(n)
complexity.
The Key/Value data structure would be like:
K1 --> V1, V2
K2 --> V1, V2, V3
K3 --> V1
K4 -->
K5 --> V4, V2
Would appreciate if anyone has any recommendations around the same or if this can be made better time-complexity wise.
Upvotes: 0
Views: 569
Reputation: 1121
Could you be more specific?
What properties describe your keys and values?
Assuming your keys are unique, you could have multiple values mapped to a key using a LinkedList or an ArrayList. To retrieve all values you just have to take a reference to the specific data structure but at one point or another you will definetely need to traverse the list so, yes, it will take O(n) time if you want to check each element for something. On the other hand, you could use a Binary Tree or a Red-Black Tree (or something else) for your values making searching among them much more efficient (as I said these depends on your value's properties).
Upvotes: 1
Reputation: 20097
In google's guava there is a very nice BiMap class where you can look-up both keys and values (it is backed by two Maps).
http://code.google.com/p/guava-libraries/
EDITED: After clarification. I think my answer does not change much. Guava has also very nice MultiMap interface (and several implementations of it) which you can most likely use for your purpose.
Upvotes: 1
Reputation: 1977
Given my above assumptions in my comments, the most straightforward way to do this which comes to mind quickly is to have two structures. Either two maps, where the keys in one are the values in the other and vice-versa, or to have two sorted lists for which you can perform a binary search on either and the result you find has a reference to the sister-element in the other list; this would give you o(log(n)).
If you go with two mirror-image maps as mentioned above, you could have o(1) if they are both HashMap
s. You could have a HashMap and a HashMap, and then have a structure which encapsulates keeping them synchronized.
Upvotes: 1