Friday, 20 November 2015

HashMap Vs LinkedHashMap Vs TreeMap in Java

Though HashMap, LinkedHashMap and TreeMap all are implementation of the Map interface and share some traits like storing (key, value) pair, having a fail-fast iterator, not being synchronized but there are certain differences too related to how elements are ordered, performance etc. So it is very important to know these differences as it will help you to make an informed choice about which Map implementation should be used to meet the requirement.

Differences among HashMap, LinkedHashMap and TreeMap

  1. First and most important difference is related to Ordering of the elements.
    HashMap makes no guarantees as to the order of the map.
    LinkedHashMap maintains the insertion order of the elements which means if we iterate a LinkedHashMap we'll get the keys in the order in which they were inserted in the Map.
    TreeMap stores objects in sorted order. The elements are ordered using their natural ordering or a comparator can be provided at map creation time to provide custom ordering.
  2. Another difference is related to allowing null as key or value.
    HashMap as well as LinkedHashMap allows one null as key, multiple values may be null though.
    TreeMap does not allow null as key. Any attempt to add null in a TreeMap will result in a NullPointerException. Values may be null.
  3. For HashMap and LinkedHashMap comparison of the elements is done using equals() method.
    As Exp. In get method for the passed key k, if this map contains a mapping from a key k to a value v such that (key==null ? k==null : key.equals(k)), then this method returns v; otherwise it returns null.
    TreeMap does the comparison of the keys using the compareTo (or compare) method, depending on whether sorting is done using Comparable or Comparator.
    As Exp. In get method for the passed key k, if this map contains a mapping from a key k to a value v such that key compares equal to k according to the map's ordering, then this method returns v; otherwise it returns null.
  4. HashMap class extends AbstractMap and implements Map interface.
    LinkedHashMap class extends HashMap and implements Map interface.
    TreeMap class extends AbstractMap and implements NavigableMap interface.
  5. HashMap stores elements in a bucket which actually is an index of the array which means the backing data structure for the HashMap is an array where bucket0 means index[0], bucket1 means index[1] of that array.
    LinkedHashMap also uses the same internal implementation, it also maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering.
    TreeMap is a Red-Black tree based NavigableMap implementation.
  6. Performance wise HashMap provides constant time performance O(1) for get() and put() method but that is in the ideal case when the Hash function distributes the objects evenly among the buckets. In worst case when equals() and HashCode() implementation is not good it may even become O(n).
    LinkedHashMap also provides constant time performance O(1) for get() and put() method but in general a little slower than the HashMap as it has to maintain a doubly linked list.
    TreeMap provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.

That's all for this topic HashMap Vs LinkedHashMap Vs TreeMap in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. Difference between HashMap and HashTable in Java
  2. How to loop through a map in Java
  3. LinkedHashMap in Java
  4. Treemap in Java
  5. HashSet Vs LinkedHashSet Vs TreeSet in Java
  6. Java Collections interview questions

You may also like -

No comments:

Post a Comment