HashMap 空间复杂度

Question

HashMap 空间复杂度

javaalgorithmhashmapbig-ospace-complexity

10

将每个下一个指针指向其下一个右侧节点。如果没有下一个右侧节点，则应将下一个指针设置为 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)，还是因为这些键的值是一个List，所以应该更高？

- Yar

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kaidul · Accepted Answer

既然我们只在这个map中存储了5个键，那么我们能否得出HashMap> map = new HashMap()的空间复杂度只有O(n)呢？或者因为这些键的值都是一个List，它的空间复杂度应该更高一些吗？

不是的。

HashMap的通用实现使用了桶(bucket)，它基本上是一个链表的链，每个节点包含<key, value>对。所以如果你有重复的节点，这并不重要——它仍然会在链表节点中复制每个键和它的值。

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

编辑

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

哈希表的空间复杂度采用大O符号记法表示，是O(n)，其中n是条目数。请记住，大O符号表示随着输入数量的增加的增长阶数，它不反映算法所占用的确切数值空间。对于哈希表，随着条目数的增加，哈希表的空间将线性增加。因此，空间复杂度为O(n)。

但是，我认为您正在寻找哈希表所占用的确切空间，这取决于哈希函数、键和值的类型。在上图中，总共占用的空间为[桶中单元格的数量(hash) + 每个桶/链表中的条目数]，每个条目占用[key类型大小+value类型大小]的空间。

希望能有所帮助。