private static final int MAX_ENTRIES = 100;
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
}
Difference between HashMap, LinkedHashMap and TreeMap
Carvia Tech  December 04, 2019  2 min read  6 views  algorithmdatastructures
All three classes (HashMap, TreeMap and LinkedHashMap) implements Map interface, and therefore represents mapping from unique key to values.

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

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.
Time complexity for get() and put() operations is Big O(1).

TreeMap is a SortedMap, based on RedBlack 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 
Redblack 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:
 What is difference between HashMap and HashSet
 Difference between HashMap and ConcurrentHashMap
 What is difference between Callable and Runnable Interface?
 What is difference between Vector and ArrayList, which one shall be preferred
 Difference between Comparable and Comparator in Java
 Can the keys in HashMap be mutable
 What is difference between JDK JRE and JVM
Find more on this topic:
Core Java
Core Java  OOP Concepts, Garbage Collection, Multithreading, Collections Framework, Java 8 Features, Lambda Functions, Streams.
Last updated 1 week ago
Recommended books for interview preparation:
Similar Posts
 Explain Java Exception Class Hierarchy
 Http download using Java NIO FileChannel
 CRC32 checksum calculation Java NIO
 Set precision and scale for a double value in java
 Difference between HashMap, LinkedHashMap and TreeMap
 What is difference between ExecutorService submit and execute method
 What is left shift right shift and unsigned rght shift operator in Java
 What happens when wait() & notify() method are called
 can we write a java method that swaps two integers
 Find missing numbers in 4 billion unique numbers with 50MB RAM
Enter your email address to subscribe to this blog and receive notifications of new posts by email.