HashMap Implementation

The JAVA HashMap class implements Map<K, V> Interface and uses a nested inner Entry<K, V> for storing the key, value pair.

Here is the code snippet of Entry<K, V> class

/**   * Here Entry class provide the flavor of Actual Map.Entry<K,V>   * @author Manoj   * @param <K>   * @param <V>   */  private static class Entry<K, V> implements Map.Entry<K, V> {   private int hash;   private K key;   private V value;   Entry<K, V> next;   public K getKey() {    // TODO Auto-generated method stub    return null;   }   public V getValue() {    // TODO Auto-generated method stub    return null;   }   public V setValue(V value) {    // TODO Auto-generated method stub    return null;   }  }

When we call the put method of HashMap, first it calculates the hashcode of the key to find the appropriate bucket. Default initial capacity of hashmap is 16

HashMap maintain an array of HashMap.Entry<K,V> of size 16.

For a particular key hasmap calculate the hashcode and put that key into the bucket of Entry<K,V> array.

Suppose hashcode value of a key is 9 than Entry will be made for that key at 8th index of HashMap.Entry<K,V> array. And there is one more entry at index location 5 as shown in below table.

0
1
2
3
4
5	HashMap$Entry<K,V>
6
7
8	HashMap$Entry<K,V>
9
10
11
12
13
14
15

Now we are going to put a third element but hashcode of third element is again 8, then hashmap will maintain a linkedlist in 8^th index. Refer below diagram

0
1
2
3
4
5	HashMap$Entry<K,V>	.next->	null
6
7
8	HashMap$Entry<K,V>	.next->	HashMap$Entry<K,V>	.next = null
9
10
11
12
13
14
15

Now when we try to get the value hashmap follow the same procedure first calculate the hashcode than search for that element into that bucket if multiple entries found than traverse the linked list and compare the value of the key with equals() method and then return the corresponding value for that key.