Friday, March 29, 2024
HomeJavaHow HashMap works in Java

How HashMap works in Java


HashMap in Java works on hashing ideas. It’s a knowledge construction that enables us to retailer object and retrieve it in fixed time O(1) offered we all know the important thing. In hashing, hash capabilities are used to hyperlink keys and values in HashMap. Objects are saved by the calling put(key, worth) methodology of HashMap and retrieved by calling the get(key) methodology. Once we name the put methodology, the hashcode() methodology of the important thing object is known as in order that the hash operate of the map can discover a bucket location to retailer the worth object, which is definitely an index of the interior array, often known as the desk. HashMap internally shops mapping within the type of Map.Entry object which comprises each key and worth object.

Whenever you wish to retrieve the article, you name
the get() methodology and once more cross the important thing object. This time once more key objects generate the identical hash code (it is obligatory for it to take action to retrieve the article and that is why HashMap keys are immutable e.g. String) and we find yourself on the identical bucket location. If there is just one object then it’s returned and that is your worth object which you’ve got saved earlier.

Issues get slightly tough when collisions happen. It is easy to reply this query if in case you have learn a superb ebook or course on knowledge construction and algorithms like these knowledge construction courses and books. If you know the way the hash desk knowledge construction works then this can be a piece of cake.

For the reason that inside array of HashMap is of mounted dimension, and if you happen to maintain storing objects, in some unspecified time in the future in time hash operate will return the identical bucket location for 2 completely different keys, that is referred to as collision in HashMap. On this case, a linked listing is fashioned at that bucket location and a brand new entry is saved as the following node.

If we attempt to retrieve an object from this linked listing, we’d like an additional test to seek for the right worth, that is carried out by the equals() methodology. Since every node comprises an entry, HashMap retains evaluating the entry’s key object with the handed key utilizing equals() and when it returns true, Map returns the corresponding worth.

Since looking out inlined listing is an O(n) operation, within the worst case hash collision reduces a map to a linked listing. This difficulty is lately addressed in Java 8 by changing the linked listing to the tree to look in O(logN) time. By the way in which, you’ll be able to simply confirm how HashMap works by wanting on the code of HashMap.java in your Eclipse IDE if you understand connect the supply code of JDK in Eclipse.

How HashMap Internally Works in Java?

How HashMap works in Java or typically how does get methodology works in HashMap is a quite common query on Java interviews these days. Nearly everyone who labored in Java is aware of about HashMap, the place to make use of HashMap, and the distinction between Hashtable and HashMap then why did this interview query turn out to be so particular? Due to the depth, it affords.


It has turn out to be a really well-liked Java interview query in virtually any senior or mid-senior stage Java interview. Funding banks largely choose to ask this query and typically even ask you to implement your individual HashMap primarily based upon your coding aptitude.

The introduction of ConcurrentHashMap and different concurrent collections has additionally made these questions a place to begin to delve right into a extra superior characteristic. let’s begin the journey.

internal working of HashMap in Java

Questions begin with a easy assertion:

1. Have you ever used HashMap earlier than or  What’s HashMap? Why do you employ it? 

Nearly everyone solutions this with sure after which the interviewee retains speaking about widespread information about HashMap like HashMap accepts null whereas Hashtable would not, HashMap isn’t synchronized, HashMap is quick, and so forth together with fundamentals like its shops key and worth pairs, and many others. 

This reveals that the individual has used HashMap and is sort of acquainted with the performance it affords, however the interview takes a pointy flip from right here and the following set of follow-up questions will get extra detailed in regards to the fundamentals concerned with HashMap in Java. Interviewer strike again with questions like:

2. Do you Understand how HashMap works in Java or How does get () methodology of HashMap works in Java

And you then get solutions like,  I do not trouble its normal Java API, you higher look code on Java supply or Open JDK; I can discover it out in Google at any time, and many others. However some interviewee undoubtedly solutions this and can say HashMap works on the precept of hashing, now we have put(key, worth) and get(key) methodology for storing and retrieving Objects from HashMap

Once we cross Key and Worth object to put() methodology on Java HashMap, HashMap implementation calls hashCode methodology on Key object and applies returned hashcode into its personal hashing operate to discover a bucket location for storing Entry object, the vital level to say is that HashMap in Java shops each key and worth object as Map.Entry in a bucket is important to know the retrieving logic. 


If individuals fail to acknowledge this and say it solely shops Worth within the bucket they may fail to elucidate the retrieving logic of any object saved in Java HashMap. This reply may be very a lot acceptable and does make sense that the interviewee has a good bit of data on how hashing works and the way HashMap works in Java.
However that is simply the beginning of the story and confusion will increase if you put the candidate on situations confronted by Java builders on daily foundation. The subsequent query may very well be about collision detection and collision decision in Java HashMap  like:

3. What’s going to occur if two completely different objects have the identical hashcode?

Now from right here onwards actual confusion begins, someday candidate will say that since hashcode is equal, each objects are equal and HashMap will throw an exception or not retailer them once more, and many others, You then would possibly wish to remind them about equals() and hashCode() contract that two unequal objects in Java can have the identical hashcode. 
Some will hand over at this level and few will transfer forward and say “Since hashcode is identical, bucket location can be identical and collision will happen in HashMap Since HashMap makes use of LinkedList to retailer object, this entry (object of Map.Entry comprise key and worth )  shall be saved in LinkedList. Nice this reply is sensible although there are lots of collision decision strategies out there like linear probing and chaining, that is the best, and HashMap in Java does comply with this. However the story doesn’t finish right here and the interviewer asks

4. How will you retrieve the Worth object if two Keys could have the identical hashcode?

how HashMap works internally in JavaThe interviewee will say we are going to name get() methodology after which HashMap makes use of Key Object’s hashcode to search out out bucket location and retrieves Worth object however then it’s good to remind him that there are two Worth objects are saved in the identical bucket, so they may say about traversal in LinkedList till we discover the worth object, you then ask how do you establish worth object as a result of you do not have worth object to check Till they know that HashMap shops each Key and Worth in LinkedList node or as Map.Entry they will not be capable of resolve this difficulty and can attempt to fail.

However these bunch of people that keep in mind this key data will say that after discovering bucket location, we are going to name keys.equals() methodology to establish an accurate node in LinkedList and return related worth object for that key in Java HashMap. Excellent that is the right reply.

In lots of instances, interviewee fails at this stage as a result of they get confused between hashCode() and equals() or keys and values object in Java HashMap which is fairly apparent as a result of they’re coping with the hashcode() in all earlier questions and equals() come within the image solely in case of retrieving worth object from HashMap in Java. 
Some good builders level out right here that utilizing an immutable, remaining object with correct equals() and hashcode() implementation would act as good Java HashMap keys and enhance the efficiency of Java HashMap by lowering collision
Immutability additionally permits caching their hashcode of various keys which makes the general retrieval course of very quick and means that String and numerous wrapper courses e.g. Integer excellent keys in Java HashMap.
How get method works in HashMap in Java


















Now if you happen to clear this complete Java HashMap interview,  You’ll be stunned by this very attention-grabbing query “What occurs On HashMap in Java if the scale of the HashMap exceeds a given threshold outlined by load issue ?”. Till you know the way HashMap works precisely you will not be capable of reply this query. If the scale of the Map exceeds a given threshold outlined by load-factor e.g. if the load issue is .75 it should act to re-size the map as soon as it crammed 75%. 
Just like different assortment courses like ArrayList,  Java HashMap re-size itself by creating a brand new bucket array of dimension twice the earlier dimension of HashMap after which begin placing each outdated factor into that new bucket array. This course of is known as rehashing as a result of it additionally applies the hash operate to discover a new bucket location. 

For those who handle to reply this query on HashMap in Java you can be greeted by “do you see any drawback with resizing of HashMap in Java”, you may not be capable of decide the context, after which he’ll attempt to offer you a touch about a number of threads accessing the Java HashMap and doubtlessly in search of race situation on HashMap in Java

So the reply is Sure there’s a potential race situation that exists whereas resizing HashMap in Java, if two thread on the identical time discovered that now HashMap wants resizing they usually each attempt to resize. on the method of resizing HashMap in Java, the factor within the bucket which is saved within the linked listing get reversed so as throughout their migration to the brand new bucket as a result of Java HashMap would not append the brand new factor on the tail as a substitute it append new factor on the head to keep away from tail traversing.

If race situation occurs then you’ll find yourself with an infinite loop. Although this level, you’ll be able to doubtlessly argue that what the hell makes you assume to make use of HashMap in a multi-threaded setting to interviewer 🙂

Some extra Hashtable and HashMap Questions 

Few extra query on HashMap in Java which is contributed by readers of the Javarevisited weblog:


5. Why String, Integer, and different wrapper courses are thought-about good keys?

String, Integer, and different wrapper courses are pure candidates of the HashMap key, and String is probably the most incessantly used key as nicely as a result of String is immutable and remaining, and overrides equals and hashcode() methodology. Different wrapper class additionally shares comparable property. 

Immutability is required, with a purpose to stop modifications on fields used to calculate hashCode() as a result of if a key object returns completely different hashCode throughout insertion and retrieval then it will not be attainable to get an object from HashMap


Immutability is greatest because it affords different benefits as nicely like thread-safety, For those who can maintain your hashCode the identical by solely making sure fields remaining, you then go for that as nicely. 

For the reason that equals() and hashCode() methodology is used throughout retrieval of worth objects from HashMap, it is vital that key objects appropriately override these strategies and comply with contact. If an unequal object returns completely different hashcode then the possibilities of collision shall be much less which subsequently improves the efficiency of HashMap.

6. Can we use any customized object as a key in HashMap?

That is an extension of earlier questions. In fact, you should use any Object as a key in Java HashMap offered it follows equals and hashCode contract and its hashCode shouldn’t fluctuate as soon as the article is inserted into Map. If the customized object is Immutable then this shall be already taken care of as a result of you cannot change it as soon as created.

7. Can we use ConcurrentHashMap rather than Hashtable?

That is one other query which getting well-liked as a result of growing recognition of ConcurrentHashMapSince we all know Hashtable is synchronized ConcurrentHashMap offers higher concurrency by solely locking a portion of the map decided by concurrency stage. ConcurrentHashMap is definitely launched as Hashtable and can be utilized rather than it, however Hashtable offers stronger thread-safety than ConcurrentHashMap. See my submit distinction between Hashtable and ConcurrentHashMap for extra particulars.

Personally, I like this query due to its depth and the variety of ideas it touches not directly if you happen to have a look at questions requested in the course of the interview this HashMap query has verified

  • The idea of hashing
  • Collision decision in HashMap
  • Use of equals () and hashCode () and their significance in HashMap?
  • The good thing about the immutable object?
  • Race situation on HashMap  in Java
  • Resizing of Java HashMap

Simply to summarize listed below are the solutions which do make sense for the above questions

8. How HashMap  works in Java

HashMap works on the precept of hashing, now we have put() and get() methodology for storing and retrieving objects from HashMap.Once we cross each key and worth to place() methodology to retailer on HashMap, it makes use of key object hashcode() methodology to calculate hashcode and them by making use of hashing on that hashcode it identifies bucket location for storing worth object. 

Whereas retrieving it makes use of the important thing object equals methodology to search out out the right key-value pair and return the worth object related to that key. HashMap makes use of a linked listing in case of collision and objects shall be saved within the subsequent node of the linked listing. Additionally, HashMap shops each key and worth tuples in each node of the linked listing within the type of Map.Entry object. 

9. What’s going to occur if two completely different HashMap key objects have the identical hashcode?

They are going to be saved in the identical bucket however no subsequent node of the linked listing. And keys equals () methodology shall be used to establish the right key-value pair in HashMap.

10. How null secret’s dealt with in HashMap? Since equals() and hashCode() are used to retailer and retrieve values, how does it work within the case of the null key?
The null secret’s dealt with specifically in HashMap, there are two separate strategies for that putForNullKey(V worth) and getForNullKey(). Later is an offloaded model of get() to lookup null keys.  Null keys all the time map to index 0.

This null case is break up out into separate strategies for the sake of efficiency within the two mostly used operations (get and put), however integrated with conditionals in others. Briefly, the equals() and hashcode() strategies are usually not used within the case of null keys in HashMap.

right here is how nulls are retrieved from HashMap

   non-public V getForNullKey() {

        if (dimension == 0) {
            return null;
        }
        for (Entry<Ok,V> e = desk[0]; e != null; e = e.subsequent) {
            if (e.key == null)
                return e.worth;
        }
        return null;
    }
When it comes to utilization, Java HashMap may be very versatile and I’ve largely used HashMap as a cache in an digital buying and selling utility I’ve labored on. For the reason that finance area used Java closely and as a consequence of efficiency causes we’d like caching HashMap and ConcurrentHashMap comes as very helpful there. You too can test the next articles from Javarevisited to be taught extra about HashMap and Hashtable in Java:


HashMap Modifications in JDK 1.7 and JDK 1.8

There’s some efficiency enchancment carried out on HashMap and ArrayList from JDK 1.7, which reduces reminiscence consumption. Attributable to this empty Maps are lazily initialized and can price you much less reminiscence. Earlier, if you create HashMap like new HashMap() it robotically creates an array of default size e.g. 16. 


After some analysis, the Java crew discovered that almost all of those Map are non permanent and by no means use that many parts, and solely find yourself losing reminiscence. Additionally, From JDK 1.8 onwards HashMap has launched an improved technique to take care of a excessive collision price. 


Since a poor hash operate e.g. which all the time return the situation of the identical bucket, can flip a HashMap right into a linked listing, like changing the get() methodology to carry out in O(n) as a substitute of O(1) and somebody can benefit from this reality, Java now internally substitute linked listing to a binary true as soon as a sure threshold is breached. This ensures efficiency or order O(log(n)) even within the worst case the place a hash operate isn’t distributing keys correctly.

Additional Studying
How does HashMap works in JavaIf you’re getting ready for Java interviews then I recommend you check out the Java Interview Information: 200+ Java Interview questions, a superb useful resource for all ranges of Java programmers. This ebook comprises questions from all vital Java subjects. You too can be a part of these greatest Knowledge Buildings and Algorithms programs to brush up on a few of your knowledge construction and algorithm abilities. 


Associated submit:

And, if you happen to choose to look at than learn then you can even try this tutorial on our Youtube channel the place now we have talked in regards to the inside working of HashMap and How HashMap works usually. If you wish to obtain notifications about new tutorials, you’ll be able to subscribe to our Youtube channel right here. 

Thanks for studying this text thus far. For those who like this HashMap tutorial then please share it with your folks and colleagues. You probably have any questions or suggestions then please drop a notice. 

P. S. – If you’re new to the Java growth world and wish to be taught Java Assortment in-depth, together with courses like ConcurrentHashMap and HashMap then you can even try these greatest Java Assortment programs to be taught them in depth. 



RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments