Difference Betwixt Hashmap, Linkedhashmap As Well As Treemap Inwards Java
The java.util.Map is i of the around of import interfaces from Java Collection Framework. It provides hash tabular array information construction functionality past times its implementations similar HashMap, Hashtable, LinkedHashMap too a trivial chip of sorting amongst the TreeMap. So if y'all are looking to shop key-value pairs inward Java program, you accept a broad make of choices available depending upon your requirement. The primary divergence betwixt LinkedHashMap, TreeMap too HashMap comes inward their internal implementation too 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 endure used whenever y'all ask a hashing-based information construction for storing your mappings (key-value pairs).
TreeMap is a Red-Black tree based NavigableMap implementation provides y'all sorting, on top of hashing offered past times Map interface. This agency y'all tin dismiss non exclusively retrieve elements inward guaranteed log(n) fourth dimension (Algorithms are adaptations of those inward Cormen, Leiserson, too Rivest's Introduction to Algorithms), but also iterate through those mapping inward a predefined sorted order, but y'all ask to pay a heavy toll to give-up the ghost on mappings inward sorted order.
On the other hand, LinkedHashMap is a compromise betwixt these two, it doesn't supply sorting but different HashMap, it provides ordering e.g. maintaining mappings inward an companionship they are inserted into Map, known every bit insertion order or companionship on which they are accessed, called access order.
Apart from these iii pop Map implementation, y'all also accept unopen to 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 accept a particular map called WeakHashMap for creating a Garbage Collector friendly Cache, where values give-up the ghost eligible for garbage collection every bit shortly every bit at that topographic point is no other reference to them apart from keys inward WeakHashMap.
Then at that topographic point is IdentityHashMap for creating a Map which uses identity instead of equality for comparison keys since identity equality is rare, y'all teach less number of collisions on this Map too finally, JDK v introduced ConcurrentHashMap for amend scalability inward a multi-threaded environment, where the number of reader threads clearly outnumbers a number of author threads.
LinkedHashMap tin dismiss endure used to maintain insertion order, on which keys are inserted into Map or it tin dismiss also endure 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 y'all consummate command over sorting elements past times passing custom Comparator of your choice, but amongst the expense of unopen to performance. Since entries are stored inward a tree-based information structure, it provides lower performance than HashMap too LinkedHashMap.
On the other hand, TreeMap, which sorts elements inward natural companionship doesn't allow nil keys because compareTo() method throws NullPointerException if compared amongst null. If y'all 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 dismiss also endure whatever functioning which affects iteration companionship 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 demeanour is non guaranteed, too they throw ConcurrentModificationException on the best-effort basis, which agency practise non write code, which depends upon this behavior. It should exclusively endure used to honor programming bugs.
BTW, constant fourth dimension performance is exclusively provided if mappings are distributed uniformly across bucket location. In the existent world, y'all ever accept collision too HashMap handles collision past times using a linked listing to shop collided elements. This tin dismiss trim down worst illustration performance of HashMap upwards to O(n).
To mitigate the inward a higher house performance issue, JDK 8 has introduced balanced tree instead of linked listing inward illustration of frequent collision inward HashMap. It internally switches to balanced tree from linked listing if at that topographic point 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 demeanour is exclusively applicable to HashMap, LinkedHashMap, too ConcurrentHashMap, Hashtable is left behind to save its legacy iteration companionship every bit many legacy Java application relies on that too this changes that order. This is also a proficient illustration of why y'all should non rely on undocumented features of JDK e.g. iteration companionship of HashMap because they tin dismiss alter inward future.
but HashMap is sure enough faster than Hashtable because it's non synchronized. Iteration over Map is take proportional to the "capacity" + "size" of HashMap, that's why it's of import to ready the initial capacity high plenty if iteration performance is important. You tin dismiss farther usage initial capacity too 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() too remove() operation, Algorithms are based upon those given inward Cormen, Leiserson, too Rivest's Introduction to Algorithms.
LinkedHashMap is a trade-off betwixt two, similar HashMap it also provides constant fourth dimension performance for add, contains too remove, though it's slightly slower than HashMap, to maintain linked list. By the way, looping over Map inward the illustration of LinkedHashMap is slightly faster than HashMap because the fourth dimension required is proportional to size only. So if y'all ask insertion companionship or access order, consider using LinkedHashMap over TreeMap inward Java.
When using synchronized Map e.g. synchronized LinkedHashMap or SortedMap, y'all must practise at the fourth dimension or creating the map to preclude accidental non-synchronized access. You tin dismiss usage the next idiom to create Synchronized Map inward Java:
Synchronized LinkedHashMap
Synchronized TreeMap
Remember to usage Collections.synchronizedMap() for synchronizing HashMap, LinkedHashMap too Collections.synchronizedSortedMap() method for synchronizing TreeMap. If y'all are non comfortable too thus run into this guide on how to synchronize HashMap inward Java.
On the other hand, LinkedHashMap extends HashMap too uses linked listing to supply insertion companionship guarantee. It uses doubly-linked listing running through all of its entries, which tin dismiss also endure used to maintain access-order. Remember, insertion companionship is non affected if a primal is re-inserted into LinkedHashMap, but access companionship is affected if LinkedHashMap is created to maintain access-order.
TreeMap is internally based upon Red-Black Tree too NavigableMap, introduced inward JDK 6. The Red-Black tree is used to maintain the sorting companionship 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 too take operations. Algorithms are adaptations of those inward Cormen, Leiserson, too Rivest's Introduction to Algorithms.
TreeMap is your give-up the ghost to map implementation if y'all desire to give-up the ghost on keys in a sorted order, either inward their natural companionship defined past times Comparable interface or a custom companionship imposed past times Comparator interface, though it's worth remembering that your compareTo() or compare() method must endure consistent amongst equals() method, because Map interface is defined inward price of equals too TreeMap uses compareTo for comparison keys. So if keys compare() or compareTo() implementation is non consistent, too thus it volition neglect to obey Map's full general contract.
HashMap is your full general purpose hashing based collection, whenever y'all ask to usage a hash tabular array information construction inward Java to shop key-value pairs, the commencement selection goes to HashMap inward a unmarried threaded environment. If y'all happened to usage a Map inward a multi-threaded environs consider using Hashtable, synchronized HashMap or ConcurrentHashMap from Java Collection Framework.
Since LinkedHashMap solved the work of chaotic ordering provided past times Hashtable too HashMap, without incurring the high cost associated amongst TreeMap, y'all tin dismiss also usage LinkedHashMap to create a re-create of a Map inward Java, every bit shown inward below example.
You tin dismiss run into that TreeMap has sorted mappings inward contrary order, because of contrary Comparator provided to it. Also, LinkedHashMap has created a re-create of TreeMap too companionship of entries are retained.
That's all on the difference betwixt LinkedHashMap, TreeMap, too HashMap inward Java. Though all iii are Map implementation, they accept a different purpose too used accordingly. Use LinkedHashMap, if y'all ask to maintain insertion or access companionship of mappings e.g. inward LRU Cache. Use TreeMap, if y'all ask to maintain mappings inward a sorted order, either inward their natural companionship or a custom companionship defined past times Comparator too usage HashMap for all your full general purpose hashing based collection requirement. HashMap allows y'all to retrieve an object inward O(1) fourth dimension if y'all know the key.
Further Learning
Java In-Depth: Become a Complete Java Engineer
answer)What is the divergence betwixt HashMap too ArrayList inward Java? (answer) What is the divergence betwixt HashSet too ArrayList inward Java? (answer) 5 differences betwixt HashMap too Hashtable inward Java? (answer) What is the divergence betwixt ArrayList too LinkedList inward Java? (answer) How to usage NavigableMap inward Java 6? [example] How to usage BlockingQueue inward Java Program? [example]
TreeMap is a Red-Black tree based NavigableMap implementation provides y'all sorting, on top of hashing offered past times Map interface. This agency y'all tin dismiss non exclusively retrieve elements inward guaranteed log(n) fourth dimension (Algorithms are adaptations of those inward Cormen, Leiserson, too Rivest's Introduction to Algorithms), but also iterate through those mapping inward a predefined sorted order, but y'all ask to pay a heavy toll to give-up the ghost on mappings inward sorted order.
On the other hand, LinkedHashMap is a compromise betwixt these two, it doesn't supply sorting but different HashMap, it provides ordering e.g. maintaining mappings inward an companionship they are inserted into Map, known every bit insertion order or companionship on which they are accessed, called access order.
Apart from these iii pop Map implementation, y'all also accept unopen to 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 accept a particular map called WeakHashMap for creating a Garbage Collector friendly Cache, where values give-up the ghost eligible for garbage collection every bit shortly every bit at that topographic point is no other reference to them apart from keys inward WeakHashMap.
Then at that topographic point is IdentityHashMap for creating a Map which uses identity instead of equality for comparison keys since identity equality is rare, y'all teach less number of collisions on this Map too finally, JDK v introduced ConcurrentHashMap for amend 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 iii classes implement java.util.Map interface too follows full general contract of a Map interface, defined inward price of equals() too hashCode() method, they also accept several differences inward price of Ordering, Sorting, permitting nil elements, Iteration, Performance, Speed too internal implementation. Let's accept a quick await on each of these properties.Ordering too Sorting
HashMap doesn't supply whatever ordering guarantee for entries, which means, y'all tin dismiss non assume whatever companionship land iterating over keys too values of HashMap. This demeanour of HashMap is similar to Hashtable land other ii Map implementation provides ordering guarantee.LinkedHashMap tin dismiss endure used to maintain insertion order, on which keys are inserted into Map or it tin dismiss also endure 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 y'all consummate command over sorting elements past times passing custom Comparator of your choice, but amongst the expense of unopen to performance. Since entries are stored inward a tree-based information structure, it provides lower performance than HashMap too LinkedHashMap.
Null keys too Values
HashMap allows one null primal too multiple null values. It keeps nil primal based entries on index[0] on an internal bucket. If y'all await at the put() method of HashMap, y'all tin dismiss see, it doesn't throw NullPointerException for nil keys. Since LinkedHashMap is a subclass of HashMap, it also allows null keys too values.On the other hand, TreeMap, which sorts elements inward natural companionship doesn't allow nil keys because compareTo() method throws NullPointerException if compared amongst null. If y'all 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 sentiment methods e.g. values() or keySet() is fail-fast iterators, which agency they volition throw ConcurrentModificatoinException if Collection is modified structurally in i lawsuit 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 dismiss also endure whatever functioning which affects iteration companionship 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 demeanour is non guaranteed, too they throw ConcurrentModificationException on the best-effort basis, which agency practise non write code, which depends upon this behavior. It should exclusively endure used to honor programming bugs.
Performance too Speed
Since HashMap is a barebone implementation of java.util.Map interface, it provides constant fourth dimension performance for the get() too put() operation, where put() method is used to shop entries (key-value pairs) too get() is used to retrieve a value based on a key.BTW, constant fourth dimension performance is exclusively provided if mappings are distributed uniformly across bucket location. In the existent world, y'all ever accept collision too HashMap handles collision past times using a linked listing to shop collided elements. This tin dismiss trim down worst illustration performance of HashMap upwards to O(n).
To mitigate the inward a higher house performance issue, JDK 8 has introduced balanced tree instead of linked listing inward illustration of frequent collision inward HashMap. It internally switches to balanced tree from linked listing if at that topographic point 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 demeanour is exclusively applicable to HashMap, LinkedHashMap, too ConcurrentHashMap, Hashtable is left behind to save its legacy iteration companionship every bit many legacy Java application relies on that too this changes that order. This is also a proficient illustration of why y'all should non rely on undocumented features of JDK e.g. iteration companionship of HashMap because they tin dismiss alter inward future.
but HashMap is sure enough faster than Hashtable because it's non synchronized. Iteration over Map is take proportional to the "capacity" + "size" of HashMap, that's why it's of import to ready the initial capacity high plenty if iteration performance is important. You tin dismiss farther usage initial capacity too 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() too remove() operation, Algorithms are based upon those given inward Cormen, Leiserson, too Rivest's Introduction to Algorithms.
LinkedHashMap is a trade-off betwixt two, similar HashMap it also provides constant fourth dimension performance for add, contains too remove, though it's slightly slower than HashMap, to maintain linked list. By the way, looping over Map inward the illustration of LinkedHashMap is slightly faster than HashMap because the fourth dimension required is proportional to size only. So if y'all ask insertion companionship or access order, consider using LinkedHashMap over TreeMap inward Java.
Thread-safety too Synchronization
All iii Map implementation are not thread-safe, which agency y'all tin dismiss non usage them safely inward a multi-threaded application. Though y'all tin dismiss synchronize them externally past times using Collections.synchronizedMap(Map map) method. Alternatively, y'all tin dismiss also usage their concurrent counterpart e.g. ConcurrentHashMap which is also a amend selection than HashMap inward a concurrent Java application.When using synchronized Map e.g. synchronized LinkedHashMap or SortedMap, y'all must practise at the fourth dimension or creating the map to preclude accidental non-synchronized access. You tin dismiss usage 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 usage Collections.synchronizedMap() for synchronizing HashMap, LinkedHashMap too Collections.synchronizedSortedMap() method for synchronizing TreeMap. If y'all are non comfortable too thus run into this guide on how to synchronize HashMap inward Java.
Internal Implementation
TreeMap is Red-Black tree based NavigableMap implementation land HashMap is internally backed past times an array. It uses index[0] to shop entries corresponding to nil keys. In fact, questions related to the inner working of HashMap is really pop inward Java, for example, How does get() method of HashMap plant internally is i of the often used questions to Senior Java developers.On the other hand, LinkedHashMap extends HashMap too uses linked listing to supply insertion companionship guarantee. It uses doubly-linked listing running through all of its entries, which tin dismiss also endure used to maintain access-order. Remember, insertion companionship is non affected if a primal is re-inserted into LinkedHashMap, but access companionship is affected if LinkedHashMap is created to maintain access-order.
TreeMap is internally based upon Red-Black Tree too NavigableMap, introduced inward JDK 6. The Red-Black tree is used to maintain the sorting companionship 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 too take operations. Algorithms are adaptations of those inward Cormen, Leiserson, too Rivest's Introduction to Algorithms.
When to usage LinkedHashMap, TreeMap, too HashMap
You tin dismiss usage a LinkedHashMap when y'all ask to give-up the ghost on your mappings inward either insertion order or access order. LinkedHashMap past times default keeps elements inward the order, on which they are inserted, too this companionship is reflected when y'all traverse over LinkedHashMap, but it also provides a constructor, which allows y'all to give-up the ghost on entries inward access order, the. companionship inward which they are accessed. One of the clever usage of Java LinkedHashMap is to usage it every bit Least Recently Use or LRU Cache.TreeMap is your give-up the ghost to map implementation if y'all desire to give-up the ghost on keys in a sorted order, either inward their natural companionship defined past times Comparable interface or a custom companionship imposed past times Comparator interface, though it's worth remembering that your compareTo() or compare() method must endure consistent amongst equals() method, because Map interface is defined inward price of equals too TreeMap uses compareTo for comparison keys. So if keys compare() or compareTo() implementation is non consistent, too thus it volition neglect to obey Map's full general contract.
HashMap is your full general purpose hashing based collection, whenever y'all ask to usage a hash tabular array information construction inward Java to shop key-value pairs, the commencement selection goes to HashMap inward a unmarried threaded environment. If y'all happened to usage a Map inward a multi-threaded environs consider using Hashtable, synchronized HashMap or ConcurrentHashMap from Java Collection Framework.
Since LinkedHashMap solved the work of chaotic ordering provided past times Hashtable too HashMap, without incurring the high cost associated amongst TreeMap, y'all tin dismiss also usage LinkedHashMap to create a re-create of a Map inward Java, every bit shown inward below example.
An illustration of using LinkedHashMap, TreeMap too HashMap inward Java
Let's run into an illustration of how to usage these Map implementations. In this example, nosotros volition usage HashMap to create a full general purpose Cache, TreeMap to create a sorted Cache too nosotros volition usage LinkedHashMap for copying a Map (cache) too 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 usage LinkedHashMap, TreeMap too HashMap. * It shows that HashMap doesn't guarantee whatever order, TreeMap keeps them in * sorted companionship determined past times default using Comparable or explicit Comparator * provided past times client, too LinkedHashMap also give-up the ghost on mapping inward companionship 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 companionship {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 dismiss run into that TreeMap has sorted mappings inward contrary order, because of contrary Comparator provided to it. Also, LinkedHashMap has created a re-create of TreeMap too companionship of entries are retained.
Summary
Here is the summary of differences betwixt HashMap, LinkedHashMap, too TreeMap inward Java:
That's all on the difference betwixt LinkedHashMap, TreeMap, too HashMap inward Java. Though all iii are Map implementation, they accept a different purpose too used accordingly. Use LinkedHashMap, if y'all ask to maintain insertion or access companionship of mappings e.g. inward LRU Cache. Use TreeMap, if y'all ask to maintain mappings inward a sorted order, either inward their natural companionship or a custom companionship defined past times Comparator too usage HashMap for all your full general purpose hashing based collection requirement. HashMap allows y'all to retrieve an object inward O(1) fourth dimension if y'all know the key.
Further Learning
Java In-Depth: Become a Complete Java Engineer
answer)
Thanks for reading this article thus far. If y'all similar this article too thus delight portion amongst your friends too colleagues. If y'all accept whatever questions or feedback too thus delight drib a comment.
0 Response to "Difference Betwixt Hashmap, Linkedhashmap As Well As Treemap Inwards Java"
Post a Comment