CODEWITHSUNDEEP
javahashmaptime-complexity
Movieboy
Movieboy

Reputation: 373

Alternative to Traversing Hasmap of list Values?

I have a hashmap that contains a list as its values:

HashMap<Integer,ArrayList<<Children>> parent

I used this because it allowed for an O(1) lookup of children belonging to the parent (by using the Parent ID as the key). However, the problem is when I need to find the parent of a child. This requires traversing the whole Hashmap and looking at all the values in each individual map. I'm not against doing this but is there anything faster that could be done?

Upvotes: 0

Views: 40

Answers (1)

steves165
steves165

Reputation: 104

Instead of having a Map<Integer, List<Children>> you could implement a Guava MultiMap as defined here. The MultiMap would have the structure MultiMap<Integer, Children> now this doesn't solve your current problem. However if you take a quick look around stack overflow you can find an implementation of a MultiBiMap like this, a MultiBiMap would have the advantage of two way lookups, so you could lookup by the ID of the parent or inverse the Map and lookup by the Child object (**The child would need a HashCode and Equals implementation for the lookup).

PS: I am aware this is hideously complex but if you are looking purely for efficiency this should be pretty efficient.

Upvotes: 1

Related Questions