4

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)

Cody
  • 65
  • 3
  • 2
    Yes, this is still `O(1)`, since the time it takes to access an element is not affected by how many elements exist. – Vince Jun 28 '16 at 21:06
  • 1
    Welcome to the site! Check out the [tour](https://stackoverflow.com/tour) for more introduction. [This question](http://stackoverflow.com/questions/1055243/is-a-java-hashmap-really-o1) has more details about HashMaps specifically. In general, yes, if you have two O(1) operations, the result should be O(1). However, the constants hidden in the big-O will get larger. – cxw Jun 28 '16 at 21:07
  • the search of hashmap is constant time. 2 * C = 2C = O(1) anyway – CSK Jun 28 '16 at 21:10

2 Answers2

4

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.

Bohemian
  • 412,405
  • 93
  • 575
  • 722
2

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.

Chris Gong
  • 8,031
  • 4
  • 30
  • 51