title: What is HashMap memory usage in Java if it adds existing data
body: <p>Say I have two linked lists of same length.</p>
  
  <pre><code>class Node {
     int val;
     Node next;
  }
  
  List&lt;Node&gt; list1 = LinkedList&lt;&gt;(); // list1 has 1,2,3,4,5,6,7... N
  List&lt;Node&gt; list2 = LinkedList&lt;&gt;(); // list2 has 1,2,3,4,5,6,7... N
  </code></pre>
  
  <p>I create a <code>HashMap</code> and map each element of list1 to list2</p>
  
  <pre><code>Map&lt;Node, Node&gt; map = new HashMap&lt;Node, Node&gt;();
  for (int i = 0; i &lt; list.size(); i++){
      map.put(list1.get(i), list2.get(i));
  }
  </code></pre>
  
  <p>The <code>HashMap</code> 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 <code>list1</code> and <code>list2</code> as extra memory), what is the space complexity? O(N) or O(1)?</p>