<div dir="ltr" style="text-align: justify;" trbidi="on"><i><b>What is Hashing?</b></i><br />
Hashing in its simplest form, is a way to assigning a unique code for any variable/object after applying any formula/algorithm on its properties. A true Hashing function must follow this rule:</p>
<p> Hash function should return the same hash code each and every time, when function is applied on same or equal objects. In other words, two equal objects must produce same hash code consistently.</p>
<p> <i><b>Note:</b></i> All objects in java inherit a default implementation of <b>hashCode()</b> function defined in Object class. This function produce hash code by typically converting the internal address of the object into an integer, thus producing different hash codes for all different objects.</p>
<div align='center' id="ads-id"></div>
<p><b>HashMap is an array of Entry objects:</b><br />
Consider HashMap as just an array of objects.</p>
<p>Have a look what this Object is:</p>
<pre class="highlight" name="code">static class Entry<;K,V>; implements Map.Entry<;K,V>; { 
 final K key; 
 V value; 
 Entry<;K,V>; next; 
 final int hash; 
... 
} 
</pre>
<p>
Each Entry object represents key-value pair. Field next refers to other Entry object if a bucket has more than 1 Entry.</p>
<p> Sometimes it might happen that <i><b>hashCodes </b></i>for 2 different objects are the same. In this case 2 objects will be saved in one bucket and will be presented as <i><b>LinkedList</b></i>. The entry point is more recently added object. This object refers to other object with next field and so one. Last entry refers to null.<br />
When you create <i><b>HashMap </b></i>with default constructor</p>
<pre class="highlight" name="code">HashMap hashMap = new HashMap(); 
</pre>
<p>Array is gets created with size 16 and default 0.75 load balance.</p>
<div class="separator" style="clear: both; text-align: center;"><img border="0" src="https://dineshonjava.com/wp-content/uploads/2013/06/Hash_Map3.jpg" title="How does java Hashmap work internally"/></div>
<p></p>
<div style="background-color: white; border: 0px none; clear: both; font-family: Arial,'Liberation Sans','DejaVu Sans',sans-serif; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 18px; margin: 0px 0px 1em; padding: 0px; text-align: left; text-indent: 0px; text-transform: none; vertical-align: baseline; white-space: normal; word-spacing: 0px; word-wrap: break-word;"><b style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; font-size: 14px; font-weight: bold; margin: 0px; padding: 0px; vertical-align: baseline;">Adding a new key-value pair</b></div>
<ol style="background-color: white; border: 0px none; font-family: Arial,'Liberation Sans','DejaVu Sans',sans-serif; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 18px; list-style: decimal outside none; margin: 0px 0px 1em 30px; padding: 0px; text-align: left; text-indent: 0px; text-transform: none; vertical-align: baseline; white-space: normal; word-spacing: 0px;">
<li style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline; word-wrap: break-word;">Calculate <i><b>hashcode </b></i>for the key</li>
<li style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline; word-wrap: break-word;">
<div style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; clear: both; font-size: 14px; margin: 0px 0px 1em; padding: 0px; vertical-align: baseline; word-wrap: break-word;">Calculate position ;hash % (arrayLength-1)) ;where element should be placed(bucket number)</div>
</li>
<li style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline; word-wrap: break-word;">
<div style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; clear: both; font-size: 14px; margin: 0px 0px 1em; padding: 0px; vertical-align: baseline; word-wrap: break-word;">If you try to add a value with a key which has already been saved in <i><b>HashMap</b></i>, then value gets overwritten.</div>
</li>
<li style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline; word-wrap: break-word;">Otherwise element is added to the bucket. If bucket has already at least one element &#8211; a new one is gets added and placed in the first position in the bucket. Its ;next ;field refers to the old element.</li>
</ol>
<div style="background-color: white; border: 0px none; clear: both; font-family: Arial,'Liberation Sans','DejaVu Sans',sans-serif; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 18px; margin: 0px 0px 1em; padding: 0px; text-align: left; text-indent: 0px; text-transform: none; vertical-align: baseline; white-space: normal; word-spacing: 0px; word-wrap: break-word;"><b style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; font-size: 14px; font-weight: bold; margin: 0px; padding: 0px; vertical-align: baseline;">Deletion:</b></div>
<ol style="background-color: white; border: 0px none; font-family: Arial,'Liberation Sans','DejaVu Sans',sans-serif; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 18px; list-style: decimal outside none; margin: 0px 0px 1em 30px; padding: 0px; text-align: left; text-indent: 0px; text-transform: none; vertical-align: baseline; white-space: normal; word-spacing: 0px;">
<li style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline; word-wrap: break-word;">Calculate <i><b>hashcode </b></i>for the given key</li>
<li style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline; word-wrap: break-word;">Calculate bucket number (hash % (arrayLength-1))</li>
<li style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline; word-wrap: break-word;">Get a reference to the first Entry object in the bucket and by means of equals method iterate over all entries in the given bucket. Eventually we will find correct Entry. If desired element is not found &#8211; return ;null</li>
</ol>
<p><b>What <i>put()</i> method actually does:</b><br />
Before going into <b>put()</b> method’s implementation, it is very important to learn that instances of <i><b>Entry </b></i>class are stored in an array. <i><b>HashMap </b></i>class defines this variable as:</p>
<pre class="highlight" name="code">/** 
 * The table, resized as necessary. Length MUST Always be a power of two. 
 */ 
 transient Entry[] table; 
</pre>
<p>Now look at code implementation of <i><b>put()</b></i> method:</p>
<pre class="highlight" name="code">/** 
 * Associates the specified value with the specified key in this map. If the 
 * map previously contained a mapping for the key, the old value is 
 * replaced. 
 * 
 * @param key 
 * key with which the specified value is to be associated 
 * @param value 
 * value to be associated with the specified key 
 * @return the previous value associated with <;tt>;key<;/tt>;, or <;tt>;null<;/tt>; 
 * if there was no mapping for <;tt>;key<;/tt>;. (A <;tt>;null<;/tt>; return 
 * can also indicate that the map previously associated 
 * <;tt>;null<;/tt>; with <;tt>;key<;/tt>;.) 
 */ 
 public V put(K key, V value) { 
 if (key == null) 
 return putForNullKey(value); 
 int hash = hash(key.hashCode()); 
 int i = indexFor(hash, table.length); 
 for (Entry<;k , V>; e = table[i]; e != null; e = e.next) { 
 Object k; 
 if (e.hash == hash &;&; ((k = e.key) == key || key.equals(k))) { 
 V oldValue = e.value; 
 e.value = value; 
 e.recordAccess(this); 
 return oldValue; 
 } 
 } 
 
 modCount++; 
 addEntry(hash, key, value, i); 
 return null; 
 } 
</pre>
<p>
<b>Lets note down the steps one by one:</b></p>
<p> <b>Step1-</b> First of all, key object is checked for null. If key is null, value is stored in table[0] position. Because hash code for null is always 0.</p>
<p> <b>Step2</b>&#8211; Then on next step, a hash value is calculated using key’s hash code by calling its <b>hashCode()</b> method. This hash value is used to calculate index in array for storing Entry object. JDK designers well assumed that there might be some poorly written <i><b>hashCode()</b></i> functions that can return very high or low hash code value. To solve this issue, they introduced another hash() function, and passed the object’s hash code to this hash() function to bring hash value in range of array index size.</p>
<p> <b>Step3- </b>Now<i><b> indexFor(hash, table.length)</b></i> function is called to calculate exact index position for storing the Entry object.</p>
<p> <b>Step4</b>&#8211; Here comes the main part. Now, as we know that two unequal objects can have same hash code value, how two different objects will be stored in same array location [called bucket].</p>
<p>Answer is <b>LinkedList</b>. If you remember, Entry class had an attribute “next”. This attribute always points to next object in chain. This is exactly the behavior of LinkedList.</p>
<p>So, in case of collision, Entry objects are stored in LinkedList form. When an Entry object needs to be stored in particular index, HashMap checks whether there is already an entry?? If there is no entry already present, Entry object is stored in this location.</p>
<p>If there is already an object sitting on calculated index, its next attribute is checked. If it is null, and current Entry object becomes next node in LinkedList. If next variable is not null, procedure is followed until next is evaluated as null.</p>
<p>What if we add the another value object with same key as entered before. Logically, it should replace the old value. How it is done? Well, after determining the index position of Entry object, while iterating over LinkedList on calculated index, HashMap calls equals method on key object for each Entry object. All these Entry objects in LinkedList will have similar hash code but equals() method will test for true equality. If key.equals(k) will be true then both keys are treated as same key object. This will cause the replacing of value object inside Entry object only.</p>
<p>In this way, HashMap ensure the uniqueness of keys.</p>
<p><b>How <i>get()</i> methods works internally</b><br />
Now we have got the idea, how key-value pairs are stored in HashMap. Next big question is : what happens when an object is passed in get method of HashMap? How the value object is determined?</p>
<p>Answer we already should know that the way key uniqueness is determined in put() method , same logic is applied in get() method also. The moment HashMap identify exact match for the key object passed as argument, it simply returns the value object stored in current Entry object.</p>
<p>If no match is found, get() method returns null.</p>
<p>Let have a look at code:</p>
<pre class="highlight" name="code">/** 
 * Returns the value to which the specified key is mapped, or {@code null} 
 * if this map contains no mapping for the key. 
 * 
 * <;p>; 
 * More formally, if this map contains a mapping from a key {@code k} to a 
 * value {@code v} such that {@code (key==null ? k==null : 
 * key.equals(k))}, then this method returns {@code v}; otherwise it returns 
 * {@code null}. (There can be at most one such mapping.) 
 * 
 * <;/p>;<;p>; 
 * A return value of {@code null} does not <;i>;necessarily<;/i>; indicate that 
 * the map contains no mapping for the key; it's also possible that the map 
 * explicitly maps the key to {@code null}. The {@link #containsKey 
 * containsKey} operation may be used to distinguish these two cases. 
 * 
 * @see #put(Object, Object) 
 */ 
 public V get(Object key) { 
 if (key == null) 
 return getForNullKey(); 
 int hash = hash(key.hashCode()); 
 for (Entry<;k , V>; e = table[indexFor(hash, table.length)]; e != null; e = e.next) { 
 Object k; 
 if (e.hash == hash &;&; ((k = e.key) == key || key.equals(k))) 
 return e.value; 
 } 
 return null; 
 } 
</pre>
<div style="background-color: #f2f9fc; border-radius: 3px; border: 1px solid #c9e6f2; line-height: 1.45; padding: 16px;">
<b>Java Collections Tutorial</b></p>
<ol style="text-align: left;">
<li><b><a href="https://dineshonjava.com/arraylist-class-in-java-collection/">ArrayList class</a></b></li>
<li><b><a href="https://dineshonjava.com/linkedlist-class-in-collection/">LinkedList class</a></b></li>
<li><b><a href="https://dineshonjava.com/listiterator-interface-in-collection/">ListIterator interface</a></b></li>
<li><b><a href="https://dineshonjava.com/hashset-class-in-collection/">HashSet class</a></b></li>
<li><b><a href="https://dineshonjava.com/linkedhashset-class-in-collection/">LinkedHashSet class</a></b></li>
<li><b><a href="https://dineshonjava.com/treeset-classin-collection/">TreeSet class</a></b></li>
<li><b><a href="https://dineshonjava.com/difference-between-hashset-and-treeset/">Difference between TreeSet &; HashSet</a></b></li>
<li><b><a href="https://dineshonjava.com/map-interface-in-collection/">Map interface</a></b></li>
<li><b><a href="https://dineshonjava.com/hashmap-class-in-collection-framework/">HashMap class</a></b></li>
<li><b><a href="https://dineshonjava.com/difference-between-treemap-vs-hashmap/">Difference between TreeMap vs HashMap</a></b></li>
<li><b><a href="https://dineshonjava.com/linkedhashmap-class-in-collection/">LinkedHashMap class</a></b></li>
<li><b><a href="https://dineshonjava.com/treemap-class-in-collection-framework/">TreeMap class</a></b></li>
<li><b><a href="https://dineshonjava.com/hashtable-class-in-collection-framework/">Hashtable class</a></b></li>
<li><b><a href="https://dineshonjava.com/difference-between-hashmap-and/">Difference between HashMap and HashTable in Java</a></b></li>
<li><b><a href="https://dineshonjava.com/sorting-in-collection-framework/">Sorting</a></b></li>
<li><b><a href="https://dineshonjava.com/java-comparable-and-comparator/">Comparable interface</a></b></li>
</ol>
</div>
<div style="background-color: pink; border-width: thin; text-align: center;"><b><;<;<a href="https://dineshonjava.com/hashmap-class-in-collection-framework/">Previous</a> <;<; ; ; || <a href="https://dineshonjava.com/core-java-baby-step-to-be-best-java-ian/">Index </a>||  ; >;>;<a href="https://dineshonjava.com/linkedhashmap-class-in-collection/">Next</a> >;>;</b></div>
<p>
</div>
<div class="wp-post-navigation"> 
									 <div class="wp-post-navigation-pre"> 
									 <a href="https://dineshonjava.com/hashmap-class-in-collection-framework/">Previous</a> 
									 </div> 
									 <div class="wp-post-navigation-next"> 
									 <a href="https://dineshonjava.com/linkedhashmap-class-in-collection/">Next</a> 
									 </div> 
									</div>
<script type="text/javascript">
jQuery(document).ready(function($) {
 $.post('https://dineshonjava.com/wp-admin/admin-ajax.php', {action: 'mts_view_count', id: '413'});
});
</script>
Strategy Design Patterns We can easily create a strategy design pattern using lambda. To implement…
Decorator Pattern A decorator pattern allows a user to add new functionality to an existing…
Delegating pattern In software engineering, the delegation pattern is an object-oriented design pattern that allows…
Technology has emerged a lot in the last decade, and now we have artificial intelligence;…
Managing a database is becoming increasingly complex now due to the vast amount of data…
Overview In this article, we will explore Spring Scheduler how we could use it by…