Overview

HashMap works based on the hashing principle. Hashing is the mechanism of assigning a code to a variable or attribute using an algorithm to enable easy retrieval.

Hashing will follow properties:

  • Objects that are equal but return different hash codes
  • Objects that are not equal but return the same hash code

Refer our article on What is hashCode() method in Java?

HashMap stores the Objects as Entry instances, not as key and value.

What Is Entry Class?

HashMap has an static class called an Entry Class which holds the key and values.

How Does put() Method Work Internally?

The internal implementation of the put() method will look like this:

Line 2: It checks if the key given is null or not. If the given key is null, it will be stored in the zero position, as the hashcode of null will be zero.

Line 4: It applies the hashcode to the key.hashCode() by calling the hashcode method. In order to get the value within the limits of an array, the hash(key.hashCode()) is called, which performs some shifting operations approximately 8 at default load factor on the hashcode.

Line 5: The indexFor() method is used to get the exact location to store the Entry object.

Line 12: If the map previously contained a mapping for the key, the old value is replaced and returns the previous value associated with the key or null if there was no mapping for key.

Line 17: Based on the calculated hash value HashMap implementation decides which bucket should store the particular Entry object. If calculated hash value is same, it will store entries in the same bucket. In the case of the Collision, the HashMap checks for the value of the next attribute if it is null it inserts the Entry object in that location, if next attribute is not null then it keeps the loop running till next attribute is null then stores the Entry object there.

In a nutshell, there can be three scenarios in case of put():

  • Using hashCode() method, hash value will be calculated. In which bucket particular entry will be stored is ascertained using that hash.
  • equals() method is used to find if such a key already exists in that bucket, if not found then a new node is created with the map entry and stored within the same bucket. A LinkedList is used to store those nodes.
  • If equals() method returns true, it means that the key already exists in the bucket. In that case, the new value will overwrite the old value for the matched key.
Entry Object with Key-Value
Pictorial representation of how Entry objects is stored in table array

How Does get() Method Work Internally?

Almost the same logic as applied in the put() method will be used to retrieve the value.

Line 2: It checks if the key given is null or not. If the given key is null, it will return values from zero position, as the hashcode of null will be zero.

Line 4: It applies the hashcode to the key.hashCode() by calling the hashcode method. In order to get the value within the limits of an array, the hash(key.hashCode()) is called, which performs some shifting operations approximately 8 at default load factor on the hashcode.

Line 7: If the correct bucket is found, it returns the value.

Line 10: If no match is found, it returns null.

Performance Enhancement for HashMap in Java 8

Though HashMap implementation provides constant time performance O(1) for get() and put() method, but that is in the ideal case when the Hash function distributes the objects evenly among the buckets.

But the performance may worsen in the case hashCode() used is not proper(O(n)) and there are lots of hash collisions. As we know now that in the case of hash collision entry objects are stored as a node in a LinkedList and equals() method is used to compare keys. That comparison to find the correct key within a LinkedList is a linear operation so in a worst case scenario the complexity becomes O(n).

To address this issue in Java 8 hash elements uses balanced trees instead of linked lists after a certain threshold is reached. Which means HashMap starts with storing Entry objects in linked list, but after the number of items in a hash becomes larger than a certain threshold, the hash will change from using a linked list to a balanced tree, this will improve the worst case performance from O(n) to O(log n).

It's good to share...Share on FacebookTweet about this on TwitterShare on LinkedInPin on PinterestShare on Google+Email this to someone

Leave a Reply

Your email address will not be published. Required fields are marked *