Hash Map

1.     String HashMap: works on hashing algorithm

·         Allows null key and values

·         Not ordered collection and iterate over hashmap based on key but keys not guaranteed in order of insert

·         Not synchronized

·         Stores entries in multiple singly linked lists called buckets. Default number of bins is 16 and it is always power of 2

·         Uses inner class Node<K,V> for storing map entries. Map.entry is used which  means each bucket is a combination of key and value.

·         Uses hashcode() and equal() methods on keys for get() and put() operations.

·         Not thread-safe but can get thread-safe using Collections.synchronizedMap method at the cost of performace

·         How hashmap works? 

·         Hashmap load factor: used to figure out when hash map will be rehashed and bucket size increased. By default, load factor=.75 and bucket/capapcity=16. Threshold=load factor* capacity=12. When there are more than 12 mapping bucket size increases to the next power of 2 i.e. 32. If we want to save space, we can increase load factor to .8/.9 but get and set operation will take more time

2.     How HashMap works: Elements are stored in singly linked list called buckets.

a.       Put(K,V): when we put the element. Hashcode() of key is used to identify if already a key with same hashcode exists.

If it does (collision), equals() method is used on key to check if it is same. If equals() method return true then the value is overwritten else a new node(key+value) is added to the singly linked list.

If hashcode() for the key does not exist, then the value is inserted in hashmap.

It returns the previous value associated with that key and if no value associated then null.

System.out.println(hashMap.put("E", "Egg0")); -- null

hashMap.put("E", "Egg1");

System.out.println(hashMap.put("E", "Egg")); -- Egg1 System.out.println(hashMap.get("E")); -- Egg

b.      get(K): hashcode() is used to identify the bucket. If only 1 value exists it is returned. Else, it iterates over linked list of that bucket to check for equals()  method. If it finds something with equals() method as true it returns that value(from key value pair stored) else returns null

3.     Collision in hashmap: when 2 keys return same hashcode() i.e. same bucket location, this is termed as collision. It can be resolved by equals() method on key. Using final and immutable with proper equals() and hashcode() method implementation helps in better performance by reducing collision. Immutability also allows caching their hashcode of different keys which makes overall retrieval process very fast and suggest that String and various wrapper classes e.g. Integer very good keys in Java HashMap

4.     If size of threshold defined by load factor: load factor is by default .75 which means once 75% of buckets in hashmap are full, it is re-sized i.e. a new bucket array of twice the size is created and then starts putting the old elements in new bucket array. This is known as rehashing

5.     Race-condition: in multi-threaded environment, if 2 threads try to resize hash map at the same time. This can result in an infinite loop.

6.     Handling null: Hashmap allows both null key and value and key-value pair. Null keys are always mapped to index 0 and hashcode() and equals() method are not used in null keys case

7.     Popular methods:

 HashMap<String,String> hashMap= new HashMap<>();

hashMap.clear();

hashMap.put("A", "Apple");

hashMap.put("D", "Dog");

hashMap.put("C", "Cat");

hashMap.put("E", "Egg1");

hashMap.put("B","Boy");

System.out.println(hashMap.size()); -- 5

System.out.println(hashMap.remove("C")); --Cat *uses hash code of key*

System.out.println(hashMap.remove("F")); -- null

*remove(key,value)uses hash code of key and equals on key to compare value*

System.out.println(hashMap.remove("B", "Ball")); -- false

System.out.println(hashMap.remove("B", "Boy")); -- true

System.out.println(hashMap.replace("A", "An"));--Apple*uses hash code of key*

System.out.println(hashMap.replace("Z", "An")); -- null

*replace(key,oldvalue,newvalue)uses hash code of key and equals on key to compare oldvalue and if found then put new value*

System.out.println(hashMap.replace("A", "An","AS")); -- true

System.out.println(hashMap.replace("A", "An","AS")); -- false

System.out.println(hashMap.containsKey("A")); -- true

System.out.println(hashMap.containsValue("A")); -- false

System.out.println(hashMap); -- {A=AS, D=Dog, E=Egg1}

System.out.println(hashMap.size()); -- 3

8.     Do not have iterator by default. Iterated using keySet or EntrySet

         Set entrySet1=hashMap.entrySet();

         Iterator iterator1=entrySet1.iterator();

         while(iterator1.hasNext()){

            System.out.println(iterator1.next());

            }

          Iterator iterator2=hashMap.keySet().iterator();

         while(iterator2.hasNext()){

            System.out.println(iterator2.next()); -- first key

            String key=iterator2.next().toString();- 2nd key

            System.out.println("Key: "+key+" Value: "+ hashMap.get(key));

            }

            A=AS

D=Dog

E=Egg1

A    

Key: D Value: Dog

E

Exception in thread "main"

3.     Remove method of iterator v/s remove of collection: While iterating over collection, if we use remove() of collection error will be thrown. For such scenarios remove() of iterator should be used.

       Set entrySet1=hashMap.entrySet();

       Iterator iterator1=entrySet1.iterator();

       while(iterator1.hasNext()){

            hashMap.remove("A"); 

            }

       

       Exception in thread "main" java.util.ConcurrentModificationException

.