Difference between HashMap, LinkedHashMap and TreeMap

Carvia Tech | December 04, 2019 | 2 min read | 299 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(log n)

Null Keys



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




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


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


none, use ConcurrentHashMap or Collections.synchronizedMap()



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

Find more on this topic:
Core Java image
Core Java

Core Java - OOP Concepts, Garbage Collection, Multi-threading, Collections Framework, Java 8 Features, Lambda Functions, Streams.

Last updated 1 week ago

Recommended books for interview preparation:

This website uses cookies to ensure you get the best experience on our website. more info