HashSet
HashSet uses HashMap internally to store it’s objects. Whenever you create a HashSet object, one HashMap object associated with it is also created. This HashMap object is used to store the elements you enter in the HashSet. The elements you add into HashSet are stored as keys of this HashMap object. The value associated with those keys will be a constant.
HashMap
HashMap works on the principle of hashing, we have put() and get() method for storing and retrieving object from HashMap.When we pass both key and value to put() method to store on HashMap, it uses key object hashcode() method to calculate hashcode and them by applying hashing on that hashcode it identifies bucket location for storing value object. While retrieving it uses key object equals method to find out correct key value pair and return value object associated with that key. HashMap uses linked list in case of collision and object will be stored in next node of linked list.
Important point to mention is that HashMap in Java stores both key and value object as Map.Entry in a bucket which is essential to understand the retrieving logic.
What will happen if two different objects have the same hashcode?
Now from here onwards real confusion starts, sometime candidate will say that since hashcode is equal, both objects are equal and HashMap will throw exception or not store them again etc, Then you might want to remind them about equals() and hashCode() contract that two unequal objects in Java can have same hashcode. Some will give up at this point and few will move ahead and say "Since hashcode is same, bucket location would be same and collision will occur in HashMap Since HashMap uses LinkedList to store object, this entry (object of Map.Entry comprise key and value ) will be stored in LinkedList
Now from here onwards real confusion starts, sometime candidate will say that since hashcode is equal, both objects are equal and HashMap will throw exception or not store them again etc, Then you might want to remind them about equals() and hashCode() contract that two unequal objects in Java can have same hashcode. Some will give up at this point and few will move ahead and say "Since hashcode is same, bucket location would be same and collision will occur in HashMap Since HashMap uses LinkedList to store object, this entry (object of Map.Entry comprise key and value ) will be stored in LinkedList
HashMap Changes in JDK 1.7 and JDK 1.8
There is some performance improvement done on HashMap and ArrayList from JDK 1.7, which reduce memory consumption. Due to this empty Map are lazily initialized and will cost you less memory. Earlier, when you create HashMap e.g. new HashMap() it automatically creates an array of default length e.g. 16. After some research, Java team found that most of this Map are temporary and never use that many elements, and only end up wasting memory. Also, From JDK 1.8 onwards HashMap has introduced an improved strategy to deal with high collision rate. Since a poor hash function e.g. which always return location of same bucket, can turn a HashMap into linked list, i.e. converting get() method to perform in O(n) instead of O(1) and someone can take advantage of this fact, Java now internally replace linked list to a binary true once certain threshold is breached. This ensures performance or order O(log(n)) even in the worst case where a hash function is not distributing keys properly.
Some other Concepts
- The concept of hashing
- Collision resolution in HashMap
- Use of equals () and hashCode () and their importance in HashMap?
- The benefit of the immutable object?
- Race condition on HashMap in Java
- Resizing of Java HashMap
- Immutable key object
- Load factor and balancing
ConcurrentHashMap
ConcurrentHashMap performs better than earlier two because it only locks a portion of Map, instead of whole Map, which is the case with Hashtable and synchronized Map. CHM allows concurred read operations and the same time maintains integrity by synchronizing write operations.
ConcurrentHashMap is introduced as an alternative of Hashtable and provided all functions supported by Hashtable with an additional feature called "concurrency level", which allows ConcurrentHashMap to partition Map. ConcurrentHashMap allows multiple readers to read concurrently without any blocking. This is achieved by partitioning Map into different parts based on concurrency level and locking only a portion of Map during updates. Default concurrency level is 16, and accordingly Map is divided into 16 part and each part is governed with a different lock. This means, 16 thread can operate on Map simultaneously until they are operating on different part of Map. This makes ConcurrentHashMap high performance despite keeping thread-safety intact. Though, it comes with a caveat. Since update operations like put(), remove(), putAll() or clear() is not synchronized, concurrent retrieval may not reflect most recent change on Map.
Concurrency-Level: Defines the number which is an estimated number of concurrently updating threads. The implementation performs internal sizing to try to accommodate this many threads.
Load-Factor: It's a threshold, used to control resizing.
Initial Capacity: The implementation performs internal sizing to accommodate these many elements.
When to use ConcurrentHashMap in Java
ConcurrentHashMap is best suited when you have multiple readers and few writers. If writers outnumber reader, or writer is equal to reader, than performance of ConcurrentHashMap effectively reduces to synchronized map orHashtable. Performance of CHM drops, because you got to lock all portion of Map, and effectively each reader will wait for another writer, operating on that portion of Map. ConcurrentHashMap is a good choice for caches, which can be initialized during application start up and later accessed my many request processing threads. As javadoc states, CHM is alsoa good replacement of Hashtable and should be used whenever possible, keeping in mind, that CHM provides slightly weeker form of synchronization than Hashtable.
Example to understand differnce between ConcurrentHashMap and HashMap
package com.journaldev.util; import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.concurrent.ConcurrentHashMap; public class ConcurrentHashMapExample { public static void main(String[] args) { //ConcurrentHashMap Map<String,String> myMap = new ConcurrentHashMap<String,String>(); myMap.put("1", "1"); myMap.put("2", "1"); myMap.put("3", "1"); myMap.put("4", "1"); myMap.put("5", "1"); myMap.put("6", "1"); System.out.println("ConcurrentHashMap before iterator: "+myMap); Iterator<String> it = myMap.keySet().iterator(); while(it.hasNext()){ String key = it.next(); if(key.equals("3")) myMap.put(key+"new", "new3"); } System.out.println("ConcurrentHashMap after iterator: "+myMap); //HashMap myMap = new HashMap<String,String>(); myMap.put("1", "1"); myMap.put("2", "1"); myMap.put("3", "1"); myMap.put("4", "1"); myMap.put("5", "1"); myMap.put("6", "1"); System.out.println("HashMap before iterator: "+myMap); Iterator<String> it1 = myMap.keySet().iterator(); while(it1.hasNext()){ String key = it1.next(); if(key.equals("3")) myMap.put(key+"new", "new3"); } System.out.println("HashMap after iterator: "+myMap); } }
When we try to run the above class, output is
ConcurrentHashMap before iterator: {1=1, 5=1, 6=1, 3=1, 4=1, 2=1} ConcurrentHashMap after iterator: {1=1, 3new=new3, 5=1, 6=1, 3=1, 4=1, 2=1} HashMap before iterator: {3=1, 2=1, 1=1, 6=1, 5=1, 4=1} Exception in thread "main" java.util.ConcurrentModificationException at java.util.HashMap$HashIterator.nextEntry(HashMap.java:793) at java.util.HashMap$KeyIterator.next(HashMap.java:828) at com.test.ConcurrentHashMapExample.main(ConcurrentHashMapExample.java:44)