How HashMap works in Java

HashMap works on the principle of Hashing. There are several terms: key, hash code, hash function, bucket, entry in HashMap

public int hashCode()
hashCode returns an integer code, we can call this method as hash function

A bucket is used to store key value pairs . A bucket can have multiple key-value pairs . In hash map, bucket used simple linked list to store objects. In a bucket, there maybe one or more entries inside the linked list

hash (getting from hash(key.hashCode())) is used to find the bucket location at which the Entry object is stored . Entry object stores in the bucket like this (hash,key,value,bucketindex) .

How to avoid the conflict hash code ( for example, key 1 and key 2 might have the same hashcode), both records will be saved in the bucket as a linked list (two entries). When we want to receive the value for key2, it will get the bucket which has two entries in the list. we traverse through linked list , comparing keys in each entries using keys.equals() until it return true. Then the corresponding entry object Value is returned .

The figure below demos the concept how the data can be saved in the HashMap


In Summary
1. HashMap works on the principal of hashing
2. HashMap uses the hashCode() method to calculate a hash value. Hash value is calculated using the key object. This hash value is used to find the correct bucket where Entry object will be stored
3. HashMap uses the equals() method to find the correct key
4. more than one key have the same hash value, Entry objects are stored as a linked-list with in a same bucket. With in a bucket values are stored as Entry objects which contain both key and value.

Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedInShare on RedditShare on StumbleUponEmail this to someoneShare on TumblrDigg this

Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">