Describe a use case where `TreeMap`'s range query capabilities would be highly beneficial compared to using a `HashMap`.
Java interview question for Advanced practice.
Answer
A compelling use case for TreeMap is managing a time-series dataset where keys represent timestamps. For example, imagine storing stock prices or sensor readings where the key is a LocalDateTime object and the value is the price or reading. With a TreeMap, you can efficiently perform range queries that are difficult and inefficient with a HashMap. For example: Get all data within a specific time window: Using subMap(startTime, endTime) you can instantly get a view of all readings that occurred within a specific hour, day, or month. With a HashMap, you would have to iterate through the entire map and check each key individually, which is an $O(n)$ operation. Find the first reading after a specific time: ceilingEntry(timestamp) can find the next available data point after a system outage or a specific event. Find the last reading before a specific time: floorEntry(timestamp) can find the most recent data point before a given moment. In these scenarios, the $O(\log n)$ complexity of TreeMap's navigation methods provides a significant performance advantage over the $O(n)$ full scan required by HashMap.
Explanation
TreeMap implements the NavigableMap interface, which provides powerful methods like headMap, tailMap, subMap, ceilingKey, and floorKey for sophisticated navigation and range-based searches.