How HashMap works in java 2

Myth丶恋晨 2021-12-17 14:19 179阅读 0赞

#  #

https://www.javacodegeeks.com/2014/03/how-hashmap-works-in-java.html

Most common interview questions are “How HashMap works in java”, “How get and put method of HashMap work internally”. Here I am trying to explain internal functionality with an easy example. Rather than going through theory, we will start with example first, so that you will get better understanding and then we will see how get and put function work in java.  
Lets take a very simple example. I have a Country class, we are going to use Country class object as key and its capital name(string) as value. Below example will help you to understand, how these key value pair will be stored in hashmap.

## 1. Country.java ##

<table> 
 <tbody> 
  <tr> 
   <td><code>01</code></td> 
   <td><code>package</code>&nbsp;<code>org.arpit.javapostsforlearning;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>02</code></td> 
   <td><code>public</code>&nbsp;<code>class</code>&nbsp;<code>Country { </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>04</code></td> 
   <td><code>&nbsp;</code><code>String name;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>05</code></td> 
   <td><code>&nbsp;</code><code>long</code>&nbsp;<code>population;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>07</code></td> 
   <td><code>&nbsp;</code><code>public</code>&nbsp;<code>Country(String name,&nbsp;</code><code>long</code>&nbsp;<code>population) { </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>08</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>super</code><code>();</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>10</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>this</code><code>.population = population;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>12</code></td> 
   <td><code>&nbsp;</code><code>public</code>&nbsp;<code>String getName() { </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>13</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>name;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>15</code></td> 
   <td><code>&nbsp;</code><code>public</code>&nbsp;<code>void</code>&nbsp;<code>setName(String name) { </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>18</code></td> 
   <td><code>&nbsp;</code><code>public</code>&nbsp;<code>long</code>&nbsp;<code>getPopulation() { </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>19</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>population;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>21</code></td> 
   <td><code>&nbsp;</code><code>public</code>&nbsp;<code>void</code>&nbsp;<code>setPopulation(</code><code>long</code>&nbsp;<code>population) { </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>22</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>this</code><code>.population = population;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>25</code></td> 
   <td><code>&nbsp;</code><code>// If length of name in country object is even then return 31(any random number) and if odd then return 95(any random number).</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>26</code></td> 
   <td><code>&nbsp;</code><code>// This is not a good practice to generate hashcode as below method but I am doing so to give better and easy understanding of hashmap.</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>27</code></td> 
   <td><code>&nbsp;</code><code>@Override</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>28</code></td> 
   <td><code>&nbsp;</code><code>public</code>&nbsp;<code>int</code>&nbsp;<code>hashCode() { </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>29</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>if</code><code>(</code><code>this</code><code>.name.length()%</code><code>2</code><code>==</code><code>0</code><code>)</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>30</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>31</code><code>;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>32</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>95</code><code>;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>34</code></td> 
   <td><code>&nbsp;</code><code>@Override</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>35</code></td> 
   <td><code>&nbsp;</code><code>public</code>&nbsp;<code>boolean</code>&nbsp;<code>equals(Object obj) { </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>37</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>Country other = (Country) obj;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>38</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;</code><code>if</code>&nbsp;<code>(name.equalsIgnoreCase((other.name)))</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>39</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>true</code><code>;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>40</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>false</code><code>;</code></td> 
  </tr> 
 </tbody> 
</table>

If you want to understand more about hashcode and equals method of object, you may refer **[hashcode() and equals() method in java][hashcode_ and equals_ method in java]**

## 2. HashMapStructure.java(main class) ##

<table> 
 <tbody> 
  <tr> 
   <td><code>01</code></td> 
   <td><code>import</code>&nbsp;<code>java.util.HashMap;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>02</code></td> 
   <td><code>import</code>&nbsp;<code>java.util.Iterator;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>04</code></td> 
   <td><code>public</code>&nbsp;<code>class</code>&nbsp;<code>HashMapStructure { </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>07</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* @author Arpit Mandliya</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>09</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>static</code>&nbsp;<code>void</code>&nbsp;<code>main(String[] args) { </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>11</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Country india=</code><code>new</code>&nbsp;<code>Country(</code><code>"India"</code><code>,</code><code>1000</code><code>);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>12</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Country japan=</code><code>new</code>&nbsp;<code>Country(</code><code>"Japan"</code><code>,</code><code>10000</code><code>);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>14</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Country france=</code><code>new</code>&nbsp;<code>Country(</code><code>"France"</code><code>,</code><code>2000</code><code>);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>15</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Country russia=</code><code>new</code>&nbsp;<code>Country(</code><code>"Russia"</code><code>,</code><code>20000</code><code>);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>17</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>HashMap&lt;country,string&gt; countryCapitalMap=</code><code>new</code>&nbsp;<code>HashMap&lt;country,string&gt;();</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>18</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>countryCapitalMap.put(india,</code><code>"Delhi"</code><code>);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>19</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>countryCapitalMap.put(japan,</code><code>"Tokyo"</code><code>);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>20</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>countryCapitalMap.put(france,</code><code>"Paris"</code><code>);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>21</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>countryCapitalMap.put(russia,</code><code>"Moscow"</code><code>);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>23</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Iterator&lt;country&gt; countryCapitalIter=countryCapitalMap.keySet().iterator();</code><code>//put debug point at this line</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>24</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code><code>(countryCapitalIter.hasNext())</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>26</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Country countryObj=countryCapitalIter.next();</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>27</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>String capital=countryCapitalMap.get(countryObj);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>28</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(countryObj.getName()+</code><code>"----"</code><code>+capital);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>34</code></td> 
   <td><code>&lt;/country&gt;&lt;/country,string&gt;&lt;/country,string&gt;</code></td> 
  </tr> 
 </tbody> 
</table>

Now put debug point at line 23 and right click on project->debug as-> java application. Program will stop execution at line 23 then right click on countryCapitalMap then select watch.You will be able to see structure as below.  
  
[![HashMapStructure1][]][HashMapStructure1 1]  
Now From above diagram, you can observe following points

1.  1.  There is an Entry\[\] array called table which has size 16.
    2.  This table stores Entry class’s object. HashMap class has a inner class called Entry.This Entry have key value as instance variable. Lets see structure of entry class Entry Structure.

<table> 
 <tbody> 
  <tr> 
   <td><code>1</code></td> 
   <td><code>static</code>&nbsp;<code>class</code>&nbsp;<code>Entry&nbsp;</code><code>implements</code>&nbsp;<code>Map.Entry</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>3</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>final</code>&nbsp;<code>K key;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>4</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>V value;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>5</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Entry next;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>6</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>final</code>&nbsp;<code>int</code>&nbsp;<code>hash;</code></td> 
  </tr> 
 </tbody> 
</table>

1.  Whenever we try to put any key value pair in hashmap, Entry class object is instantiated for key value and that object will be stored in above mentioned Entry\[\](table). Now you must be wondering, where will above created Enrty object get stored(exact position in table). The answer is, hash code is calculated for a key by calling Hascode() method. This hashcode is used to calculate index for above Entry\[\] table.
2.  Now, If you see at array index 10 in above diagram, It has an Entry object named HashMap$Entry.
3.  We have put 4 key-values in hashmap but it seems to have only 2!!!!This is because if two objects have same hashcode, they will be stored at same index. Now question arises how? It stores objects in a form of LinkedList(logically).

So how hashcode of above country key-value pairs are calculated.

<table> 
 <tbody> 
  <tr> 
   <td><code>1</code></td> 
   <td><code>Hashcode&nbsp;</code><code>for</code>&nbsp;<code>Japan =&nbsp;</code><code>95</code>&nbsp;<code>as its length is odd.</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>2</code></td> 
   <td><code>Hashcode&nbsp;</code><code>for</code>&nbsp;<code>India =</code><code>95</code>&nbsp;<code>as its length is odd</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>3</code></td> 
   <td><code>HashCode&nbsp;</code><code>for</code>&nbsp;<code>Russia=</code><code>31</code>&nbsp;<code>as its length is even.</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>4</code></td> 
   <td><code>HashCode&nbsp;</code><code>for</code>&nbsp;<code>France=</code><code>31</code>&nbsp;<code>as its length is even.</code></td> 
  </tr> 
 </tbody> 
</table>

Below diagram will explain LinkedList concept clearly.  
  
[![HashMapStructure2][]][HashMapStructure2 1]  
So now if you have good understanding of hashmap structure,Lets go through put and get method.

## Put : ##

Lets see implementation of put method:

<table> 
 <tbody> 
  <tr> 
   <td><code>02</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>* Associates the specified value with the specified key in this map. If the</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>03</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>* map previously contained a mapping for the key, the old value is</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>04</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>* replaced.</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>06</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>* @param key</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>07</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; key with which the specified value is to be associated</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>08</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>* @param value</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>09</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; value to be associated with the specified key</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>10</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>* @return the previous value associated with &lt;tt&gt;key&lt;/tt&gt;, or &lt;tt&gt;null&lt;/tt&gt;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>11</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if there was no mapping for &lt;tt&gt;key&lt;/tt&gt;. (A &lt;tt&gt;null&lt;/tt&gt; return</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>12</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; can also indicate that the map previously associated</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>15</code></td> 
   <td><code>&nbsp;</code><code>public</code>&nbsp;<code>V put(K key, V value) { </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>17</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>putForNullKey(value);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>18</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>int</code>&nbsp;<code>hash = hash(key.hashCode());</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>19</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>int</code>&nbsp;<code>i = indexFor(hash, table.length);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>20</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>for</code>&nbsp;<code>(Entry&lt;k , V&gt; e = table[i]; e !=&nbsp;</code><code>null</code><code>; e = e.next) { </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>21</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;</code><code>Object k;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>22</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;</code><code>if</code>&nbsp;<code>(e.hash == hash &amp;&amp; ((k = e.key) == key || key.equals(k))) { </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>23</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>V oldValue = e.value;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>24</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>e.value = value;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>25</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>e.recordAccess(</code><code>this</code><code>);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>26</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>oldValue;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>30</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>modCount++;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>31</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>addEntry(hash, key, value, i);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>32</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>null</code><code>;</code></td> 
  </tr> 
 </tbody> 
</table>

now lets understand above code step by step

1.  Key object is checked for null. If key is null then it will be stored at table\[0\] because hashcode for null is always 0.
2.  Key object’s hashcode() method is called and hash code is calculated. This hashcode is used to find index of array for storing Entry object. It may happen sometimes that, this hashcode function is poorly written so JDK designer has put another function called hash() which takes above calculated hash value as argument.If you want to learn more about hash() function, you can refer [hash and indexFor method in hashmap][].
3.  indexFor(hash,table.length) is used to calculate exact index in table array for storing the Entry object.
4.  As we have seen in our example, if two key objects have same hashcode(which is known as **collision**) then it will be stored in form of linkedlist.So here, we will iterate through our linkedlist.

*  If there is no element present at that index which we have just calculated then it will directly put our Entry object at that index.
 *  If There is element present at that index then it will iterate until it gets Entry->next as null.Then current Entry object become next node in that linkedlist
 *  What if we are putting same key again, logically it should replace old value. Yes,it will do that.While iterating it will check key equality by calling equals() method(**key.equals(k)**), if this method returns true then it replaces value object with current Entry’s value object.

## Get: ##

Lets see implementation of get now:

<table> 
 <tbody> 
  <tr> 
   <td><code>02</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>* Returns the value to which the specified key is mapped, or {@code null}</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>03</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>* if this map contains no mapping for the key.</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>06</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>* More formally, if this map contains a mapping from a key {@code k} to a</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>07</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>* value {@code v} such that {@code (key==null ? k==null :</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>08</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>* key.equals(k))}, then this method returns {@code v}; otherwise it returns</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>09</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>* {@code null}. (There can be at most one such mapping.)</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>12</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>* A return value of {@code null} does not &lt;i&gt;necessarily&lt;/i&gt; indicate that</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>13</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>* the map contains no mapping for the key; it's also possible that the map</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>14</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>* explicitly maps the key to {@code null}. The {@link #containsKey</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>15</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>* containsKey} operation may be used to distinguish these two cases.</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>17</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>* @see #put(Object, Object)</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>19</code></td> 
   <td><code>&nbsp;</code><code>public</code>&nbsp;<code>V get(Object key) { </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>21</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>getForNullKey();</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>22</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>int</code>&nbsp;<code>hash = hash(key.hashCode());</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>23</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>for</code>&nbsp;<code>(Entry&lt;k , V&gt; e = table[indexFor(hash, table.length)]; e !=&nbsp;</code><code>null</code><code>; e = e.next) { </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>24</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;</code><code>Object k;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>25</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;</code><code>if</code>&nbsp;<code>(e.hash == hash &amp;&amp; ((k = e.key) == key || key.equals(k)))</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>26</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>e.value;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>28</code></td> 
   <td><code>&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>null</code><code>;</code></td> 
  </tr> 
 </tbody> 
</table>

As you got the understanding on put functionality of hashmap. So to understand get functionality is quite simple. If you pass any key to get value object from hashmap.

1.  Key object is checked for null. If key is null then value of Object resides at table\[0\] will be returned.
2.  Key object’s hashcode() method is called and hash code is calculated.
3.  indexFor(hash,table.length) is used to calculate exact index in table array using generated hashcode for getting the Entry object.
4.  After getting index in table array, it will iterate through linkedlist and check for key equality by calling equals() method and if it returns true then it returns the value of Entry object else returns null.

## Key points to Remeber: ##

*  HashMap has a inner class called Entry which stores key-value pairs.
 *  Above Entry object is stored in Entry\[ \](Array) called table
 *  An index of table is logically known as bucket and it stores first element of linkedlist
 *  Key object’s hashcode() is used to find bucket of that Entry object.
 *  If two key object ‘s have same hashcode , they will go in same bucket of table array.
 *  Key object ‘s equals() method is used to ensure uniqueness of key object.
 *  Value object ‘s equals() and hashcode() method is not used at all

转载于:https://www.cnblogs.com/kungfupanda/p/6736812.html

[hashcode_ and equals_ method in java]: http://javapostsforlearning.blogspot.in/2014/02/hashcode-and-equals-method-in-java.html
[HashMapStructure1]: https://www.javacodegeeks.com/wp-content/uploads/2014/03/HashMapStructure1.jpg
[HashMapStructure1 1]: http://www.javacodegeeks.com/wp-content/uploads/2014/03/HashMapStructure1.jpg
[HashMapStructure2]: https://www.javacodegeeks.com/wp-content/uploads/2014/03/HashMapStructure2.jpg
[HashMapStructure2 1]: http://www.javacodegeeks.com/wp-content/uploads/2014/03/HashMapStructure2.jpg
[hash and indexFor method in hashmap]: http://javapostsforlearning.blogspot.in/2014/02/hash-and-indexfor-method-in-hashmap.html