HashMap Space Complexity

Question

Here's a sample solution for "Populating Next Right Pointers in Each Node" puzzle:

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");
    }
}

The solution itself doesn't really matter, but what I'm struggling with is determining its Space complexity:

Logically the type of object we are storing in a HashMap should make a difference on its Space complexity, but how we can determine it by having the key and value of the map?

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

Kaidul · Accepted Answer · 2019-05-13T12:12:28.477

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?

No.

The general implementation of HashMap uses bucket which is basically a chain of linked lists each node containing <key, value> pair. So if you have duplicate nodes, that doesn't matter - it will still replicate each key with it's value in linked list node.

You can find different hashtable implementation and their collision resolution techniques here.

Edit

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 Complexity of hashmap in big-O notation is O(n) where n is the number of entries. Remember that, big-O notation depicts the order of growth with the number of input, it doesn't reflect the exact numerical space an algorithm takes. For hashmap, with the increase of the number of entries, the hashmap's space will increase linearly. So space complexity is O(n).

But, I think you're looking for the exact space a hashmap takes which solely depends on the hashing function, type of key and values. In the above picture, total space taken is [number of cell in buckets(hash) + number of entries in each bucket/linked list] and each entry takes [size of key type + size of value type] space.

HIH.

right, 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? — Yar, Apr 16 '17 at 04:35
Could you please take a look at this question too? http://stackoverflow.com/questions/43422027/what-is-the-time-complexity-of-this-function — Yar, Apr 16 '17 at 18:31
@Yar If you can always put question and provide me link in future — Kaidul, Apr 17 '17 at 04:52

HashMap Space Complexity

1 Answers1

Edit