How HashMap Works

HashMap stores the values in key-value pair and works on the concept of hashing.

Hashing

Hashing is a function which generates a unique value using some algorithms and functions. The first and foremost rule of hashing function is it has to generate the same hash always for the same value.

HashMap

HashMap as mentioned earlier, works on Hashing.

• It uses a hash table for storing the values in key-value pair. 
• table is an linked list of type Entry (an inner class) which stores the entries for the same hashCode.
• It can store key as null (only one).
• It has two methods get and put for storing and retrieving the values.

Hashing in HashMap

• To generate the hash value, we have to implement hashCode method for the key.
• HashMap does one more level of hashing because it may be possible that our implementation may not generate unique value of hash always [As unique value of hash to be generated always].
• Get the hashCode value defined and performs the hashing on top of it as below.

    final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        h ^= k.hashCode();
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

What equals() does?

• The uniqueness of a key is decided both on equals and hashCode methods.
• The hash is used for deciding the index of the bucket to store the value. 
• equals method is used to decide the equality of the values. 
• Two values having the same hashCode may not be equal. Those values are stored as an array in the same bucket. 
• But, two values which are equal (true with equals method) must have same hashCode

The following diagram explains the overview of objects stored in the HashMap

• HashMap internally stores the value in a list of buckets (named table) of type Entry.
• Each bucket (Entry) is a linked list of key-value pairs of same hashCode.
• Current key-value pair has a link to next entry 
• In the above hashMap, 
• There are two entries with hashCode H1 and three entries with hashCode H9 which are linked list
• Only one key/value pair stored for H14 and H16
• Other buckets are empty. 
• While storing or retrieving a value using a key. HashMap does the following
• Calculates the hashCode for the key 
• Finds the bucket for the key.
• Creates the bucket (If not exist) and stores the values in the linked list for the particular bucket [In case of put method]
• If bucket not found, returns null. Otherwise parse through the linked list for that particular bucket and finds the entry for the key[In case of get method].

How get method works

Look at the get method of HashMap

    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);
        return null == entry ? null : entry.getValue();
    }

Only three steps

1. It checks for null. If the key is null, then returns the value which stored at null key.
1. Value for null key is stored at location 0. Returns null if size is 0 otherwise value at null.
2. Gets the bucket entry for the key.
1. Performs hash of the key[as in above code of hash]. 
2. Find the bucket for that entry and parse through the table (linked list) and finds the value. 
3. If no entry found, returns null otherwise returns the value at the entry.

How put method works

The put method code is as follows

    public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> 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;
    }

Put method also works same as get method but little difference

• If key is null, adds the value at null key (Index 0).
• Get the bucket entry for the key.
• Performs hash of the key[as in above code of hash]. 
• Finds the entry with hashCode. If not there, creates it.
• Stores the value in the particular bucket and links to the previous element in the bucket(linked list).

One Note to remember that, put method always returns the old value present at the key. If it's newly stored then returns null.

Size of HashMap

• HashMap initially will be created with default capacity of 16. 
• We can explicitly specify the size of hashMap with an argument (int value)
• HashMap can have a maximum capacity of 1073741824

Happy Learning!!!!!