TreeMap in Java: A Must-Know Data Structure

15 Jul, 2024

TreeMap is a powerful and versatile data structure in Java that implements the NavigableMap interface. It is part of the Java Collections Framework and provides an efficient way to store key-value pairs in a sorted order. In this article, we'll explore the concept of TreeMap, its features, main methods, and provide practical examples to demonstrate its usage.

What is TreeMap?

TreeMap is a Red-Black tree-based implementation of the NavigableMap interface. It stores key-value pairs in a sorted order based on the natural ordering of its keys or a custom Comparator provided at the time of creation. The main characteristics of TreeMap include:

1. Sorted Order: Keys are always maintained in a sorted order.
2. No Null Keys: TreeMap does not allow null keys (although null values are permitted).
3. Non-synchronized: TreeMap is not thread-safe by default.
4. Performance: Operations like get(), put(), remove(), and containsKey() have a time complexity of O(log n).

Main differences vs HashMap

HashMap and TreeMap are both implementations of the Map interface in Java, but they have distinct characteristics that make them suitable for different scenarios. Here's a comprehensive comparison of HashMap and TreeMap:

1. Ordering:

   • HashMap: Does not maintain any order of its elements.
   • TreeMap: Maintains its elements in sorted order based on the natural ordering of its keys or a custom Comparator.

2. Performance:

   • HashMap: Offers O(1) time complexity for basic operations (get, put, remove) on average.
   • TreeMap: Offers O(log n) time complexity for basic operations.

3. Null keys and values:

   • HashMap: Allows one null key and multiple null values.
   • TreeMap: Does not allow null keys (throws NullPointerException) but permits null values.

4. Implementation:

   • HashMap: Implemented as a hash table.
   • TreeMap: Implemented as a Red-Black tree.

5. Memory usage:

   • HashMap: Generally uses less memory.
   • TreeMap: Typically requires more memory due to the overhead of maintaining the tree structure.

6. Iteration order:

   • HashMap: No guaranteed order when iterating.
   • TreeMap: Iterates in the sorted order of keys.

7. Range operations:

   • HashMap: Does not support range operations efficiently.
   • TreeMap: Supports efficient range operations (e.g., subMap, headMap, tailMap).

8. Collision handling:

   • HashMap: Uses separate chaining with linked lists or trees (in Java 8+) to handle collisions.
   • TreeMap: Doesn't need collision handling as it uses a tree structure.

9. Key requirements:

   • HashMap: Keys must implement hashCode() and equals() methods.
   • TreeMap: Keys must be comparable (implement Comparable) or a custom Comparator must be provided.

Pay extra attention to the compareTo implementation, because TreeMap considers two keys equal if they compareTo method returns 0, even if equals return false. You can read more about how to implement correctly the Comparable interface in my article Java Comparable compareTo method: Natural Order Of Things.

10. Use cases:

    • HashMap: Best for scenarios where fast insertion, deletion, and retrieval are prioritized.
    • TreeMap: Ideal when sorted order is required or when range-based operations are frequent.

11. Customization:

    • HashMap: Allows customization of initial capacity and load factor.
    • TreeMap: Allows customization of the comparison method through a Comparator.

12. Predictability:

    • HashMap: Performance can degrade if many keys have the same hash code.
    • TreeMap: Performance is more consistent and predictable.

13. Navigation methods:

    • HashMap: Does not provide navigation methods.
    • TreeMap: Offers methods like lowerKey, higherKey, floorKey, ceilingKey for navigating the structure.

14. Thread safety:

    • Both HashMap and TreeMap are not thread-safe by default.
    • Use Collections.synchronizedMap() or ConcurrentHashMap for thread-safe operations with HashMap.
    • Use Collections.synchronizedSortedMap() for thread-safe operations with TreeMap.

When to choose HashMap:

• When you need the fastest possible insertion, deletion, and lookup operations.
• When you don't need ordered data.
• When your keys have good hash functions to minimize collisions.

When to choose TreeMap:

• When you need to maintain data in sorted order.
• When you frequently perform range-based operations.
• When you need to find the closest matches (floor, ceiling, etc.) for given keys.
• When predictable performance is more important than fastest average performance.

Like the article? Support me by subscribing to the blog

Creating a TreeMap

To create a TreeMap, you can use one of the following constructors:

// Default constructor
TreeMap<K, V> treeMap = new TreeMap<>();

// Constructor with a custom Comparator
TreeMap<K, V> treeMap = new TreeMap<>(Comparator<? super K> comparator);

// Constructor with an existing SortedMap
TreeMap<K, V> treeMap = new TreeMap<>(SortedMap<K, ? extends V> m);

// Constructor with an existing Map
TreeMap<K, V> treeMap = new TreeMap<>(Map<? extends K, ? extends V> m);

// Custom Comparator for sorting strings by length
Comparator<String> lengthComparator = Comparator.comparingInt(String::length);
TreeMap<String, Integer> treeMap = new TreeMap<>(lengthComparator);

Or starting from Java 9 you can create an unmodifiable TreeMap like this:

TreeMap<String, Integer> smallMap = new TreeMap<>(Map.of("A", 1, "B", 2, "C", 3));

Main Methods of TreeMap

Let's explore the main methods of TreeMap with examples using an event logging system:

TreeMap<LocalDateTime, String> eventLog = new TreeMap<>();

put(K key, V value)

This method is used to insert a key-value pair into the TreeMap.

eventLog.put(LocalDateTime.of(2023, 5, 1, 10, 0), "System startup");
eventLog.put(LocalDateTime.of(2023, 5, 1, 10, 15), "User login: Alice");
eventLog.put(LocalDateTime.of(2023, 5, 1, 10, 30), "Database backup initiated");

get(Object key)

This method retrieves the value associated with the specified key.

String event = eventLog.get(LocalDateTime.of(2023, 5, 1, 10, 15)); // Returns "User login: Alice"

remove(Object key)

This method removes the mapping for the specified key from the TreeMap.

eventLog.remove(LocalDateTime.of(2023, 5, 1, 10, 30)); // Removes the database backup event

containsKey(Object key) and containsValue(Object value)

These methods check if the TreeMap contains a specific key or value.

boolean hasEvent = eventLog.containsKey(LocalDateTime.of(2023, 5, 1, 10, 0)); // Returns true
boolean hasLoginEvent = eventLog.containsValue("User login: Alice"); // Returns true

firstKey() and lastKey()

These methods return the first (earliest) and last (latest) keys in the TreeMap.

LocalDateTime earliestEvent = eventLog.firstKey(); // Returns 2023-05-01T10:00
LocalDateTime latestEvent = eventLog.lastKey(); // Returns 2023-05-01T10:15

headMap(K toKey), tailMap(K fromKey), and subMap(K fromKey, K toKey)

These methods return views of portions of the TreeMap.

LocalDateTime cutoff = LocalDateTime.of(2023, 5, 1, 10, 10);
SortedMap<LocalDateTime, String> earlierEvents = eventLog.headMap(cutoff);
SortedMap<LocalDateTime, String> laterEvents = eventLog.tailMap(cutoff);
SortedMap<LocalDateTime, String> eventsBetween = eventLog.subMap(
    LocalDateTime.of(2023, 5, 1, 10, 5),
    LocalDateTime.of(2023, 5, 1, 10, 20)
);

ceilingEntry(K key) and floorEntry(K key)

These methods return the entry with the least key greater than or equal to the given key (ceiling) or the greatest key less than or equal to the given key (floor).

LocalDateTime searchTime = LocalDateTime.of(2023, 5, 1, 10, 10);
Map.Entry<LocalDateTime, String> nextEvent = eventLog.ceilingEntry(searchTime); // Returns entry for 10:15
Map.Entry<LocalDateTime, String> previousEvent = eventLog.floorEntry(searchTime); // Returns entry for 10:00

higherEntry(K key) and lowerEntry(K key)

These methods return the entry with the least key strictly greater than the given key (higher) or the greatest key strictly less than the given key (lower).

LocalDateTime searchTime = LocalDateTime.of(2023, 5, 1, 10, 0);
Map.Entry<LocalDateTime, String> nextEvent = eventLog.higherEntry(searchTime); // Returns entry for 10:15
Map.Entry<LocalDateTime, String> previousEvent = eventLog.lowerEntry(searchTime); // Returns null (no earlier event)

pollFirstEntry() and pollLastEntry()

These methods remove and return the first (earliest) or last (latest) entry in the TreeMap.

Map.Entry<LocalDateTime, String> earliestEvent = eventLog.pollFirstEntry(); // Removes and returns entry for 10:00
Map.Entry<LocalDateTime, String> latestEvent = eventLog.pollLastEntry(); // Removes and returns entry for 10:15

descendingMap()

This method returns a reverse order view of the mappings in the TreeMap.

NavigableMap<LocalDateTime, String> reverseEventLog = eventLog.descendingMap();

floorKey()

The floorKey(K key) method returns the largest key in the TreeMap that is less than or equal to the given key. If there is no such key, it returns null.

LocalDateTime searchTime = LocalDateTime.of(2023, 5, 1, 10, 20);
LocalDateTime floorKey = eventLog.floorKey(searchTime); // Returns 2023-05-01T10:15

This example demonstrates how TreeMap can be effectively used for maintaining a chronological event log. The timestamp acts as the key, maintaining a natural ascending order, while the value is the event description. This structure allows for efficient operations like finding all events within a certain time range, identifying the earliest and latest events, or adding new events in the correct chronological order.

Some advantages of using TreeMap for an event log include:

• Automatic chronological sorting of events.
• Efficient lookup of events by timestamp
• Simple to add new events while maintaining the chronological order.
• Efficient range queries: Methods like tailMap(), headMap(), and subMap() operate in O(log n) time, making it very efficient to select a range of values.

TreeMap Time Complexity

Basic Operations:

• put(K key, V value): O(log n)
• get(Object key): O(log n)
• remove(Object key): O(log n)
• containsKey(Object key): O(log n)
• containsValue(Object value): O(n) — This is because you might need to scan through all entries to find the value.
• size(): O(1)
• clear(): O(n) — Removing all entries requires iterating through them.
• isEmpty(): O(1)

Navigation Operations:

• firstKey(): O(log n)
• lastKey(): O(log n)
• higherKey(K key): O(log n)
• lowerKey(K key): O(log n)
• ceilingKey(K key): O(log n)
• floorKey(K key): O(log n)
• firstEntry(): O(log n)
• lastEntry(): O(log n)
• higherEntry(K key): O(log n)
• lowerEntry(K key): O(log n)
• ceilingEntry(K key): O(log n)
• floorEntry(K key): O(log n)

View Operations:

• headMap(K toKey): O(log n)
• tailMap(K fromKey): O(log n)
• subMap(K fromKey, K toKey): O(log n)
• headMap(K toKey, boolean inclusive): O(log n)
• tailMap(K fromKey, boolean inclusive): O(log n)
• subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive): O(log n)
• descendingMap(): O(1) — The reverse view can be obtained in constant time.
• navigableKeySet(): O(1)
• descendingKeySet(): O(1)

Bulk Operations:

• putAll(Map<? extends K, ? extends V> map): O(n log n) — Adding n elements requires n operations, each taking O(log n) time.
• clone(): O(n) — Cloning involves copying all entries.

Collection View Operations:

• keySet(): O(1)
• values(): O(1)
• entrySet(): O(1)

Removal Operations:

• pollFirstEntry(): O(log n)
• pollLastEntry(): O(log n)

Comparison and Hashing:

• comparator(): O(1)
• equals(Object o): O(n) — Checking equality involves comparing all entries.
• hashCode(): O(n) — Computing the hash code requires visiting all entries.

Utility Methods:

• replace(K key, V value): O(log n)
• replace(K key, V oldValue, V newValue): O(log n)
• putIfAbsent(K key, V value): O(log n)
• compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction): O(log n)
• computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction): O(log n)
• computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction): O(log n)
• merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction): O(log n)

Iteration:

• forEach(BiConsumer<? super K, ? super V> action): O(n) — Iterating through all entries involves visiting each one.

Note:

• n represents the number of elements in the TreeMap.
• The time complexities are average-case scenarios. In the worst case, some operations might take up to O(n) time if the tree becomes unbalanced, but TreeMap uses Red-Black tree implementation which ensures that the tree remains balanced after insertions and deletions.
• Space complexity for TreeMap is O(n) for all operations.

Applicability

TreeMap is particularly useful in scenarios where you need to maintain sorted key-value pairs and perform range-based operations efficiently. Here are some common applications:

Event Logging and Analysis

• Storing system events with timestamps as keys and event descriptions as values.
• Efficiently retrieving events within specific time ranges.
• Analyzing the sequence of events in chronological order.

Financial Applications

• Storing financial transactions with unique transaction IDs as keys and transaction details as values.
• Maintaining a history of asset prices with timestamps as keys and price information as values.
• Easily accessing price data for specific time periods or ranges.
• Managing scheduled price changes with effective dates as keys and new price information as values.

Scheduling and Appointment Systems

• Using time slots as keys and appointment details as values.
• Quickly finding available time slots or checking for conflicts.

Version Control Systems

• Storing code revisions with version numbers or timestamps as keys and change details as values.
• Efficiently retrieving the state of the code at any given point in time.

Caching with Expiration

• Implementing a cache with expiration times as keys and cached data as values.
• Easily removing expired entries and retrieving valid cached data.

Leaderboards and Rankings

• Maintaining a sorted list of scores or rankings with score as the key and player information as the value.
• Efficiently updating and retrieving top N players or finding a player's rank.

Dictionary and Spell Checking

• Storing words as keys and their definitions or usage information as values.
• Quickly finding words and performing prefix-based searches.

Conclusion

TreeMap is a versatile and efficient data structure in Java that provides sorted key-value pair storage. Its implementation as a Red-Black tree ensures good performance for most operations. The main advantages of using TreeMap include:

1. Automatic sorting of keys
2. Efficient searching, insertion, and deletion operations
3. Support for range-based operations

However, it's important to note that TreeMap may not be the best choice in all scenarios. For example, if you don't need sorted keys or if you're working with a large number of elements and don't require sorting, other Map implementations like HashMap might be more suitable.

When working with TreeMap, keep in mind the following best practices:

1. Choose appropriate keys: Ensure that the keys you use have a natural ordering or provide a custom Comparator.
2. Be cautious with null keys: TreeMap doesn't allow null keys, so handle this case in your code.
3. Consider thread safety: If you need thread-safe operations, use Collections.synchronizedSortedMap() to wrap your TreeMap or consider using ConcurrentSkipListMap for better concurrency.
4. Use the NavigableMap methods: Take advantage of the powerful navigation methods provided by the NavigableMap interface for more complex operations.

By understanding the features and methods of TreeMap, you can effectively utilize this data structure in your Java applications to manage sorted key-value pairs and perform efficient range-based operations.

#java #treemap