What is treemap in Java?
Understanding TreeMap in Java
\\n\\n
TreeMap is a Map implementation that stores key-value pairs in a sorted order. Unlike HashMap, which stores entries in no particular order, TreeMap maintains keys in sorted order according to their natural ordering or a custom Comparator. This sorted behavior makes TreeMap valuable for scenarios where you need to process keys in order or perform range queries.
\\n\\n
TreeMap is backed by a Red-Black tree data structure, a self-balancing binary search tree. This design ensures that operations like insertion, deletion, and lookup maintain O(log n) time complexity, making TreeMap a reliable choice when both sorting and reasonable performance matter.
\\n\\n
TreeMap vs HashMap vs LinkedHashMap
\\n\\n
Understanding the differences between these three Map implementations helps you choose the right one for your needs.
\\n\\n
HashMap stores key-value pairs with no guaranteed order. Entries appear in whatever order they end up in the internal hash table. Performance for put, get, and remove operations is O(1) on average, but you sacrifice ordering.
\\n\\n
HashMap map = new HashMap<>();\\nmap.put(3, "Three");\\nmap.put(1, "One");\\nmap.put(2, "Two");\\nSystem.out.println(map); // Output order is not guaranteed \\n\\n
LinkedHashMap maintains insertion order. Entries appear in the order they were added. This preserves predictability while keeping O(1) average performance for basic operations. However, entries are not sorted by key value.
\\n\\n
LinkedHashMap map = new LinkedHashMap<>();\\nmap.put(3, "Three");\\nmap.put(1, "One");\\nmap.put(2, "Two");\\nSystem.out.println(map); // Output: {3=Three, 1=One, 2=Two} (insertion order) \\n\\n
TreeMap sorts keys by their natural order or a custom Comparator. When you iterate or access entries, they appear in sorted order. Operations are O(log n) instead of O(1), but the sorting guarantee is valuable.
\\n\\n
TreeMap map = new TreeMap<>();\\nmap.put(3, "Three");\\nmap.put(1, "One");\\nmap.put(2, "Two");\\nSystem.out.println(map); // Output: {1=One, 2=Two, 3=Three} (sorted order) \\n\\n
Choose HashMap when insertion speed is critical and order does not matter. Choose LinkedHashMap when you need insertion order predictability. Choose TreeMap when sorted order or range operations are requirements.
\\n\\n
Creating a TreeMap
\\n\\n
Creating a TreeMap with natural ordering is straightforward. Keys must implement Comparable or you must provide a Comparator.
\\n\\n
TreeMap scores = new TreeMap<>();\\nscores.put("Alice", 95);\\nscores.put("Bob", 87);\\nscores.put("Charlie", 92);\\nSystem.out.println(scores); // Output: {Alice=95, Bob=87, Charlie=92} (alphabetically sorted) \\n\\n
For custom sorting order, pass a Comparator to the constructor. This example sorts in reverse alphabetical order:
\\n\\n
TreeMap scores = new TreeMap<>(Collections.reverseOrder());\\nscores.put("Alice", 95);\\nscores.put("Bob", 87);\\nscores.put("Charlie", 92);\\nSystem.out.println(scores); // Output: {Charlie=92, Bob=87, Alice=95} (reverse alphabetical) \\n\\n
You can also pass a custom Comparator for complex sorting logic:
\\n\\n
TreeMap scores = new TreeMap<>((a, b) -> b.compareTo(a));\\n// This is equivalent to Collections.reverseOrder() for String keys \\n\\n
Adding, Removing, and Getting Entries
\\n\\n
TreeMap provides the standard Map methods for manipulating entries.
\\n\\n
The put method adds or updates an entry:
\\n\\n
TreeMap map = new TreeMap<>();\\nmap.put("apple", 5);\\nmap.put("banana", 3);\\nmap.put("apple", 6); // Updates the value for "apple"\\nSystem.out.println(map.get("apple")); // Output: 6 \\n\\n
The get method retrieves a value by key:
\\n\\n
Integer value = map.get("banana");\\nSystem.out.println(value); // Output: 3\\n\\n
The remove method deletes an entry:
\\n\\n
map.remove("banana");\\nSystem.out.println(map.containsKey("banana")); // Output: false\\n\\n
The containsKey method checks existence without retrieving the value:
\\n\\n
if (map.containsKey("apple")) {\\n System.out.println("apple is in the map");\\n}\\n\\n
Natural Ordering vs Custom Comparator
\\n\\n
Natural ordering uses the key’s built-in Comparable implementation. Integer, String, Double, and other standard classes implement Comparable, so they work naturally in TreeMap.
\\n\\n
TreeMap map = new TreeMap<>();\\nmap.put(30, "Thirty");\\nmap.put(10, "Ten");\\nmap.put(20, "Twenty");\\nfor (Integer key : map.keySet()) {\\n System.out.println(key);\\n}\\n// Output:\\n// 10\\n// 20\\n// 30 \\n\\n
Custom Comparators let you define sorting rules for objects that do not implement Comparable or when you want non-standard ordering:
\\n\\n
class Person {\\n String name;\\n int age;\\n \\n Person(String name, int age) {\\n this.name = name;\\n this.age = age;\\n }\\n}\\n\\n// Sort Person objects by age\\nComparator byAge = (p1, p2) -> Integer.compare(p1.age, p2.age);\\nTreeMap map = new TreeMap<>(byAge);\\nmap.put(new Person("Alice", 30), "Engineer");\\nmap.put(new Person("Bob", 25), "Designer");\\n// Entries are sorted by age \\n\\n
TreeMap Methods for Sorted Navigation
\\n\\n
TreeMap provides specialized methods that take advantage of its sorted nature.
\\n\\n
The firstKey and lastKey methods return the smallest and largest keys:
\\n\\n
TreeMap map = new TreeMap<>();\\nmap.put(30, "Thirty");\\nmap.put(10, "Ten");\\nmap.put(20, "Twenty");\\nSystem.out.println(map.firstKey()); // Output: 10\\nSystem.out.println(map.lastKey()); // Output: 30 \\n\\n
The headMap method returns a view of all entries with keys less than a specified key:
\\n\\n
SortedMap head = map.headMap(25);\\nSystem.out.println(head); // Output: {10=Ten, 20=Twenty} \\n\\n
The tailMap method returns a view of all entries with keys greater than or equal to a specified key:
\\n\\n
SortedMap tail = map.tailMap(20);\\nSystem.out.println(tail); // Output: {20=Twenty, 30=Thirty} \\n\\n
The subMap method returns entries within a range:
\\n\\n
SortedMap sub = map.subMap(15, 30);\\nSystem.out.println(sub); // Output: {20=Twenty} (15 inclusive, 30 exclusive) \\n\\n
The floorKey method returns the largest key less than or equal to the specified key:
\\n\\n
System.out.println(map.floorKey(25)); // Output: 20\\n\\n
The ceilingKey method returns the smallest key greater than or equal to the specified key:
\\n\\n
System.out.println(map.ceilingKey(25)); // Output: 30\\n\\n
The descendingMap method provides a reverse-sorted view of the entries:
\\n\\n
NavigableMap desc = map.descendingMap();\\nfor (Integer key : desc.keySet()) {\\n System.out.println(key);\\n}\\n// Output:\\n// 30\\n// 20\\n// 10 \\n\\n
Iterating Over a TreeMap
\\n\\n
You can iterate over TreeMap entries, keys, or values in sorted order.
\\n\\n
Iterating over entries using entrySet is the most efficient approach:
\\n\\n
TreeMap map = new TreeMap<>();\\nmap.put("apple", 5);\\nmap.put("banana", 3);\\nmap.put("cherry", 8);\\n\\nfor (Map.Entry entry : map.entrySet()) {\\n System.out.println(entry.getKey() + " -> " + entry.getValue());\\n}\\n// Output:\\n// apple -> 5\\n// banana -> 3\\n// cherry -> 8 \\n\\n
Iterating over keys only:
\\n\\n
for (String key : map.keySet()) {\\n System.out.println(key);\\n}\\n// Output: apple, banana, cherry (sorted)\\n\\n
Iterating over values only:
\\n\\n
for (Integer value : map.values()) {\\n System.out.println(value);\\n}\\n// Output: 5, 3, 8\\n\\n
Using an Iterator provides fine-grained control and allows removal during iteration:
\\n\\n
Iterator> it = map.entrySet().iterator();\\nwhile (it.hasNext()) {\\n Map.Entry entry = it.next();\\n System.out.println(entry.getKey() + " -> " + entry.getValue());\\n} \\n\\n
TreeMap Performance Characteristics
\\n\\n
Understanding TreeMap performance helps you make informed design decisions.
\\n\\n
Put, get, and remove operations have O(log n) time complexity. This is slower than HashMap’s O(1) average case but faster than a linear search would be.
\\n\\n
// Adding 1,000,000 entries\\nTreeMap map = new TreeMap<>();\\nlong start = System.currentTimeMillis();\\nfor (int i = 0; i < 1_000_000; i++) {\\n map.put(i, "value" + i);\\n}\\nlong end = System.currentTimeMillis();\\nSystem.out.println("Time: " + (end - start) + " ms"); // Slower than HashMap but acceptable \\n\\n
Range operations like headMap, tailMap, and subMap are very efficient because TreeMap's structure supports them naturally. These operations take O(log n) time plus the size of the result set.
\\n\\n
Space complexity is O(n) for storing n entries, similar to all Map implementations.
\\n\\n
When to Use TreeMap
\\n\\n
Use TreeMap when sorted order is a core requirement. If you need to process entries in key order, range queries, or frequency find minimum/maximum operations, TreeMap is the right choice.
\\n\\n
For example, in a log analysis application, you might use TreeMap with timestamps as keys to automatically keep logs in chronological order.
\\n\\n
Do not use TreeMap when insertion speed is critical and you have no need for sorted order. In those cases, HashMap is significantly faster.
\\n\\n
TreeMap works particularly well when combined with Java's collection framework. Understanding TreeMap alongside other implementations like UUID generation and object construction gives you complete mastery of Java data structures.
\\n\\n
TreeMap with Custom Objects as Keys
\\n\\n
When using custom objects as TreeMap keys, those objects must implement Comparable or you must provide a Comparator.
\\n\\n
class Book implements Comparable {\\n String title;\\n int year;\\n \\n Book(String title, int year) {\\n this.title = title;\\n this.year = year;\\n }\\n \\n @Override\\n public int compareTo(Book other) {\\n return Integer.compare(this.year, other.year);\\n }\\n}\\n\\nTreeMap library = new TreeMap<>();\\nlibrary.put(new Book("1984", 1949), "Dystopian");\\nlibrary.put(new Book("Brave New World", 1932), "Science Fiction");\\n// Entries sorted by publication year \\n\\n
TreeMap vs TreeSet
\\n\\n
TreeSet stores only unique values and maintains sorted order, while TreeMap stores key-value pairs. If you need just values without keys, TreeSet is more appropriate. Both use Red-Black trees internally and have similar performance characteristics.
\\n\\n
Leave a Reply