| Criteria | TreeMap | LinkedHashMap |
|---|---|---|
| Ordering | Sorted according to the natural ordering of its keys, or by a comparator provided at map creation time. | Insertion-order (default) or access-order defined by the last access. Not sorted by key values. |
| Performance | Logarithmic time cost for containsKey, get, put, and remove operations. | Constant time performance for common operations (get and put), but iteration depends on the capacity + size. |
| Internal Structure | Red-Black tree based NavigableMap. | Hash table + LinkedList; Entries are doubly-linked. |
| Use-case | When you need a map sorted by keys. | When you want to maintain the insertion order or access order of keys. |
| Null Keys/Values | Allows one null key (if using natural ordering) and multiple null values. Does not allow null keys if a custom comparator is used. | Allows one null key and multiple null values. |
| Thread Safety | No | No |
| Additional Features | Provides several methods like firstKey, lastKey, higherKey, etc. for navigational operations. | Provides predictable iteration order based on the order in which pairs are added to the map or accessed. |
Example: Difference Between TreeMap and LinkedHashMap in Java
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.TreeMap;
public class TreeMapVsLinkedHashMapDemo {
public static void main(String[] args) {
// Using a TreeMap
Map<String, String> treeMap = new TreeMap<>();
treeMap.put("apple", "red");
treeMap.put("banana", "yellow");
treeMap.put("cherry", "red");
// Using a LinkedHashMap
Map<String, String> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("banana", "yellow");
linkedHashMap.put("apple", "red");
linkedHashMap.put("cherry", "red");
System.out.println("TreeMap contents: " + treeMap);
System.out.println("LinkedHashMap contents: " + linkedHashMap);
}
}
Output:
TreeMap contents: {apple=red, banana=yellow, cherry=red}
LinkedHashMap contents: {banana=yellow, apple=red, cherry=red}
Explanation:
1. TreeMap: It is a Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a custom Comparator provided at map creation time. This means that the order in which keys are inserted does not matter, the map will always keep them in the sorted order.
2. LinkedHashMap: It is a hash table and linked list implementation of the Map interface, with predictable iteration order. This order is normally the order in which keys are inserted into the map (insertion-order). However, in case of access-order, the order changes when a key is accessed.
3. In the provided example:
– For TreeMap: Keys are added in a random order but when printed, they appear in their natural sorted order (alphabetically in this case).
– For LinkedHashMap: Keys are printed in the order they were inserted. First banana, then apple, and then cherry.
4. Use TreeMap when you need to maintain the entries in a sorted order. Use LinkedHashMap when you want to maintain the insertion order or access order of entries.