Deep Dive into the Maps in collections Frame work of JAVA
Generally Maps are divided into two categories .
- Non Thread safe Maps(non — synchronized)
- Thread safe maps (synchronized)
1. Non Thread Safe Vs Thread Safe
Before we split in to the maps into these two categories, first we try to understand what is non thread safe and what is thread safe
1.Maps which can throw a Concurrent Exception, those maps are known as non-thread safe
2. Maps which cannot throw a Concurrent modification exception, those maps are known as Thread safe
When will the Concurrent modification exception is thrown ?
1.When we are performing an operation on the object and we trying to modify the same object simultaneously at the same time then we will get a concurrent Modification exception.
2. Concurrent Modification will be thrown on not only with multiple threads but also with single thread.
Concurrent Modification Exception on Single Thread
From the above program we can clearly understand that we are iterating the map object and we are modifying the same map object (put operation) simultaneously with main thread so we will get the below output
Concurrent Modification Exception on Multiple Threads
From the above program we can clearly understand that In some iterations, Thread-1 iterating the map object and Thread-2 modifying the same map object(put operation) simultaneously so we will get the below output
2. Non Thread Safe and Thread Safe Map categories
PART -1 : 3. NON THREAD SAFE MAPS
(Thread safe maps will be covered in further posts)
3.1 Hash Map
1. Hierarchy
2. Behavior of Hash Map on different categories
3. Internal implementation of Hash Map :
3.2 Linked HashMap
1. Hierarchy
2. Behavior of Linked Hash Map on different categories
3. Features of Linked Hash Map
(1) It takes more memory as compared to the hash Map because it uses the DoubleLinkedList
(2) Default ordering provided by LinkedHashMap is the order on which key is inserted, known as insertion order, but LinkedHashMap can be created with another ordering called access order, which is defined by accessing entries.
(3) Iterator of LinkedHashMap returns elements in the order e.g. either insertion order or access order.
(4) Re-entering a mapping, doesn’t alter insertion order of LinkedHashMap. For example, if you already have a mapping for a key, and want to update it’s value by calling put(key, newValue), insertion order of LinkedHashMap will remain the same.
(5) Access order is affected by calling get(key), put(key, value) or putAll(). When a particular entry is accessed, it moves towards the end of the doubly linked list, maintained by LinkedHashMap.
(6) LinkedHashMap also provides a method called removeEldestEntry(), which is protected and default implementation returns false. If overridden, an implementation can return true to remove oldest entry, when a new entry is added.
4. Usage
LinkedHashMap can be used to create LRU cache in Java. Since in LRU or Least Recently Used Cache, oldest non accessed entry is removed, which is the head of the doubly linked list maintained by LinkedHashMap.
5. Observations
From the above output we clearly understand that LinkedHashMap maintains insertion order
3.3 Identity HashMap
1. Hierarchy
2. Behavior of Identity Hash Map on different categories
3. Features of Identity Hash Map
(1) The main difference between HashMap vs IdentityHashMap is that IdentityHashMap uses equality operator “==” for comparing keys and values inside Map while HashMap uses equals() for comparing keys and values.
(2) Unlike HashMap, who uses hashcode to find bucket location, IdentityHashMap doesn’t use hashCode() instead it uses System.identityHashCode(object).
(3) Another key difference between IdentityHashMap and HashMap in Java is Speed. Since IdentityHashMap doesn’t use equals() its comparatively faster than HashMap for object with expensive equals() and hashCode()
(4) One more difference between HashMap and IdentityHashMap is Immutability of the key. One of the basic requirement to safely store Objects in HashMap is keys needs to be immutable, IdentityHashMap doesn’t require keys to be immutable as it is not relied on equals and hashCode.
4. Usage
- Used for deep copying
- Memory footprint is generally smaller than HashMap
5. Observations
Here from the above program we clearly notice the difference the outputs of HashMap and the Identical HashMap. We can clearly understand that IdenticalHashMap uses == operator instead equals() method. I hope you will clearly know the difference between the == operator and equals() method
3.4 Enum Map
1. Hierarchy
2. Behavior of Enum Map on different categories
3. Features of Enum Map
(1) A specialized Map implementation for use with enum type keys.
(2) All of the keys in an Enum map must come from a single enum type that is specified, explicitly or implicitly, when the map is created.
(3) Enum maps are represented internally as arrays. This representation is extremely compact and efficient.
(4) Iterator does not fail fast
Let’s understand the Iterator does not fail fast behavior with below example
From the above Example we can clearly understand the even though the Enum Map is not a thread safe it does not gives a Concurrent Modification Exception because Iterators returned by the collection views (keySet(), entrySet(), and values()) are weakly consistent: they will never throw Concurrent Modification Exception and they may or may not show the effects of any modifications to the map that occur while the iteration is in progress.
4. Observations
3.5 Weak HashMap
1. Hierarchy
2. Behavior of Weak HashMap on different categories
3. Features of Weak HashMap
- Each key object in the WeakHashMap is stored indirectly as the referent of a Weak reference(also called hard ) reference.
- The garbage collector may discard keys at anytime, WeakHashMap may behave as an unknown thread that is silently removing entries. So it is possible for the size method to return smaller values over time.So, in WeakHashMap size decrease happens automatically.
- WeakHashMap does not implement Cloneable interface , it only implements Map interface. Hence , there is no clone() method in the WeakHashMap class.
- WeakHashMap does not implement Serializable interface . As a result , WeakHashMap object will not have any of their state serialized or deserialized.(i.e state of the WeakHashMap object cannot be saved and again resume from the saved state).
4. Usage
It is used to store the weak references as keys as a cache
5. Observations
From the above example we can clearly understand the after initiating the GC, weak references are deleted. Difference between the strong references and weak references was discussed in further posts
3.6 Tree Map
1. Hierarchy
2. Behavior of Tree Map on different categories
3. Features of Tree Map
- Navigable map provides the approximate lookups , we need to see the nearest keys
- Iteration is in natural order of Sorting is the main benefit
- finding lower and higher keys
- Map can be split into Sub maps
- Any Custom Object must and should implement Comparator Interface if you given as a key
- Performance is low as compared to the hashmap and the linked hashmap
Custom Objects Sorting and Generic TreeMap Implementation with comparator interface and internal working of Tree map will be discussed in further posts
4. Observations
4. Complexities and Performance of Non Thread Safe Maps
Complexities
Performance Test
- I conducted the performance test between the maps
- I took Thread Pool of 5 threads and each thread can do 5,00,000 put and get operations. I made like this 5 times and Each time I calculated the execution time for each thread pool and finally I calculated the average time
Result
