Hashmap in Java

If anybody asks me to describe “How HashMap works?“, I simply answer: “On principle of Hashing“. HashMap is a Collection which works on principle of Hashing and it uses key and value pairs to store the information and we can get the value if we pass key to the HashMap. You can also say HashMap is fast as it is not synchronized.

HashMap class comes from java.util package and HashMap class extends AbstractMap and implements Map, Cloneable and Serializable interfaces. HashMap is nothing but Hash table based implementation of Map Interface.

What is Hashing

Hashing in its simplest form, is a way to assigning a unique code for any variable/object after applying any formula/algorithm on its properties. A true Hashing function must follow this rule:

Hash function should return the same hash code each and every time, when function is applied on same or equal objects. In other words, two equal objects must produce same hash code consistently.

Note: All objects in java inherit a default implementation of hashCode() function defined in Object class. This function produce hash code by typically converting the internal address of the object into an integer, thus producing different hash codes for all different objects.

A little about Entry class

A map by definition is : “An object that maps keys to values”. Very easy.. right?
So, there must be some mechanism in HashMap to store this key value pair. Answer is YES. HashMap has an inner class Entry, which looks like this:

static class Entry implements Map.Entry{

          final K key;

          V value;

          Entry next;

          final int hash;

          ...

}

Surely Entry class has key and value mapping stored as attributes. Key has been marked as final and two more fields are there: next and hash.

put() method in hashmap

We need to pass Key and Value object to put() method in Java HashMap. Once we pass the key and value to in put() method of HashMap, HashMap calls hashCode method on key object and use hashcode into own hashing function to find the bucket location. Bucket is the place where Entry object is stored and hashcode is like an address of that bucket. So what exactly we store in bucket? This is very important to understand. Java stores both Key and Value object as a Map.Entry in bucket. These are stored like LinkedList. But why these are stored as LinkedList. As we know we are using the hashcode to find the bucket location but two unequal objects can have same hashcode. So there are chances of collision. So along with value key is stored.

get() methods in hashmap

We need to pass key to the get method which takes the key as an argument and try to find bucket position using the hashcode. Once it finds the bucket using equals function it gets the value and returns it.

If no match is found, get() method returns null.

Key Notes

• Data structure to store Entry objects is an array named table of type Entry.
• A particular index location in array is referred as bucket, because it can hold the first element of a LinkedList of Entry objects.
• Key object’s hashCode() is required to calculate the index location of Entry object.
• Key object’s equals() method is used to maintain uniqueness of Keys in map.
• Value object’s hashCode() and equals() method are not used in HashMap’s get() and put() methods.
• Hash code for null keys is always zero, and such Entry object is always stored in zero index in Entry[].
• Order in not maintained in hashmap.

What is the load factor in java HashMap and what happens when size of the HashMap exceeds a given threshold defined by load factor?

Load factor of HashMap is is .75 it will act to re-size the map once it filled 75%, so once size exceeds 75%, then Java HashMap re-size itself by creating a new bucket array of size twice of size defined previously for the HashMap ,then it start putting every old element into that new bucket array. This process is also called rehashing because hash function is used to find the new bucket location.