Reputation: 79
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
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 HashMap
s 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
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