Java Code Showing Internal Working of Hashmap

Hash map works on the principle of Hashing ,
Hashing is a technique which convert keys into some integer value known as Hash code .
Default size of hashmap is 16.
This Hashcode is used to store values into Hashmap.
Internally Hashmap uses Table which has array of nodes.
Each Block of table known as bucket.
Each bucket uses LinkedList to store elements and LinkedList store elements in the form node i.e key,hashcode,value and next node address

Example : 

HashMap<String,Integer> map = new HashMap<String, Integer >();

map.put(“ram”,100);

map.put(“shyam”,101);

map.put(“mohan”,102);

How put operation works in Hashmap.

Step 1 > First put operation calculate Hashcode of key . For Example here we calculate Hashcode of key ram  suppose Hashcode of key ram is 1475236 , we cannot create array of this size so we calculate index position from Hashcode (1475236) ,to calculate index position Hashmap divide the Hashcode by Map default size i.e 16 and use remainder (4)as a index to store key in table.

Step 2 > Now we calculate Hashcode of key shyam i.e 64205538 and index is 2 ,hashmap store this key at index 2.

Step 3 > Now we calculate Hashcode of key mohan i.e 4452852 and index is 4 ,hashmap store this key at index 4 .If any element is already available at particular index then bucket internally uses LinkedList to store element .This process continue for all the keys in Hashmap.

How get operation works in Hashmap.

map.get(“ram”);

map.get(“shyam”);

map.get(“mohan”);

Get also do the same operation as Put do , get operation also first calculate Hash code of key suppose Hash code of key ram is 1475236 and then it calculate the index from Hash code i.e.  4

And Now it look up at index 4 and matches the hash code , if Hash code matches then it match the key using equals() method and if key matches then it return the value . This operation continue till it get values of all keys.

public class HashmapInternalWorking {

public static void test() {
   int size = 16; // slot size
   Integer[] keys = { 1, 10, 16, 100, 1000, 10000, 2000000, 100000000 };
   HashMap<Integer, Object> map = new HashMap<Integer, Object>();

   for (Integer key : keys) {
       int hash = hash(key.hashCode());
       int i = indexFor(hash, size);

       map.put(key, "[" + hash + " : " + i + "]");
   }

   for (Integer key : map.keySet()) {
       System.out.printf("key: %9s, [inner hash : slot index]: %s,\n", key, map.get(key));
   }
}

static int hash(int h) {
   h ^= (h >>> 20) ^ (h >>> 12);
   return h ^ (h >>> 7) ^ (h >>> 4);
}

static int indexFor(int h, int length) {
   return h & (length - 1);
}
public static void main(String[] args) {
test();
}

}