Difference between HashMap LinkedHashMap and TreeMap

Question

What is the difference between HashMap  LinkedHashMap and TreeMap in Java   I don t see any difference in the output as all the three has keySet and values  What are Hashtables   Map m1   new HashMap    m1 put  map    HashMap    m1 put  schildt    java2    m1 put  mathew    Hyden    m1 put  schildt    java2s    print m1 keySet      print m1 values       SortedMap sm   new TreeMap    sm put  map    TreeMap    sm put  schildt    java2    sm put  mathew    Hyden    sm put  schildt    java2s    print sm keySet      print sm values      LinkedHashMap lm   new LinkedHashMap    lm put  map    LinkedHashMap    lm put  schildt    java2    lm put  mathew    Hyden    lm put  schildt    java2s    print lm keySet      print lm values

User · Answer

Following are major difference between HashMap and TreeMap

HashMap does not maintain any order. In other words , HashMap does not provide any guarantee that the element inserted first will be printed first, where as Just like TreeSet , TreeMap elements are also sorted according to the natural ordering of its elements
Internal HashMap implementation use Hashing and TreeMap internally uses Red-Black tree implementation.
HashMap can store one null key and many null values.TreeMap can not contain null keys but may contain many null values.
HashMap take constant time performance for the basic operations like get and put i.e O(1).According to Oracle docs , TreeMap provides guaranteed log(n) time cost for the get and put method.
HashMap is much faster than TreeMap, as performance time of HashMap is constant against the log time TreeMap for most operations.
HashMap uses equals() method in comparison while TreeMap uses compareTo() method for maintaining ordering.
HashMap implements Map interface while TreeMap implements NavigableMap interface.

User · Answer

These are different implementations of the same interface  Each implementation has some advantages and some disadvantages  fast insert  slow search  or vice versa   For details look at the javadoc of TreeMap  HashMap  LinkedHashMap

User · Answer

All three classes implement the Map interface and offer mostly the same functionality  The most important difference is the order in which iteration through the entries will happen    HashMap makes absolutely no guarantees about the iteration order  It can  and will  even change completely when new elements are added  TreeMap will iterate according to the  natural ordering  of the keys according to their compareTo   method  or an externally supplied Comparator   Additionally  it implements the SortedMap interface  which contains methods that depend on this sort order  LinkedHashMap will iterate in the order in which the entries were put into the map    Hashtable  is the generic name for hash-based maps  In the context of the Java API  Hashtable is an obsolete class from the days of Java 1 1 before the collections framework existed  It should not be used anymore  because its API is cluttered with obsolete methods that duplicate functionality  and its methods are synchronized  which can decrease performance and is generally useless   Use ConcurrentHashMap instead of Hashtable

User · Answer

All three classes HashMap  TreeMap and LinkedHashMap implements java util Map interface  and represents mapping from unique key to values    HashMap   A HashMap contains values based on the key  It contains only    unique elements   It may have one null key and multiple null values  It maintains no order   public class HashMap lt K V gt  extends AbstractMap lt K V gt  implements Map lt K V gt   Cloneable  Serializable   LinkedHashMap   A LinkedHashMap contains values based on the key  It contains only unique elements  It may have one null key and multiple null values  It is same as HashMap instead maintains insertion order    See class deceleration below  public class LinkedHashMap lt K V gt  extends HashMap lt K V gt  implements Map lt K V gt    TreeMap   A TreeMap contains values based on the key  It implements the NavigableMap interface and extends AbstractMap class  It contains only unique elements  It cannot have null key but can have multiple null values  It is same as HashMap instead maintains ascending order Sorted using the natural order of its key     public class TreeMap lt K V gt  extends AbstractMap lt K V gt  implements NavigableMap lt K V gt   Cloneable  Serializable    Hashtable   A Hashtable is an array of list  Each list is known as a bucket  The position of bucket is identified by calling the hashcode   method  A Hashtable contains values based on the key  It contains only unique elements  It may have not have any null key or value  It is synchronized  It is a legacy class   public class Hashtable lt K V gt  extends Dictionary lt K V gt  implements Map lt K V gt   Cloneable  Serializable     Ref  http   javarevisited blogspot in 2015 08 difference-between-HashMap-vs-TreeMap-vs-LinkedHashMap-Java html

User · Answer

HashMap can contain one null key   HashMap maintains no order    TreeMap  TreeMap can not contain any null key   TreeMap maintains ascending order   LinkedHashMap  LinkedHashMap can be used to maintain insertion order  on which keys are inserted into Map or it can also be used to maintain an access order  on which keys are accessed   Examples    1  HashMap map   new HashMap         map put null   Kamran        map put 2   Ali        map put 5   From        map put 4   Dir    enter code here      map put 3   Lower        for  Map Entry m   map entrySet              System out println m getKey            m getValue              2  TreeMap map   new TreeMap         map put 1   Kamran        map put 2   Ali        map put 5   From        map put 4   Dir        map put 3   Lower        for  Map Entry m   map entrySet              System out println m getKey            m getValue             3  LinkedHashMap map   new LinkedHashMap         map put 1   Kamran        map put 2   Ali        map put 5   From        map put 4   Dir        map put 3   Lower        for  Map Entry m   map entrySet              System out println m getKey            m getValue

User · Answer

See where each class is in the class hierarchy in the following diagram  bigger one   TreeMap implements SortedMap and NavigableMap while HashMap doesn t   HashTable is obsolete and the corresponding ConcurrentHashMap class should be used

User · Answer

HashMap    Order not maintains Faster than LinkedHashMap Used for store heap of objects   LinkedHashMap    LinkedHashMap insertion order will be maintained Slower than HashMap and faster than TreeMap If you want to maintain an insertion order use this   TreeMap    TreeMap is a tree-based mapping TreeMap will follow the natural ordering of key Slower than HashMap and LinkedHashMap Use TreeMap when you need to maintain natural default  ordering

User · Answer

All offer a key- value map and a way to iterate through the keys  The most important distinction between these classes are the time guarantees and the ordering of the keys    HashMap offers 0 1  lookup and insertion  If you iterate through the keys  though  the ordering of the keys is essentially arbitrary  It is implemented by an array of linked lists  TreeMap offers O log N  lookup and insertion  Keys are ordered  so if you need to iterate through the keys in sorted order  you can  This means that keys must implement the Comparable interface TreeMap is implemented by a Red-Black Tree  LinkedHashMap offers 0 1  lookup and insertion  Keys are ordered by their insertion order  It is implemented by doubly-linked buckets    Imagine you passed an empty TreeMap  HashMap  and LinkedHashMap into the following function   void insertAndPrint AbstractMap lt Integer  String gt  map      int   array   1  -1  0     for  int x   array        map put x  Integer toString x          for  int k  map keySet         System out print k                  The output for each will look like the results below   For HashMap  the output was  in my own tests    0  1  -1   but it could be any ordering  There is no guarantee on the ordering  Treemap the output was   -1  0  1  LinkedList the output was   1  -1  0

User · Answer

Hash map doesn t  preserves the insertion order  Example   Hashmap If you are inserting keys as   1  3 5  9 4   6 7   15 3   10   It can store it as   4  6 5  9 3  10 1  3 7  15   Linked Hashmap  preserves the insertion order     Example  If you are inserting keys   1  3 5  9 4   6 7   15 3   10   It will store it as  1  3 5  9 4   6 7   15 3   10   same as we insert    Tree map stores the vales in Increasing Order Of Keys   Example  If you are inserting keys   1  3 5  9 4   6 7   15 3   10   It will store it as  1  3 3  10 4   6 5   9 7   15

User · Answer

While there are plenty of excellent Answers here  I d like to present my own table describing the various Map implementations bundled with Java 11   We can see these differences listed on the table graphic    HashMap is the general-purpose Map commonly used when you have no special needs  LinkedHashMap extends HashMap  adding this behavior  Maintains an order  the order in which the entries were originally added  Altering the value for key-value entry does not alter its place in the order  TreeMap too maintains an order  but uses either  a  the    natural    order  meaning the value of the compareTo method on the key objects defined on the Comparable interface  or  b  invokes a Comparator implementation you provide     TreeMap implements both the SortedMap interface  and its successor  the NavigableMap interface   NULLs  TreeMap does not allow a NULL as the key  while HashMap  amp  LinkedHashMap do     All three allow NULL as the value   HashTable is legacy  from Java 1  Supplanted by the ConcurrentHashMap class  Quoting the Javadoc  ConcurrentHashMap obeys the same functional specification as Hashtable  and includes versions of methods corresponding to each method of Hashtable

User · Answer

HashMap makes absolutely not guarantees about the iteration order  It   can  and will  even change completely when new elements are added    TreeMap will iterate according to the  natural ordering  of the keys   according to their compareTo   method  or an externally supplied   Comparator   Additionally  it implements the SortedMap interface    which contains methods that depend on this sort order  LinkedHashMap   will iterate in the order in which the entries were put into the map   Look at how performance varying     Tree map which is an implementation of Sorted map  The complexity of the put  get and containsKey operation is O log n  due to the Natural ordering

User · Answer

I prefer visual presentation     ------------------------------------------------------------------------------       Property            HashMap               TreeMap             LinkedHashMap        -------------- --------------------- ------------------- ---------------------      Iteration        no guarantee order    sorted according                                 Order         will remain constant   to the natural          insertion-order                             over time            ordering                                   -------------- --------------------- ------------------- ---------------------       Get put                                                                                remove                O 1                 O log n                 O 1               containsKey                                                                          -------------- --------------------- ------------------- ---------------------                                               NavigableMap                                  Interfaces             Map                  Map                    Map                                                         SortedMap                                  -------------- --------------------- ------------------- ---------------------                                                                                                Null              allowed             only values             allowed             values keys                                                                          -------------- ---------------------------------------------------------------                        Fail-fast behavior of an iterator cannot be guaranteed              Fail-fast     impossible to make any hard guarantees in the presence of             behavior                unsynchronized concurrent modification                   -------------- ---------------------------------------------------------------                                                                                           Implementation        buckets             Red-Black Tree        double-linked                                                                            buckets            -------------- ---------------------------------------------------------------           Is                                                                             synchronized                 implementation is not synchronized                   ------------------------------------------------------------------------------

User · Answer

All three represent mapping from unique keys to values  and therefore implement the Map interface    HashMap is a map based on hashing of the keys  It supports O 1  get put operations  Keys must have consistent implementations of hashCode   and equals   for this to work   LinkedHashMap is very similar to HashMap  but it adds awareness to the order at which items are added  or accessed   so the iteration order is the same as insertion order  or access order  depending on construction parameters   TreeMap is a tree based mapping  Its put get operations take O log n  time  It requires items to have some comparison mechanism  either with Comparable or Comparator  The iteration order is determined by this mechanism

User · Answer

Amit  SortedMap is an interface whereas TreeMap is a class which implements the SortedMap interface  That means if follows the protocol which SortedMap asks its implementers to do  A tree unless implemented as search tree  can t give you ordered data because tree can be any kind of tree  So to make TreeMap work like Sorted order  it implements SortedMap   e g  Binary Search Tree - BST  balanced BST like AVL and R-B Tree   even Ternary Search Tree - mostly used for iterative searches in ordered way     public class TreeMap lt K V gt  extends AbstractMap lt K V gt  implements SortedMap lt K V gt   Cloneable  Serializable   In NUT-SHELL HashMap   gives data in O 1    no ordering  TreeMap   gives data in O log N   base 2  with ordered keys  LinkedHashMap   is Hash table with linked list  think of indexed-SkipList  capability to store data in the way it gets inserted in the tree  Best suited to implement LRU   least recently used

User · Answer

Just some more input from my own experience with maps  on when I would use each one    HashMap - Most useful when looking for a best-performance  fast  implementation  TreeMap  SortedMap interface  - Most useful when I m concerned with being able to sort or iterate over the keys in a particular order that I define  LinkedHashMap - Combines advantages of guaranteed ordering from TreeMap without the increased cost of maintaining the TreeMap    It is almost as fast as the HashMap    In particular  the LinkedHashMap also provides a great starting point for creating a Cache object by overriding the removeEldestEntry   method   This lets you create a Cache object that can expire data using some criteria that you define

User · Answer

HashMap   It has pair values keys values  NO duplication key values unordered unsorted it allows one null key and more than one null values   HashTable   same as hash map it does not allows null keys and null values   LinkedHashMap   It is ordered version of map implementation Based on linked list and hashing data structures   TreeMap   Ordered and sortered version based on hashing data structures

User · Answer

The most important among all the three is how they save the order of the entries   HashMap - Does not save the order of the entries  eg    public static void main String   args           HashMap lt String Integer gt  hashMap   new HashMap lt  gt             hashMap put  First  1     First --- gt  1 is put first in the map         hashMap put  Second  2    Second --- gt  2 is put second in the map         hashMap put  Third  3      Third--- gt 3 is put third in the map         for Map Entry lt String Integer gt  entry   hashMap entrySet                          System out println entry getKey    --- gt   entry getValue                         LinkedHashMap   It save the order in which entries were made  eg   public static void main String   args           LinkedHashMap lt String Integer gt  linkedHashMap   new LinkedHashMap lt  gt             linkedHashMap put  First  1     First --- gt  1 is put first in the map         linkedHashMap put  Second  2    Second --- gt  2 is put second in the map         linkedHashMap put  Third  3      Third--- gt 3 is put third in the map         for Map Entry lt String Integer gt  entry   linkedHashMap entrySet                          System out println entry getKey    --- gt   entry getValue                         TreeMap   It saves the entries in ascending order of the keys  eg   public static void main String   args  throws IOException           TreeMap lt String Integer gt  treeMap   new TreeMap lt  gt             treeMap put  A  1     A--- gt  1 is put first in the map         treeMap put  C  2    C--- gt  2 is put second in the map         treeMap put  B  3     B--- gt 3 is put third in the map         for Map Entry lt String Integer gt  entry   treeMap entrySet                          System out println entry getKey    --- gt   entry getValue

[java] Difference between HashMap, LinkedHashMap and TreeMap

Examples related to java

Examples related to map