How HashMap works in java

By | May 27, 2014

Believe it or not but you will be asked questions on HashMaps in 8 out of 10 interviews .And this is the most frequently asked question How HashMap works in java ? While some candidates are able to answer this question but they fail to answer the surrounding questions .In this article we will explain you in detail how HashMap works in java and we have provided the answer to most frequently asked interview questions .We are 100% sure that if you have read this post you will be able to answer any question on HashMaps in your interview.So lets start .

What is HashMap? Why do we use it ?

This is the first question you will be asked . Hash table based implementation of the Map interface.

We can store key-value pairs in a HashMap<K,V> using the put(key,value) method and retrieve the value
for a particular key using the get(Key) method .This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent toHashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the “capacity” of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it’s very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important. Refer this article for more information.

What’s the difference between HashMap and Hashtable ?

The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.Moreover hashtable .Hashtable was part of the original java.util and is a concrete implementation of a Dictionary.However, Java 2 re-engineered Hashtable so that it also implements the Map interface. Thus, Hashtable is now integrated into the collections framework.

How HashMap works internally in java ?

This is the most important question and most of the candidates fail to answer this even though you know the concept.For better understanding try to code you own custom HashMap in java. HashMap works on principle of hashing, we have put(key, value) and get(key) method for storing and retrieving Objects from HashMap. When we pass Key and Value object to put() method on Java HashMap, HashMap implementation calls hashCode method on Key object and applies returned hashcode into its own hashing function to find a bucket location for storing Entry object, important point to remember is that HashMap in Java stores both key and value object as Map.Entry in bucket which is essential to understand the retrieving logic. This is actually how the implementation should be as I said earlier try to code you own custom HashMap in java . If people fails to recognize this and say it only stores Value in the bucket they will fail to explain the retrieving logic of any object stored in Java HashMap

What happens when two different objects have same hashcode?
Most of the candidates get confused here.Don’t worry this is what you should say.The hashcode is used only to find the bucket location .Since hashcode is same, bucket location would be same and collision will occur in HashMap.Java is using the chaining collision resolution technique to handle collisions. Since HashMap use LinkedList to store object, this entry (the key-value pair entry ) will be stored in LinkedList as the next node.

How the value is retrieved when two keys have the same hashcode ?
Note that there can be only one entry in the HashMap with a particular key but the hashcode of two keys can be same.If you have read the question just before you will be able to answer this question.This question is like how the HashMap.get() method works internally.Here’s the answer When the get(key) method is called HashMap uses Key Object’s hashcode to find out bucket location , but as we know to different key’s can have the same hashcode .SO after finding the bucket location.It traverses the linkedlist for that bucket and calls key.equals() method to check the entry having same key.And returns the value for the node having the same key.

What is LoadFactor for HashTable ?
This is more a datastructure question than a java question.The load factor (generally value 0.75)is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.It is considered that once the size of hashtable reaches load factor*the current capacity the operations of insertion and deletion start taking too much time. So its better to resize it.Java HashMap re-size itself by creating a new bucket array of size twice of previous size of HashMap , and then start putting every old element into that new bucket array. This process is called rehashing because it also applies hash function to find new bucket location.

Why String and other wrapper classes are considered good keys ?
String is most frequently used as key because String is immutable and final,and overrides equals and hashcode() method. Other wrapper class also shares similar property. Immutabiility is required, in order to prevent changes on fields used to calculate hashCode() because if key object return different hashCode during insertion and retrieval than it won’t be possible to get object from HashMap. Immutability is best as it offers other advantages as well like thread-safety, If you can keep your hashCode same by only making certain fields final, then you go for that as well. Since equals() and hashCode() method is used during reterival of value object from HashMap, its important that key object correctly override these methods and follow contact. If unequal object return different hashcode than chances of collision will be less which subsequently improve performance of HashMap.See this article for more information Immutable Objects in Java.

What is the difference between a ConcurrentHashMap and a Hashtable in Java ?
This is more a kind of knowledge based question than a logical question.ConcurrentHashMap uses multiple buckets to store data. This avoids read locks and greatly improves performance over a HashTable. Both are thread safe, but there are obvious performance wins with ConcurrentHashMap.When you read from a ConcurrentHashMap using get(), there are no locks, contrary to the Hashtable for which all operations are simply synchronized. HashTable was released in old versions of Java whereas ConcurrentHashMap is a java 5+ thing.

Leave a Reply

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