What is the internal Implementation of HashMap in java?

In HashMap,objects are stored in the form of array of Entry objects.

 

                                            transient Entry[ ] table;

 

Now, note that Entry class contains properties like key,value,next and hash.This properties will be used by the HashMap class.

Now, lets see stepwise put(key,value) method implementation.

step1: Check whether given key is null or not.If the given key is null then call a method putForNullKey(value).Lets see this method's implementation.

Since hashcode for null is always 0, so null key is stored at table[0] position. Now, in this bucket any object may contain null as key.So using for loop each Entry object is checked for null key. If any object contains null as key then the value for null key is replaced with new one and the old value is returned.See the diagram below.

recordAccess(this) method is invoked whenever the value in an entry is overwritten by an invocation of put(k,v) for a key k that's already in the HashMap.

step 2: Now hashcode() method is used with the key to get the hashcode value.This hashcode generated is used with the hash(int h) function to get the hashcode value. This hash(int h) function defends against poor quality hash functions. Now, with this hashcode  indexFor(int h, int length) method is called to get the index or bucket where the object will be stored.Again, for loop is used to check whether the key is already available or not, if available, then the old value is replaced with new one and the old value is returned.Finally, addEntry(hash, key, value, i) method is called which adds a new entry with the specified key, value and hash code to the specified bucket.Implementation of addEntry() is given below.

get( Object key) method implementation is shown below----

The given key is checked for null key. If the given key is null then getForNullKey() method is called.If the given key is not null then hashcode() method is called with the key to get the hashcode value.Note that for the same key always same hashcode value is generated by the hashcode() method.Now, hash(int h) function is used to get the index or bucket where the key will be available.Again, using for loop each object in the bucket is checked for matching key, if found value will be returned otherwise null will be returned.

 

 

You may also like -----

What is bucket in HashMap or HashTable