The java.util.Map is i of the almost of import interfaces from Java Collection Framework. It provides hash tabular array information construction functionality past times its implementations similar HashMap, Hashtable, LinkedHashMap together with a lilliputian combat of sorting amongst the TreeMap. So if yous are looking to shop key-value pairs inward Java program, you convey a broad attain of choices available depending upon your requirement. The primary departure betwixt LinkedHashMap, TreeMap together with HashMap comes inward their internal implementation together with specific features, which makes them useful inward sure scenarios. For example, the HashMap is a full general purpose Map (hash tabular array information structure), which should hold upward used whenever yous require a hashing-based information construction for storing your mappings (key-value pairs).
TreeMap is a Red-Black tree based NavigableMap implementation provides yous sorting, on top of hashing offered past times Map interface. This agency yous tin non alone retrieve elements inward guaranteed log(n) fourth dimension (Algorithms are adaptations of those inward Cormen, Leiserson, together with Rivest's Introduction to Algorithms), but also iterate through those mapping inward a predefined sorted order, but yous require to pay a heavy cost to pop off on mappings inward sorted order.
On the other hand, LinkedHashMap is a compromise betwixt these two, it doesn't render sorting but dissimilar HashMap, it provides ordering e.g. maintaining mappings inward an firm they are inserted into Map, known every bit insertion order or firm on which they are accessed, called access order.
Apart from these 3 pop Map implementation, yous also convey simply about particular purpose Map implementations e.g. EnumMap for storing mapping amongst enum constants every bit keys, it is highly optimized for enum constants. You also convey a particular map called WeakHashMap for creating a Garbage Collector friendly Cache, where values larn eligible for garbage collection every bit shortly every bit in that place is no other reference to them apart from keys inward WeakHashMap.
Then in that place is IdentityHashMap for creating a Map which uses identity instead of equality for comparison keys since identity equality is rare, yous larn less number of collisions on this Map together with finally, JDK five introduced ConcurrentHashMap for improve scalability inward a multi-threaded environment, where the number of reader threads clearly outnumbers a number of author threads.
LinkedHashMap tin hold upward used to maintain insertion order, on which keys are inserted into Map or it tin also hold upward used to maintain an access order, on which keys are accessed. This provides LinkedHashMap an border over HashMap without compromising also much performance.
TreeMap provides yous consummate command over sorting elements past times passing custom Comparator of your choice, but amongst the expense of simply about performance. Since entries are stored inward a tree-based information structure, it provides lower performance than HashMap together with LinkedHashMap.
On the other hand, TreeMap, which sorts elements inward natural firm doesn't allow nothing keys because compareTo() method throws NullPointerException if compared amongst null. If yous are using TreeMap amongst user defined Comparator than it depends upon the implementation of compare() method.
By the way, it's worth remembering that apart from adding or removing to a greater extent than mappings, it tin also hold upward whatsoever functioning which affects iteration firm of LinkedHashMap. In access-ordered LinkedHashMap, fifty-fifty querying the Map amongst get() method is a structural modification, because it changes the iteration order, on the other mitt updating the value inward an insertion-ordered linked hash map is non a structural modification.
Finally, the fail-fast conduct is non guaranteed, together with they throw ConcurrentModificationException on the best-effort basis, which agency exercise non write code, which depends upon this behavior. It should alone hold upward used to uncovering programming bugs.
BTW, constant fourth dimension performance is alone provided if mappings are distributed uniformly across bucket location. In the existent world, yous ever convey collision together with HashMap handles collision past times using a linked listing to shop collided elements. This tin cut worst instance performance of HashMap upward to O(n).
To mitigate the higher upward performance issue, JDK 8 has introduced balanced tree instead of linked listing inward instance of frequent collision inward HashMap. It internally switches to balanced tree from linked listing if in that place are to a greater extent than than 8 entries inward i bucket. See how does HashMap handles collisions inward Java for to a greater extent than details.
Worth noting is that this conduct is alone applicable to HashMap, LinkedHashMap, together with ConcurrentHashMap, Hashtable is left behind to save its legacy iteration firm every bit many legacy Java application relies on that together with this changes that order. This is also a skilful representative of why yous should non rely on undocumented features of JDK e.g. iteration firm of HashMap because they tin alter inward future.
but HashMap is surely faster than Hashtable because it's non synchronized. Iteration over Map is conduct proportional to the "capacity" + "size" of HashMap, that's why it's of import to gear upward the initial capacity high plenty if iteration performance is important. You tin farther utilization initial capacity together with load factor to fine melody your HashMap performance, to avoid rehashing of HashMap.
TreeMap is so it's costlier than HashMap if the order is non concerned. Since TreeMap is based on tree information construction (based upon Red-Black tree), it provides the log(n) fourth dimension for the get(), put(), containsKey() together with remove() operation, Algorithms are based upon those given inward Cormen, Leiserson, together with Rivest's Introduction to Algorithms.
LinkedHashMap is a trade-off betwixt two, similar HashMap it also provides constant fourth dimension performance for add, contains together with remove, though it's slightly slower than HashMap, to maintain linked list. By the way, looping over Map inward the instance of LinkedHashMap is slightly faster than HashMap because the fourth dimension required is proportional to size only. So if yous require insertion firm or access order, consider using LinkedHashMap over TreeMap inward Java.
When using synchronized Map e.g. synchronized LinkedHashMap or SortedMap, yous must exercise at the fourth dimension or creating the map to forbid accidental non-synchronized access. You tin utilization the next idiom to create Synchronized Map inward Java:
Synchronized LinkedHashMap
Synchronized TreeMap
Remember to utilization Collections.synchronizedMap() for synchronizing HashMap, LinkedHashMap together with Collections.synchronizedSortedMap() method for synchronizing TreeMap. If yous are non comfortable therefore come across this guide on how to synchronize HashMap inward Java.
On the other hand, LinkedHashMap extends HashMap together with uses linked listing to render insertion firm guarantee. It uses doubly-linked listing running through all of its entries, which tin also hold upward used to maintain access-order. Remember, insertion firm is non affected if a telephone commutation is re-inserted into LinkedHashMap, but access firm is affected if LinkedHashMap is created to maintain access-order.
TreeMap is internally based upon Red-Black Tree together with NavigableMap, introduced inward JDK 6. The Red-Black tree is used to maintain the sorting firm imposed past times Comparable or Comparator, provided at the fourth dimension of creation. TreeMap provides guaranteed log(n) fourth dimension cost for the get, put, containsKey together with withdraw operations. Algorithms are adaptations of those inward Cormen, Leiserson, together with Rivest's Introduction to Algorithms.
TreeMap is your pop off to map implementation if yous desire to pop off on keys in a sorted order, either inward their natural firm defined past times Comparable interface or a custom firm imposed past times Comparator interface, though it's worth remembering that your compareTo() or compare() method must hold upward consistent amongst equals() method, because Map interface is defined inward damage of equals together with TreeMap uses compareTo for comparison keys. So if keys compare() or compareTo() implementation is non consistent, therefore it volition neglect to obey Map's full general contract.
HashMap is your full general purpose hashing based collection, whenever yous require to utilization a hash tabular array information construction inward Java to shop key-value pairs, the start selection goes to HashMap inward a unmarried threaded environment. If yous happened to utilization a Map inward a multi-threaded surroundings consider using Hashtable, synchronized HashMap or ConcurrentHashMap from Java Collection Framework.
Since LinkedHashMap solved the work of chaotic ordering provided past times Hashtable together with HashMap, without incurring the high cost associated amongst TreeMap, yous tin also utilization LinkedHashMap to create a re-create of a Map inward Java, every bit shown inward below example.
You tin come across that TreeMap has sorted mappings inward contrary order, because of contrary Comparator provided to it. Also, LinkedHashMap has created a re-create of TreeMap together with firm of entries are retained.
That's all on the difference betwixt LinkedHashMap, TreeMap, together with HashMap inward Java. Though all 3 are Map implementation, they convey a different purpose together with used accordingly. Use LinkedHashMap, if yous require to maintain insertion or access firm of mappings e.g. inward LRU Cache. Use TreeMap, if yous require to maintain mappings inward a sorted order, either inward their natural firm or a custom firm defined past times Comparator together with utilization HashMap for all your full general purpose hashing based collection requirement. HashMap allows yous to retrieve an object inward O(1) fourth dimension if yous know the key.
Further Learning
Java In-Depth: Become a Complete Java Engineer
answer)What is the departure betwixt HashMap together with ArrayList inward Java? (answer) What is the departure betwixt HashSet together with ArrayList inward Java? (answer) 5 differences betwixt HashMap together with Hashtable inward Java? (answer) What is the departure betwixt ArrayList together with LinkedList inward Java? (answer) How to utilization NavigableMap inward Java 6? [example] How to utilization BlockingQueue inward Java Program? [example]
TreeMap is a Red-Black tree based NavigableMap implementation provides yous sorting, on top of hashing offered past times Map interface. This agency yous tin non alone retrieve elements inward guaranteed log(n) fourth dimension (Algorithms are adaptations of those inward Cormen, Leiserson, together with Rivest's Introduction to Algorithms), but also iterate through those mapping inward a predefined sorted order, but yous require to pay a heavy cost to pop off on mappings inward sorted order.
On the other hand, LinkedHashMap is a compromise betwixt these two, it doesn't render sorting but dissimilar HashMap, it provides ordering e.g. maintaining mappings inward an firm they are inserted into Map, known every bit insertion order or firm on which they are accessed, called access order.
Apart from these 3 pop Map implementation, yous also convey simply about particular purpose Map implementations e.g. EnumMap for storing mapping amongst enum constants every bit keys, it is highly optimized for enum constants. You also convey a particular map called WeakHashMap for creating a Garbage Collector friendly Cache, where values larn eligible for garbage collection every bit shortly every bit in that place is no other reference to them apart from keys inward WeakHashMap.
Then in that place is IdentityHashMap for creating a Map which uses identity instead of equality for comparison keys since identity equality is rare, yous larn less number of collisions on this Map together with finally, JDK five introduced ConcurrentHashMap for improve scalability inward a multi-threaded environment, where the number of reader threads clearly outnumbers a number of author threads.
LinkedHashMap vs TreeMap vs HashMap
Though all 3 classes implement java.util.Map interface together with follows full general contract of a Map interface, defined inward damage of equals() together with hashCode() method, they also convey several differences inward damage of Ordering, Sorting, permitting nothing elements, Iteration, Performance, Speed together with internal implementation. Let's convey a quick await on each of these properties.Ordering together with Sorting
HashMap doesn't render whatsoever ordering guarantee for entries, which means, yous tin non assume whatsoever firm piece iterating over keys together with values of HashMap. This conduct of HashMap is similar to Hashtable piece other 2 Map implementation provides ordering guarantee.LinkedHashMap tin hold upward used to maintain insertion order, on which keys are inserted into Map or it tin also hold upward used to maintain an access order, on which keys are accessed. This provides LinkedHashMap an border over HashMap without compromising also much performance.
TreeMap provides yous consummate command over sorting elements past times passing custom Comparator of your choice, but amongst the expense of simply about performance. Since entries are stored inward a tree-based information structure, it provides lower performance than HashMap together with LinkedHashMap.
Null keys together with Values
HashMap allows one null telephone commutation together with multiple null values. It keeps nothing telephone commutation based entries on index[0] on an internal bucket. If yous await at the put() method of HashMap, yous tin see, it doesn't throw NullPointerException for nothing keys. Since LinkedHashMap is a subclass of HashMap, it also allows null keys together with values.On the other hand, TreeMap, which sorts elements inward natural firm doesn't allow nothing keys because compareTo() method throws NullPointerException if compared amongst null. If yous are using TreeMap amongst user defined Comparator than it depends upon the implementation of compare() method.
Iterators
Iterators returned past times all these Map's collection persuasion methods e.g. values() or keySet() is fail-fast iterators, which agency they volition throw ConcurrentModificatoinException if Collection is modified structurally i time Iteration begins, except past times using remove() method of Iterator.By the way, it's worth remembering that apart from adding or removing to a greater extent than mappings, it tin also hold upward whatsoever functioning which affects iteration firm of LinkedHashMap. In access-ordered LinkedHashMap, fifty-fifty querying the Map amongst get() method is a structural modification, because it changes the iteration order, on the other mitt updating the value inward an insertion-ordered linked hash map is non a structural modification.
Finally, the fail-fast conduct is non guaranteed, together with they throw ConcurrentModificationException on the best-effort basis, which agency exercise non write code, which depends upon this behavior. It should alone hold upward used to uncovering programming bugs.
Performance together with Speed
Since HashMap is a barebone implementation of java.util.Map interface, it provides constant fourth dimension performance for the get() together with put() operation, where put() method is used to shop entries (key-value pairs) together with get() is used to retrieve a value based on a key.BTW, constant fourth dimension performance is alone provided if mappings are distributed uniformly across bucket location. In the existent world, yous ever convey collision together with HashMap handles collision past times using a linked listing to shop collided elements. This tin cut worst instance performance of HashMap upward to O(n).
To mitigate the higher upward performance issue, JDK 8 has introduced balanced tree instead of linked listing inward instance of frequent collision inward HashMap. It internally switches to balanced tree from linked listing if in that place are to a greater extent than than 8 entries inward i bucket. See how does HashMap handles collisions inward Java for to a greater extent than details.
Worth noting is that this conduct is alone applicable to HashMap, LinkedHashMap, together with ConcurrentHashMap, Hashtable is left behind to save its legacy iteration firm every bit many legacy Java application relies on that together with this changes that order. This is also a skilful representative of why yous should non rely on undocumented features of JDK e.g. iteration firm of HashMap because they tin alter inward future.
but HashMap is surely faster than Hashtable because it's non synchronized. Iteration over Map is conduct proportional to the "capacity" + "size" of HashMap, that's why it's of import to gear upward the initial capacity high plenty if iteration performance is important. You tin farther utilization initial capacity together with load factor to fine melody your HashMap performance, to avoid rehashing of HashMap.
TreeMap is so it's costlier than HashMap if the order is non concerned. Since TreeMap is based on tree information construction (based upon Red-Black tree), it provides the log(n) fourth dimension for the get(), put(), containsKey() together with remove() operation, Algorithms are based upon those given inward Cormen, Leiserson, together with Rivest's Introduction to Algorithms.
LinkedHashMap is a trade-off betwixt two, similar HashMap it also provides constant fourth dimension performance for add, contains together with remove, though it's slightly slower than HashMap, to maintain linked list. By the way, looping over Map inward the instance of LinkedHashMap is slightly faster than HashMap because the fourth dimension required is proportional to size only. So if yous require insertion firm or access order, consider using LinkedHashMap over TreeMap inward Java.
Thread-safety together with Synchronization
All 3 Map implementation are not thread-safe, which agency yous tin non utilization them safely inward a multi-threaded application. Though yous tin synchronize them externally past times using Collections.synchronizedMap(Map map) method. Alternatively, yous tin also utilization their concurrent counterpart e.g. ConcurrentHashMap which is also a improve selection than HashMap inward a concurrent Java application.When using synchronized Map e.g. synchronized LinkedHashMap or SortedMap, yous must exercise at the fourth dimension or creating the map to forbid accidental non-synchronized access. You tin utilization the next idiom to create Synchronized Map inward Java:
Synchronized LinkedHashMap
Map<Integer, Integer> numbers = Collections.synchronizedMap(new LinkedHashMap<>());
Synchronized TreeMap
SortedMap<Integer, String> sorted = Collections.synchronizedSortedMap(new TreeMap<>());
Remember to utilization Collections.synchronizedMap() for synchronizing HashMap, LinkedHashMap together with Collections.synchronizedSortedMap() method for synchronizing TreeMap. If yous are non comfortable therefore come across this guide on how to synchronize HashMap inward Java.
Internal Implementation
TreeMap is Red-Black tree based NavigableMap implementation piece HashMap is internally backed past times an array. It uses index[0] to shop entries corresponding to nothing keys. In fact, questions related to the inner working of HashMap is rattling pop inward Java, for example, How does get() method of HashMap plant internally is i of the oft used questions to Senior Java developers.On the other hand, LinkedHashMap extends HashMap together with uses linked listing to render insertion firm guarantee. It uses doubly-linked listing running through all of its entries, which tin also hold upward used to maintain access-order. Remember, insertion firm is non affected if a telephone commutation is re-inserted into LinkedHashMap, but access firm is affected if LinkedHashMap is created to maintain access-order.
TreeMap is internally based upon Red-Black Tree together with NavigableMap, introduced inward JDK 6. The Red-Black tree is used to maintain the sorting firm imposed past times Comparable or Comparator, provided at the fourth dimension of creation. TreeMap provides guaranteed log(n) fourth dimension cost for the get, put, containsKey together with withdraw operations. Algorithms are adaptations of those inward Cormen, Leiserson, together with Rivest's Introduction to Algorithms.
When to utilization LinkedHashMap, TreeMap, together with HashMap
You tin utilization a LinkedHashMap when yous require to pop off on your mappings inward either insertion order or access order. LinkedHashMap past times default keeps elements inward the order, on which they are inserted, together with this firm is reflected when yous traverse over LinkedHashMap, but it also provides a constructor, which allows yous to pop off on entries inward access order, the. firm inward which they are accessed. One of the clever utilization of Java LinkedHashMap is to utilization it every bit Least Recently Use or LRU Cache.TreeMap is your pop off to map implementation if yous desire to pop off on keys in a sorted order, either inward their natural firm defined past times Comparable interface or a custom firm imposed past times Comparator interface, though it's worth remembering that your compareTo() or compare() method must hold upward consistent amongst equals() method, because Map interface is defined inward damage of equals together with TreeMap uses compareTo for comparison keys. So if keys compare() or compareTo() implementation is non consistent, therefore it volition neglect to obey Map's full general contract.
HashMap is your full general purpose hashing based collection, whenever yous require to utilization a hash tabular array information construction inward Java to shop key-value pairs, the start selection goes to HashMap inward a unmarried threaded environment. If yous happened to utilization a Map inward a multi-threaded surroundings consider using Hashtable, synchronized HashMap or ConcurrentHashMap from Java Collection Framework.
Since LinkedHashMap solved the work of chaotic ordering provided past times Hashtable together with HashMap, without incurring the high cost associated amongst TreeMap, yous tin also utilization LinkedHashMap to create a re-create of a Map inward Java, every bit shown inward below example.
An representative of using LinkedHashMap, TreeMap together with HashMap inward Java
Let's come across an representative of how to utilization these Map implementations. In this example, nosotros volition utilization HashMap to create a full general purpose Cache, TreeMap to create a sorted Cache together with nosotros volition utilization LinkedHashMap for copying a Map (cache) together with maintaining orders inward the master Map.import java.util.Collections; import java.util.HashMap; import java.util.LinkedHashMap; import java.util.Map; import java.util.SortedMap; import java.util.TreeMap; /** * Java Program to demonstrate How to utilization LinkedHashMap, TreeMap together with HashMap. * It shows that HashMap doesn't guarantee whatsoever order, TreeMap keeps them in * sorted firm determined past times default using Comparable or explicit Comparator * provided past times client, together with LinkedHashMap also pop off on mapping inward firm they * are added or accessed.,
* * @author Javin Paul */ public class MapTest { public static void main(String args[]){ //Using HashMap every bit full general purpose unmarried threaded cache Map<Integer, String> cache = new HashMap<>(); cache.put(1, "Stuart"); cache.put(2, "Steven"); cache.put(3, "James"); cache.put(4, "Ian"); System.out.printf("Name of Employee amongst id %d is %s %n", 1, cache.get(1)); System.out.println("Order of Entries inward HashMap - Not guaranteed"); System.out.println(cache); //Using TreeMap to create a sorted cache, sorting keys on contrary order SortedMap<Integer, String> sortedCache = new TreeMap<>(Collections.reverseOrder()); sortedCache.putAll(cache); System.out.println("Order of Entries inward TreeMap - Sorted inward contrary order"); System.out.println(sortedCache); //Using LinkedHashMap to create re-create of a Map inward Java Map<Integer, String> re-create = new LinkedHashMap<>(sortedCache); System.out.println("Order of Entries inward a re-create Map created past times LinkedHashMap"); System.out.println(copy); } } Output: Name of Employee amongst id 1 is Stuart Order of Entries inward HashMap - Not guaranteed {1=Stuart, 2=Steven, 3=James, 4=Ian} Order of Entries inward TreeMap - Sorted inward contrary firm {4=Ian, 3=James, 2=Steven, 1=Stuart} Order of Entries inward a re-create Map created past times LinkedHashMap {4=Ian, 3=James, 2=Steven, 1=Stuart}
You tin come across that TreeMap has sorted mappings inward contrary order, because of contrary Comparator provided to it. Also, LinkedHashMap has created a re-create of TreeMap together with firm of entries are retained.
Summary
Here is the summary of differences betwixt HashMap, LinkedHashMap, together with TreeMap inward Java:
That's all on the difference betwixt LinkedHashMap, TreeMap, together with HashMap inward Java. Though all 3 are Map implementation, they convey a different purpose together with used accordingly. Use LinkedHashMap, if yous require to maintain insertion or access firm of mappings e.g. inward LRU Cache. Use TreeMap, if yous require to maintain mappings inward a sorted order, either inward their natural firm or a custom firm defined past times Comparator together with utilization HashMap for all your full general purpose hashing based collection requirement. HashMap allows yous to retrieve an object inward O(1) fourth dimension if yous know the key.
Further Learning
Java In-Depth: Become a Complete Java Engineer
answer)
Thanks for reading this article therefore far. If yous similar this article therefore delight part amongst your friends together with colleagues. If yous convey whatsoever questions or feedback therefore delight drib a comment.