HashMap Vs LinkedHashMap Vs TreeMap in Java

Though HashMap, LinkedHashMap and TreeMap all are implementations 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 among HashMap, LinkedHashMap and TreeMap in Java 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 in Java

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 or access order (based on the constructor) 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 or the order in which its entries were last accessed, from least-recently accessed to most-recently.
   TreeMap stores objects in sorted order. The elements in TreeMap are ordered according to the natural ordering of its keys or a Comparator can be provided at map creation time to provide custom ordering of its keys.

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 Example 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 Example 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.
   
   • Refer How HashMap internally works in Java to know more about the internal implementation of HashMap in Java.
   LinkedHashMap extends HashMap and uses the same internal implementation as HashMap. Apart from that 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!

>>>Return to Java Advanced Tutorial Page | Return to Java Collections Framework Tutorial Page>>>

---

Related Topics

1. Difference Between HashMap And Hashtable in Java
2. How to Loop Through a Map in Java
3. LinkedHashMap in Java With Examples
4. HashSet Vs LinkedHashSet Vs TreeSet in Java
5. Java Collections Interview Questions And Answers

You may also like-

1. How to Sort Elements in Different Order in TreeSet
2. How to Sort ArrayList of Custom Objects in Java
3. Deadlock in Java Multi-Threading
4. Difference Between sleep And wait in Java Multi-Threading
5. How to Fix The Target Type of This Expression Must be a Functional Interface Error
6. Java Pass by Value or Pass by Reference
7. Serialization Proxy Pattern in Java
8. Creating Custom Exception Class in Java