java - 如果添加现有数据，Java 中的 HashMap 内存使用量是多少

Question

假设我有两个相同长度的链表。

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

我创建一个HashMap并将 list1 的每个元素映射到 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));
}

唯一插入对现有数据的HashMap引用，它不会创建任何新节点。在内存使用方面，HashMap 消耗了多少内存？换句话说，如果我们谈论这个插入的空间复杂度（我们没有将list1and使用的内存list2算作额外的内存），那么空间复杂度是多少？O(N) 还是 O(1)？

标签： javaalgorithmmemoryhashmapspace-complexity

Answer 1

HashMap 必须保留对每个键和它所具有的每个值的引用。实际上，由于实现映射所需的内部数据结构，它通常会占用更多，但与对键和值的引用相比，它可以忽略不计。长话短说 - HashMap 的空间复杂度为 O(n)。