HashMap 空间复杂度

Question

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

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

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)还是因为这些键的值是 a Listis 应该比这更多？

Answer 1

由于我们在这个映射中只存储了 5 个键，我们是否可以得出 HashMap> map = new HashMap>(); 的空间复杂度？只是 O(n) 还是因为这些键的值是一个 List 应该比这更多？

不。

HashMap使用桶的一般实现，它基本上是一个链表链，每个节点包含<key, value>对。所以如果你有重复的节点，那没关系——它仍然会复制每个键和它在链表节点中的值。

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

编辑

所以在这个例子中我们有 5 个键，每个键都指向一组 List，但是我们如何确定整体空间复杂度呢？

大 O 表示法中 hashmap 的空间复杂度是O(n)其中n的条目数。请记住，大 O 表示法描述了输入数量的增长顺序，它不反映算法采用的确切数字空间。对于hashmap，随着条目数的增加，hashmap的空间会线性增加。所以空间复杂度为O(n)。

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

嗨。