HASHMAP IN JAVA & HOW IT WORKS INTERNALLY

Hashmap is one of the popular classes in Java, and it is a hashtable-based implementation of the Map interface.  What does it mean that hashmap is a map? A map is a key-value mapping, that every key is mapped to exactly one value and we can use that key to retrieve the corresponding value from the hashmap.

Now a question comes, why do we need to store data in key-value format why not just add values in the list? Well, the reason is performance, the time complexity to find the specific element in the list is O(n) and O(log n) if the list is sorted, but in hashmap the time complexity to insert and retrieve a value is O(1) on average. We can look at the time complexity later in this blog.

KEY POINTS ABOUT HASHMAP IN JAVA:

·       Hashmap in Java is part of Java. util package

·       It allows duplicate values but the key must be unique, in case where there are duplicate keys the last one will override the other(s).

·       It permits multiple null values  and a single  null key

·       Hashmap doesn’t maintain an order for insertion. It iterates over entries through a key set.

·       Hashmap is equivalent to hashtable except hashmap is not synchronized (not thread safe), to make it thread-safe we have to synchronize externally or use concurrent hashmap

·       We can store different or the same datatype for keys and values. For example: The key is an integer and values as a String or both integer or string.

·       The datatypes are specified using the wrapper class instead of the primitive datatype.

·       It uses a hash function to compute an index based on the key that suggests where an entry can be found or inserted.

·       Insertion is through the put() and to retrieve an element we have to use get().

CONSTRUCTORS IN HASHMAP:

1.HashMap()

This creates an empty constructor with default size 16 and load factor 0.75.

Example:HashMap<String ,Integer> demo_map=new HashMap<String ,Integer>();

2.HashMap(int initialcapacity)

This creates the empty hashmap with the given capacity as size and load factor 0.75.

Example: HashMap<String ,Integer> demo_map_size=new HashMap<String ,Integer>(5);

demo_map_size created with capacity 5 and the loadfactor 0.75.

3.HashMap(int initialcapacity, float loadfactor)

Constructs an empty hashmap with the specified capacity and load factor.

Example:HashMap<String ,Integer> demo_map_load=new HashMap<String ,Integer>(5,0.75f);

4. HashMap(Map<?extendsK,?extends V>m)

  This creates a new hash map with same mappings as the specified map.

Example:HashMap<String ,Integer> demo_map=new HashMap<String ,Integer>();

HashMap<String ,Integer> demo_map1=new HashMap<String ,Integer>(demo_map);

BASIC OPERATIONS OF HASHMAP:

The hashmap includes basic operation like add ,get,update and delete the elements just like any other datastrucutre. Following are some of the basic operations :

1)ADD Elements

To insert elements into the hashmap a put() with key and value is used put(Key,Value).

2)Remove Elements

We can remove the element from the hashmap by using the key as an argument and delete the entry for the given key if its present in the hashmap or remove(k,v) which takes both key and value as a argument and delete the entry from the hashmap only if both key-value pair match.

3)Access Elements

3.1)To access particular element

To access the particular element , we can pass the key as an argument and retrieve the corresponding value from the hashmap. We can access the value present in the hashmap by using get(key) .

3.2) To access only the keys of the element

To retrieve all the keys of an element from the hashmap then keyset() is used. This will return just the set of the keys in hashmaps.

3.3 ) To retrieve the values alone from the hashmap

The values() used to get all the values of the key from the hashmap. This return just the set of values.

3.4)To access the entries of hashmap

The entrySet() will return the set of entries (<K,V>) from the hashmap.

3.5)Traverse the Hashmap:

We can use for each loop and then access the key and value in the entry using getKey() and getValue(). Map.Entry(K,V) allows us to access the entries of map.

Example:

demo_map.put("RedTeam",10);

demo_map.put("BlueTeam",20);

demo_map.put("GreenTeam",30);

demo_map.put("YellowTeam",40);

demo_map.put("OrangeTeam",50);

for(Map.Entry<String, Integer> m : demo_map.entrySet())

{

System.out.println(m.getKey()+","+m.getValue());

}

4)Update

put(K,V) this method is used to update the value associated with the given key , or we can use replace().

In the above example if we want to update GreenTeam value to 45 then :demo_map.put("GreenTeam",45);

or we can use :demo_map. replace("GreenTeam",45);

INTERNAL STRUCTURE OF HASHMAP:

Considering the internal structure of the hashmap, it has a Node<K, V> which represents the inner class Entry<K, V> to store the mappings of the hashmap. Each key-value pair stored as an object of the Entry<K,V>class. This class is a static inner class of hashmap.  Each node has four fields:

·       Key-The key attribute stores the key and it is of the final type

·       Value-Value attribute holds the value of the element

·       Hash - This attribute stores the hashcode of the key.

·       Nextnode: The Entry<K, V>  next holds the pointer to the next key-value pair.

1.Buckets are the array of nodes or entries that store the element. This has a different capacity, the default capacity is 16 .

2.Hashing:

Hashmap doesn’t insert the element like how we do in the array based on the index. Instead, it uses the technique called hashing, which is a two-step process that converts the given key into a hash using the hashcode() and uses the hashcode of the key to find the index that determines where the element should be placed.

3.HashCollision:

When distinct keys have the same hashcode value then it is called hash collision, in that case, a Linked-list or a balanced tree structure gets created and the value in the next entry node is populated.

PERFORMANCE OF HASHMAP: An instance of hashmap has two parameters that affects its performance which are : initial capacity and load factor.

1.Initial capacity of Hashmap:

The capacity of the hashmap is no of buckets in the hashtable.  By default, it is 16. The capacity of the hashmap gets doubled every time it reaches the threshold.

2.Load Factor:

It is a measure of how much percentage the hashmap are  allowed to insert the elements before it increase its capacity. The default load factor is 0.75 ranging between 0 to 1. Some of the terms related to performance are :

Threshold:

This is calculated as a product of the load factor and the capacity of the hashmap.

Threshold= current capacity * load factor

The default threshold value is calculated by, the initial capacity of 16  and the load factor of 0.75 :

Default Threshold=16*0.75=12

This means after adding 12 elements to the hashmap, we have to start rehashing which will double the capacity of the hashmap.

Rehashing is the process of increasing the capacity in the form of 2 power n, initially, it is 2^4=16 when the threshold is reached the value will be increased in the 2^n series where n=5,6, etc, and the capacity will be 2^5=32,2^6=64, etc.

This process of rehashing is both space and time-consuming. So we must choose initial capacity by keeping the number of expected elements in mind so that the rehashing process doesn’t occur frequently.

Regarding the load factor, the default 0.75 offers a good tradeoff between time and space costs.

For example, if we choose the load factor as 1.0f then rehashing takes place after 100% of the current capacity  which will save the space but this will increase retrieval time of the existing element.

If we use 0.50f then rehashing takes place after 50% of the current capacity which leads to an increase in number of rehashing processes, which will degrade the performance of the hashmap in time and space. So always choose the initial capacity and load factor such that it will minimize the rehashing process.

Let's see an example on how put() and get() work internally:

Step1: Hashmap colormap=new Hashmap();

This creates an empty hashmap object with a default initial capacity of 2^4 which is 16 and a default load factor/ fill ratio of 0.75.

It will create an empty bucket with 16 nodes, then it will start adding the elements when insertion occurs.

Step 2: Inserting key-value pair: colormap.put(1,”green”);

It will calculate the hash code of the key  1, which is 210678.

Note: we can check the hash code of the key using hashcode () as:

System.out.println(color. get(1).hashcode());// which gives 210678

Step 3: Now it will calculate the index by using index=hashcode(key) & (n-1)

So, for this node, it will be index 2.

Step 4: Now this will add the element in the index “2” if there is no object is present.

When we add a next key-value colormap.put (6,” yellow”) which turned out to have the same hash code and the same index i.e. 2, in that case, this will create a new node linking to its previous node. Same for the key-value pair(7,” orange”).

These 3 nodes with the key (1,6,7) give a view of the Linked list. So whenever we are adding elements, hashmap it blindly doesn’t allocate the slot in the bucket, it will call the hash() on the key to get the hash and index value.

In case of a null key, it adds the key-value pair in the reserved place which is index 0 with the hash value as 0.  This is the process of adding the elements into the hashmap.

Now Let's see how  get () works:

Example: String color_name=colormap.get(3) ;

                   System.out.println(“Retrieving value by key :”+color_name);

1)    First it will calculate the hash code of the key(3). It will be generated as 210780

2)    Next it will calculate the index and it will be 8.

3) Now it will go to index 8 of the array and compare the elements key with the given key using equals(), if both are equal it will retrieve the value of the key 3 which is “white”, otherwise it will check for the next existing element.

THE TIME COMPLEXITY OF HASHMAP:

The performance of the hashmap depends on the hash function implementation. If there is no hash collision then the time complexity is O(1). If the hash implementation has hash collision then the complexity will be O(n).

CHANGES IN JAVA 8 IMPLEMENTATION:

To improve the working of hashmap, Java 8 updates the internal implementation workflow which handles the hash collision in a better way.

Before Java 8 the when a collision occurs the hashmap use a linked list which  has low performance which impacts the complexity. Both the key and the value were placed in a node, and in the worst case, the complexity is O(n) due to link traversal.

The changes made in Java8 are: Once certain threshold level is reached the values are now automatically store in a tree manner rather than a linked list. So instead of  O(n) retrieval time, we now have better O(log n) retrieval performance.

That’s all about the introduction and internal working of hashmap, Thank you all for reading till the end. Happy Learning!!