What is HashMap memory usage in Java if it adds existing data

Question

Say I have two linked lists of same length.

class Node {
   int val;
   Node next;
}

List<Node> list1 = LinkedList<>(); // list1 has 1,2,3,4,5,6,7... N
List<Node> list2 = LinkedList<>(); // list2 has 1,2,3,4,5,6,7... N

I create a HashMap and map each element of list1 to list2

Map<Node, Node> map = new HashMap<Node, Node>();
for (int i = 0; i < list.size(); i++){
    map.put(list1.get(i), list2.get(i));
}

The HashMap only inserts reference to existing data, it doesn't create any new Node. In term of memory usage, how much memory does the HashMap consume? In other words, if we talk about space complexity of this insertion (we are not counting the memory used by the list1 and list2 as extra memory), what is the space complexity? O(N) or O(1)?

How could it be O(1)? You said it yourself: The map needs to hold a reference to each element of the lists. How could it be O(1)? — JB Nizet
– JB Nizet, Commented Jul 7, 2018 at 13:40
The space complexity is O(n), regardless of how many bytes it uses per element. The complexity only tells you, how it scales, and well, storing twice the number of elements will need roughly consume twice the memory. That’s a linear dependency, also known as O(n). Besides that, there is no relationship between the map and the LinkedList, further, a Node class have a next reference suggests some kind of linked list that is also unrelated to the LinkedList. — Holger
– Holger, Commented Jul 7, 2018 at 13:45

Mureinik · Accepted Answer · 2018-07-07 13:43:47Z

1

A HashMap has to keep a reference to each key and each value it has. In practice, it would usually take up a bit more due to the internal data structures needed to implement the map, but it's negligible compared to the references to the keys and values. To make a long story short - a HashMap has an O(n) space complexity.

answered Jul 7, 2018 at 13:43

Mureinik

316k54 gold badges400 silver badges405 bronze badges

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

1 Comment

Holger Over a year ago

It doesn’t matter, how much more a HashMap node takes, it’s still O(n), a linear dependency between size and space, the same way ArrayList and LinkedList have O(n) space complexity, despite the latter takes about six time the space of the former…

Collectives™ on Stack Overflow

What is HashMap memory usage in Java if it adds existing data

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related