HashMap Space 复杂度

Question

这是“Populating Next Right Pointers in Each Node”谜题的示例解决方案：

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to 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");
    }
}

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

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

换句话说，如果我们在此映射中仅存储 5 个键（用于 5 个节点），我们是否可以得出结论 HashMap<Integer,List<Node>> map = new HashMap<Integer,List<Node>>(); 的 space 复杂度只是 O(n) 或因为这些键的值是 List 应该不止于此？

Answer 1

since we are storing just 5 keys in this map, can we conclude that the space complexity of HashMap> map = new HashMap>(); is just O(n) or since the value of those keys are a List is should be more than that?

没有

HashMap 的一般实现使用 bucket，它基本上是一个链表链，每个节点包含 <key, value> 对。因此，如果您有重复的节点，那没关系 - 它仍会在链表节点中复制每个键及其值。

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

编辑

so in this example we have 5 keys and each key points to a set of List, but how we are determining the overall space complexity?

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

但是，我认为您正在寻找完全取决于散列函数、键和值类型的散列映射所采用的确切 space。在上图中，总共 space 采取的是 [buckets(hash) 中的单元格数 + 每个 bucket/linked 列表中的条目数]，每个条目采取 [键类型的大小 + 值类型的大小] space.

嗨。

HashMap Space 复杂度

HashMap Space Complexity

java

algorithm

hashmap

big-o

space-complexity

编辑