CODEWITHSUNDEEP
javabig-ocomputer-science
승기유
승기유

Reputation: 133

What is time complexity for nested map

For the nested map like :

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

What would the time complexity be for its normal operation like put, remove, containsKey?

Thanks!

Upvotes: 1

Views: 986

Answers (1)

Eran
Eran

Reputation: 393811

The time complexity would be the same as the time complexity of non-nested HashMaps.

Each lookup still takes average constant time.

To search for an inner value in the nested Map you need to perform two lookups - the first in the outer Map, and if a value was found in the outer Map, a second lookup in the inner Map. Since both lookup will take constant time, the total lookup time remains constant.

The same is true for put, remove, etc...

Upvotes: 3

Related Questions