Space Complexity of HashMap when iterating over an Array in linear time

Question

I have a doubt regarding the space complexity of a program. Let's say I am iterating over an Array (stores event ids) with a size of n (may be in billions). I wanted to track the occurrence of each event id, so I have used a hash map to store event id as key and its occurrence counter as value.

Here is the pseudo code:

Map m =  HashMap<>
for i to n-1
  if m.contains(i)
     int prevCount =  m.get(i)
     m.put(i, prevCount +1)
  else
   m.put(i, 1)

What would be the space complexity?

PS This is my first question in stackoverflow, if it seems duplicate, please route me to the correct answer.

Eran · Accepted Answer · 2014-12-06 23:07:42Z

3

Your loop adds at most n-1 key/value pairs to the HashMap.

Therefore, the space complexity is O(n), since the HashMap internal storage consists of an array whose size would reach a power of 2 close to n (assuming you didn't give the HashMap an initial capacity that is much larger than n), and each element of the array is a linked list with an O(1) average number of elements.

edited Dec 6, 2014 at 23:07

answered Dec 6, 2014 at 17:52

Eran

395k57 gold badges726 silver badges793 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

here_to_learn Over a year ago

Thanks for your reply, so when we compute space complexity specially for hash map type data structure, Do we consider the space taken by each K,V OR Do we consider the Space taken by entry object in array. Lets say my program memory can store upto a billion items, and I got say same number of events all unique, if we consider space complexity for each K,V it will be n^2 items in memory which might go out of memory. I am bit confused here.. Sorry my question might sound like a newbie but please give your inputs.

Eran Over a year ago

@here4learn normally you can consider the space taken by a single key value pair as constant, so the space complexity of the map depends only on the total number of pairs

Collectives™ on Stack Overflow

Space Complexity of HashMap when iterating over an Array in linear time

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related