CODEWITHSUNDEEP
javahashmapbig-o
Cody
Cody

Reputation: 65

Embedded Hash Map Big(O)?

If you embed a hash map like so:

Map<String, Map<String, String>> map = new HashMap<String, Map<String, String>();
Map<String, String> innerMap = new HashMap<String, String>();

innerMap.put("x","y");
map.put("z", innerMap);

innerMap = map.get("z"); <---------- O(1) time
String y = innerMap.get("x"); <-------- O(1) time

Does this mean that as long as both maps search times stay relatively close to O(1) then you can essentially search through a second level of a hashmap still in O(1) time?

My internship responsibilities have me dealing heavily with data comparisons and I used something similar to this the other day. I had a string key value that was the name of a certain "Plan" and a value as a hashmap. The internal hashmap had a string key value of an employee ID and a relationship(if an employee was visited twice meaning they had two different coverage levels within the plan from the external map, then their relationship would be updated. Was my choice of DS here a good one? I was attempting to achieve a lookup & edit time of O(1)

Upvotes: 4

Views: 507

Answers (2)

Bohemian
Bohemian

Reputation: 425378

O(1) doesn't mean "completes in one step". It means it completes in (approximately) the same amount of time no matter how large the population. That's why O(1) is also called constant time.

A fixed number of repetitions of a constant time operation is also constant time, ie O(1).

The answer is "yes", your data structure has O(1) time complexity for accessing values from the nested maps.

Upvotes: 4

Chris Gong
Chris Gong

Reputation: 8229

You're basically asking if the runtime of finding an element in a hashmap within another hashmap is constant. The answer is yes. Because think about a hashmap of hashmaps first. As you said earlier, the time it takes to find a value using a key is constant. The total runtime is just this twice; therefore O(1) * 2 = O(2) which is still O(1). Of course, you have to consider collisions, which in excess, can slow down the searching process. This can be avoided of course by picking a suitable load factor.

Upvotes: 2

Related Questions