Tuesday, January 19, 2016

What is difference between HashMap, LinkedHashMap and TreeMap?

All three classes (HashMap, TreeMap and LinkedHashMap) implements Map interface, and therefore represents mapping from unique key to values. But there are different usage scenarios for each of them -

1. HashMap is a hashing data structure which works on hashcode of keys. Keys must provide consistent implementation of equals() and hashCode() method in order to work with hashmap. 

Time complexity for get() and put() operations is Big O(1).

2. LinkedHashMap is also a hashing data structure similar to HashMap, but it retains the original order of insertion for its elements using a LinkedList. Thus iteration order of its elements is same as the insertion order for LinkedHashMap which is not the case for other two Map classes. Iterating over its elements is lightly faster than the HashMap because it does not need to traverse over buckets which are empty.

LinkedHashMap also provides a great starting point for creating a LRU Cache object by overriding the removeEldestEntry() method, as shown in the following code snippet.

private static final int MAX_ENTRIES = 100;
protected boolean removeEldestEntry(Map.Entry eldest) {
    return size() > MAX_ENTRIES;
}

Time complexity for get() and put() operations is Big O(1).

3. TreeMap is a SortedMap, based on Red-Black Binary Search Tree which maintains order of its elements based on given comparator or comparable. 

Time complexity for put() and get() operation is O (log n).

No comments:

Post a Comment

Your comment will be published after review from moderator