HashMap Internal Working - Java

Hashmap working in java

   Hashmap class is equivalent to hashmap besides two things that they are unsynchronized any permits null value.

So what is hashing ?

Hashing means that you use a function or method or algorithm to represent an object with an integer value which makes finding that element quite easy in a storage that can be hashtable ,hashmap or anything that is using hash technique.

Hashmap

Hash map is a collection in which the elements are stored as key-value pair and each element stored is known as an Entry object .

Entry object is an object of  a class named as Entry class which contains :

1.key

2.value.

3.next

4.hash

Now we will look how actually hashmap works and how values are stored in hashmap and retrieved from it?

There are main  methods used for storing and retereiving values from hash map

1.    put() method à to put /store values in hashmap

2.    get() methodàto retrieve data/values from hasmap

Values above means objects not the actual value .

Besides these two methods two more methods plays a vital role in working of hasmap

hashcode()

equals()

Both these methods are defined in Object class only .

Now let us assume we have a map and we put some elements inside it

HashMap<string,string> countryCapitalMap=new HashMap<string,string>();         countryCapitalMap.put(india,"Delhi");         countryCapitalMap.put(japan,"Tokyo");        countryCapitalMap.put(france,"Paris");         countryCapitalMap.put(russia,"Moscow");

So in the above example we have 4 entry objects with 4 key –value pair.

Now we are using put () method to add these objects to a hashmap name countryCapitalmap.

Let look inside code of put() method

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

First ,hashcode method calculates hashcode of key .

This hashcode actually indicates the index of array which stores entry objects.

The objects are stored in a single link list corresponding to each index which is also konwn as bucket

If two keys have same hashcode that means they will stored on the same index but in the same bucket or linked list .

Let us assume that we have four values in our hashmap.

countryCapitalMap.put(india,"Delhi");         countryCapitalMap.put(japan,"Tokyo");        countryCapitalMap.put(france,"Paris");         countryCapitalMap.put(russia,"Moscow");

And assume that hascode calculated on each key comes as

                                           India ->0

                                           Japan ->0

                                           France->1

                                           Russia ->2

                                           China->2

Hashmap Internal working

By default the size of hashmap is 16 that means there will be 16 buckets and 16 indexes .Here I have shown only 5.

Each node of a link list stores an Entry object which conatins following things

	Key Value Next hash

Above for illustration purposes I have shown only key.

So as india’s hashcode comes as 0and japan’s also 0 ,so the entry object corresponding to india will be stored in first node of linked list at 0 index and as entry object corresponding to japan also have same hashcode so it will stored in the next node to india and next pointer of india will point to japan’s entry object.

You will be confused that when hashcode of both keys is same then the value of india entry object should be replaced no but when hashcode of two entry objects Is same at that time equals() method comes into play .when we have to store key with same hashcode then first equals method checks whether the key for which value is to be stored and the key which is already present in hashmap is same ,if both are same then the value in entry object  is replaced by new value otherwise a new node is created and the new entry object( japan in our case) is stored.

Working of Get method in hashmap

Get method in hashmap is used to retrieve value from hashmap corresponding to a key.

Code of method get () of HashMap:

public V get(Object key) { 20   if (key == null) 21    return getForNullKey(); 22   int hash = hash(key.hashCode()); 23   for (Entry<k , V> e = table[indexFor(hash, table.length)]; e != null; e =     e.next) { 24    Object k; 25    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 26     return e.value; 27   } 28   return null; 29  }

First, same as put method , hashcode of key is calculated .

Then according to hashcode the index in array means index of bucket in which value/entry object is stored.

If there is only one node in the bucket/link list then the value is retrieved from that node.

If there are more than one node in the linklist then  equals() method comes into play .equals( ) methods traverse the list and compare value of each key present in bucket with the one for which we have to retrieve value  and retrieves value from entry object .

Author : Himanshu Bector