Difference between HashMap, LinkedHashMap and TreeMap in java

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 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 and Navigable interfaces.

SortedMap interface provides a total ordering of Map keys. The map is ordered according to the natural ordering of its keys, or by a Comparator typically provided at sorted map creation time. This order is reflected when iterating over the sorted map's collection views (returned by the entrySet, keySet and values methods). 

NavigableMap extends  SortedMap interface with navigation methods returning the closest matches for given search targets. Methods lowerEntry, floorEntry, ceilingEntry, and higherEntry return Map.Entryobjects associated with keys respectively less than, less than or equal, greater than or equal, and greater than a given key, returning null if there is no such key. Similarly, methods lowerKey,floorKey, ceilingKey, and higherKey return only the associated keys. All of these methods are designed for locating, not traversing entries.

LinkedHashMap will iterate in the order in which the entries were put into the map.This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). Note that insertion order is not affected if a key is re-inserted into the map.

LinkedHashMap has a constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). This kind of map is well-suited to building LRU caches.In addition to that LinkedHashMap provides a method removeEldestEntry(Map.Entry),can be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map.

See the example given below

import java.util.*;

public class Main {

public static void main(String args[]) {

HashMap<String,String> hashMap=new HashMap<String,String>();

LinkedHashMap<String,String> linkedMap=new LinkedHashMap<String,String>();

TreeMap<String,String> treeMap=new TreeMap<String,String>();

hashMap.put("Pakistan", "Islamabad");

hashMap.put("India", "Delhi");

hashMap.put("SriLanka","Colombo");

System.out.println("HashMap keySet :"+hashMap.keySet());

System.out.println("HashMap values :"+hashMap.values());

linkedMap.put("Pakistan", "Islamabad");

linkedMap.put("India", "Delhi");

linkedMap.put("SriLanka","Colombo");

System.out.println("LinkedHashMap keySet :"+linkedMap.keySet());

System.out.println("LinkedHashMap values :"+linkedMap.values());

treeMap.put("Pakistan", "Islamabad");

treeMap.put("India", "Delhi");

treeMap.put("SriLanka","Colombo");

System.out.println("TreeMap keySet :"+treeMap.keySet());

System.out.println("TreeMap values :"+treeMap.values());

}

}

The output is:

HashMap keySet :[Pakistan, SriLanka, India]

HashMap values :[Islamabad, Colombo, Delhi]

LinkedHashMap keySet :[Pakistan, India, SriLanka]

LinkedHashMap values :[Islamabad, Delhi, Colombo]

TreeMap keySet :[India, Pakistan, SriLanka]

TreeMap values :[Delhi, Islamabad, Colombo]

Performance Comparison

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 maintains a doubly-linked list running through all of its entries.Performance is likely to be just slightly below that of HashMap, due to the added expense of maintaining the linked list, with one exception: Iteration over the collection-views of a LinkedHashMap requires time proportional to the size of the map, regardless of its capacity. Iteration over a HashMap is likely to be more expensive, requiring time proportional to its capacity.


The TreeMap is implemented using the balanced binary tree and it has a predictable depth which is equal to log2(n) where 'n' is the number of nodes on the binary tree. In balanced binary tree, so the lookup would be O(log2n). If we have 1024 elements, it will take at most ten lookups.This is worst than a HashMap with an efficient hash function, which should only take one look-up.Keeping the tree balanced is expensive since it involves shuffling the nodes around whenever one side of the tree becomes too deep.So inserting an element into TreeMap is more expensive.

Conclusion


We can conclude the above discussion like this.Use TreeMap only when you need to iterate entries in sorted order.If you can satisfy with retrieving entries in the order of insertion, use LinkedHashMap.In all other scenarios use HashMap.Find the table given below

	Order of iteration	Performance put/get	Other features
HashMap	No order	O(1)
LinkedHashMap	Order in which entries where put into the map	O(1)+expense of maintaining linkedlist	Can be used as LRU Caches
TreeMap	Natural ordering or according to the provided Comparator.	O(log2n)