Internal working of get(key) and put(key,value) in HashMaps

In this article we will see the implementation details of get and put in HashMaps i.e. a code walk through of the HashMap class itself.

I am really excited to write this one. I am pretty sure, you would have searched this topic just like I did. There’s not much on the internet about this so I studied the internal libraries myself.

Before we begin it’s important that you have your HashMaps basics already covered. If not, the advice is to go through these articles once:

All core concepts of HashMaps in Java . The only article you need!

Create a custom Key Object in HashMaps Java

Let’s begin!

So HashMaps stores key/value pairs using hashing as an algorithm. HashMaps are internally an array of objects. In this case an array of a class Node which has hash, key, value, and next as the variables.

hash -> hash value of the bucket

key → key to be stored

value -> value to be stored

next -> memory reference to the next element in the linked list for a bucket

Java 8 and later versions use a balanced tree (also called a red black tree) instead of a LinkedList to store collided entries. This improves the worst-case performance of HashMap from O(n) to O(log n). So you will find both the approaches i.e. a tree and linked list in the code below.

hashmap.put(key,value)

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

put takes key and value as the parameters. Internally calls putVal with the hash value, key, and value.

Read the inline comments for code explanation :

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        /*
        table is your hashmap on which you are working on currently
        Initializes or doubles the table size suing resize()
        */
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        /*
        Inserts a key/value pair in a new bucket using hash as the index
        */
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        /*
        else is only called when one key/value pair already exists in the
        bucket. In this case we create a linked list or tree to add additional
        elements into the bucket
        */
        else {
            Node<K,V> e; K k;
            /*
            If the hash value and key value is same overwrite the key/value
            in this bucket
            */
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            /*
            If the bucket is an instance of a treenode them put the value in tree
            */
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                /*
                If the bucket contains a linked list, then store the key/value pair in
                this linkedlist with bucket.next pointing to the new node (very similar
                to how a linked list works)
                */
                else {
                    for (int binCount = 0; ; ++binCount) {
                        if ((e = p.next) == null) {
                            p.next = newNode(hash, key, value, null);
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }

hashmap.get(key)

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

This is the implementation detail of the get method. Takes key as the parameter. Internally calls getNode with two parameters — hash value of the key, and the key itself.

final Node<K,V> getNode(int hash, Object key){
        Node<K, V>[]tab;Node<K, V> first,e;int n;K k;
            /*
            Table is the hashmap we are working on currently.
            This will give us the bucket on which the key is stored.
            */
        if((tab=table)!=null&&(n=tab.length)>0&&
        (first=tab[(n-1)&hash])!=null) {
        /*
        Hash acts as the index of an object in the HashMap. We already have the hash meaning index of the bucket, so just check the
        first element of the bucket with the hash value passed.
        */
        if(first.hash==hash&& // always check first node
        ((k=first.key)==key||(key!=null&&key.equals(k))))
            return first;
        /*
        We already have the hash meaning we have the index to an array of objects. Just traverse the tree node or linked list and find out the right object by comparing the key object using equals()
        */
        if((e=first.next)!=null){
            if(first instanceof TreeNode)
                return((TreeNode<K, V>)first).getTreeNode(hash,key);
            do {
                if(e.hash==hash&&
                ((k=e.key)==key||(key!=null&&key.equals(k))))
                return e;
            } while((e=e.next)!=null);
            }
        }
        return null;
        }
}

As we know, a HashMap stores key/values in buckets. If multiple different keys have the same hash value, then they are stored in a single bucket in the form of a linked list or a tree(in Java8).

Please refer to the inline comments in the above code to understand the internal working of HashMaps.

You can connect with me on LinkedIn