How HashMap works internally in java?

HashMap is working based on the concept of Hashing. Before moving into further, we should know the following concepts.

• Hashing
• Bucket
• Collision
• Entry

        Hashing - Assigning an unique code for all types of variable or object with the help of algorithm/function/formula.

       Bucket – Used to store Key Value pairs. It can have multiple key value pairs and this bucket will use LinkedList as an instance. Based on hash map length buckets will be created.

       Collision – If two key objects have same hashcode, then it is called collision.

       Entry – HashMap class have one inner class called Entry for storing your Key value pairs.

Structure of Entry class:

static class Entry implements Map.Entry
{
        final K key; //instance variable
        V value; // instance variable
        Entry next;
        final int hash;
        ...//More code goes here
}

Now let’s see how put(K key, V value) working

/**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with key, or
     *         null if there was no mapping for key.
     *         (A null return can also indicate that the map
     *         previously associated null with key.)
     */
    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

1.  First It will check whether given key is null or not. If specified Key is null then it will be stored at table [0]. Table [0] is nothing but, it is Bucket 0. It’s a rule; null should be always stored in index [0].
2. Important point to remember, HashMap can allow only one null key.
3.  Next if it is not null, hascode will be calculated for the key objects. This hascode will be useful to find the index of an array of your storing Entry object.(Key value)
4.  Next indexFor (hash, table.length) will be executed and correct index integer value will be returned for storing Entry object.
5.  There is a possibility two key object have same hashcode means Collison, and then it will be stored in the form of LinkedList.
6. Suppose if no object is present in index, then it will directly put Entry object there.
7. Suppose if any existing elements there, it will use next operation to find the place to put your Entry object. After finding it will put.
8.  Next key.equals (k) will be executed to avoid adding duplicate keys. This method will check whether key object is equal or not. If it is equal (TRUE) it will replace your old Entry object with new Entry object (Current Entry object).

Now let’s see how (K key) get working

/**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
     * key.equals(k))}, then this method returns {@code v}; otherwise
     * it returns {@code null}.  (There can be at most one such mapping.)
     *
     * 
A return value of {@code null} does not necessarily
     * indicate that the map contains no mapping for the key; it's also
     * possible that the map explicitly maps the key to {@code null}.
     * The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     *
     * @see #put(Object, Object)
     */
    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        for (Entry e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

1. First It will check whether given key is null or not. If specified Key is null then it will return value object of that key object. As it is null, value will be returned from Table[0](Bucket 0).
2. If it is not null, hashcode will be calculated for the key object.
3. Next it will identify where the exact index in table for the generated hashcode to get the Entry object with the help of indexFor (hash, table.length).
4.  Once table [] index was found, it iterate the LinkedList and will check for key equality by using key.equals (k). If it will return TRUE, then value object of that Key will be returned. Otherwise, null will be returned.

Happy learning.