Arvind Talmask
Arvind Talmask

Reputation: 79

Space complexity of Java data structures

I have been searching for many websites that contain information of the space complexity of Java data structures. I am searching specifically for the space complexity of the HashMap, ArrayList, Stack and LinkedList. One site that I found that came close and had information only on the Stack and LinkedList was: http://bigocheatsheet.com/, but it only had the worst case. Would any one know of any other sources that have information on the space complexity of the HashMap or ArrayList, preferably average case and worst case?

Upvotes: 1

Views: 10481

Answers (2)

Stephen C
Stephen C

Reputation: 718798

They are all O(N) in space usage under normal conditions. (So are all of the standard collection data structures, I think ...)

Of course, that doesn't tell you some important facts about how much space these data structures will use in practice. For example:

  • An ArrayList or HashMaps space usage is not directly proportional to the list size. Both have a "double the size when full" strategy for some or all of their space utilization.

  • In the best case, an ArrayList uses less space per element than a LinkedList, and a LinkedList uses less space per element than a HashMap.

And so on.

It is also difficult to quantify the worst case ... because there are certain usage patterns that can lead to an empty ArrayList or HashMap occupying a large amount of space. For these data structures, the space usage may be proportional to the maximum N value (so far) not the current N value.

  • An ArrayList does not "give back" space when elements are removed.

  • With a HashMap the space occupied by the chains can grow and shrink, but the hash array only grows.

Upvotes: 2

kaykay
kaykay

Reputation: 556

If you check the code for these classes, you can see that they are internally represented as arrays. Hence the complexity of operations should be similar to those on arrays.

Upvotes: 0

Related Questions