Difference between HashMap, LinkedHashMap and TreeMap

Upasana | December 04, 2019 | 2 min read | 403 views | algorithm-datastructures


All three classes (HashMap, TreeMap and LinkedHashMap) implements Map interface, and therefore represents mapping from unique key to values.

  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).

Property HashMap LinkedHashMap TreeMap

Time complexity (Big O) for get, put, containsKey and remove method

O(1)

O(1)

O(log n)

Null Keys

Allowed

Allowed

Not allowed if the key uses natural ordering or the comparator does not support comparison on null keys

Interface

Map

Map

Map, SortedMap and NavigableMap

Iteration order

Random order

Based on constructor - either insertion order or access order

Sorted - either on natural order of key or according to the comparator provided during construction

Data structure

List of buckets. If more than 8 entries in bucket, then linked list will convert to balanced tree

Doubly linked list of buckets

Red-black tree - a self balancing search tree, O(log n) for insert, delete and search operations)

Contract for Keys

must override equals() and hashcode()

must override equals() and hashcode()

key should implement comparator otherwise natural ordering will be used to sort the keys

Applications

General purpose with fast retrieval. ConcurrentHashMap can be used when concurrency is key requirement.

LRU cache, any other place where insertion or access order matters

Range Search, finding an employee whose salary is next to given employee. Algorithms where sorted or navigable features are required

Synchronization

none, use ConcurrentHashMap or Collections.synchronizedMap()

none

none


Top articles in this category:
  1. What is difference between HashMap and HashSet
  2. Difference between HashMap and ConcurrentHashMap
  3. Discuss internals of a ConcurrentHashmap (CHM) in Java
  4. Can the keys in HashMap be mutable
  5. What is difference between Vector and ArrayList, which one shall be preferred
  6. Difference between Callable and Runnable Interface
  7. How will you implement your custom threadsafe Semaphore in Java

Recommended books for interview preparation:

Find more on this topic: