HashMap空间复杂度

Question

下面是一个解决"在每个节点中填充下一个右指针“难题的示例解决方案：

填充每个下一个指针以指向其下一个右节点。如果没有下一个右节点，则应将下一个指针设置为空。

public void connect(Node root) {
    HashMap<Integer,List<Node>> map = new HashMap<Integer,List<Node>>();
    traverse(root, map , 0);
}

private void traverse(Node root, HashMap<Integer,List<Node>> map , int level){

    if(root != null){

        if(map.containsKey(level)){
            List<Node> temp = map.get(level);
            Node set = temp.get(temp.size() -1 );
            set.next = root;
            root.next = null;
            temp.add(root);
            map.put(level,temp);
        }
        else{
            root.next = null;
            List<Node> temp = new ArrayList<Node>();
            temp.add(root);
            map.put(level,temp);
        }
        level++;
        traverse(root.left, map , level);
        traverse(root.right, map,level);
        System.out.println("test");
    }
}

解决方案本身并不重要，但我正在努力确定其空间复杂性：

从逻辑上讲，我们存储在HashMap中的对象类型应该对其空间复杂性产生影响，但是我们如何通过拥有映射的键和值来确定它呢？

换句话说，如果我们在这个映射中只存储5个键(5个节点)，我们是否可以得出结论：HashMap<Integer,List<Node>> map = new HashMap<Integer,List<Node>>();的空间复杂性只是O(n)，或者因为这些键的值是List，所以应该更多？

Answer 1

既然我们在这个映射中只存储了5个键，那么我们可以得出这样的结论: HashMap> map =新HashMap>()；的空间复杂性只是O(n)，或者因为这些键的值是List，所以应该更多吗？

不是的。

HashMap的一般实现使用桶，它基本上是一个链表链，每个节点都包含<key, value>对。因此，如果您有重复的节点，这并不重要-它仍然将复制每个键与它的值在链表节点。

​

​

您可以找到不同的哈希表实现及其冲突解决技术这里。

编辑

在这个例子中，我们有5个键和一组列表的每个关键点，但是我们是如何确定整个空间复杂性的呢？

大O符号中hashmap的空间复杂性是O(n)，其中n是条目的数量。记住，大O表示法描述了随输入数增长的顺序，它没有反映算法所占的精确的数值空间。对于hashmap，随着条目数量的增加，hashmap的空间将线性增加。所以空间复杂性就是O(n)。

但是，我认为您是在寻找hashmap所占用的确切空间，这完全取决于散列函数、键类型和值。在上面的图片中，所占的总空间是桶(散列)中的单元格数+每个桶/链接列表中的条目数，每个条目的大小为键类型的大小+值类型空间的大小。

HIH。