TreeMap is a Red-Black tree-based NavigableMap implementation in Java. It’s part of the Java Collections Framework, located in the java.util package.
Key Points:
Ordering: The elements in a TreeMap are always in sorted order. By default, it’s in natural order, but a custom order can be provided using a comparator.
Null Key: TreeMap doesn’t allow null keys but allows multiple null values. However, it can have a null comparator.
Performance: Provides guaranteed log(n) time cost for the get, put, and remove operations.
Not Thread-Safe: TreeMap isn’t synchronized. If multiple threads access a map concurrently and at least one of the threads modifies it, it must be synchronized externally.
Create a TreeMap and Add New Elements
import java.util.TreeMap;
public class TreeMapExample {
public static void main(String[] args) {
// Creating a TreeMap of fruits and their prices
TreeMap<String, Double> fruitPrices = new TreeMap<>();
// Adding fruits and their prices to the TreeMap
fruitPrices.put("Apple", 0.55);
fruitPrices.put("Banana", 0.35);
fruitPrices.put("Cherry", 0.75);
fruitPrices.put("Date", 1.10);
// Displaying the contents of the TreeMap
System.out.println("Fruit Prices:");
fruitPrices.forEach((fruit, price) -> System.out.println(fruit + ": $" + price));
}
}
Output:
Fruit Prices: Apple: $0.55 Banana: $0.35 Cherry: $0.75 Date: $1.10
Explanation:
1. A TreeMap named fruitPrices is created to store fruit names as keys and their prices as values.
2. Four fruit-price pairs are added to the TreeMap.
3. As TreeMap stores its keys in natural ordering, when displayed, the fruit names appear in alphabetical order.
4. The forEach method is used to iterate over the TreeMap and print each fruit and its associated price.
Create a TreeMap with a Custom Comparator (Descending Order of Keys)
import java.util.Comparator;
import java.util.TreeMap;
public class TreeMapDescendingOrder {
public static void main(String[] args) {
// Creating a TreeMap with a custom comparator to sort keys in descending order
TreeMap<String, Double> fruitPrices = new TreeMap<>(Comparator.reverseOrder());
// Adding fruits and their prices to the TreeMap
fruitPrices.put("Apple", 0.55);
fruitPrices.put("Banana", 0.35);
fruitPrices.put("Cherry", 0.75);
fruitPrices.put("Date", 1.10);
// Displaying the contents of the TreeMap
System.out.println("Fruit Prices (Descending Order):");
fruitPrices.forEach((fruit, price) -> System.out.println(fruit + ": $" + price));
}
}
Output:
Fruit Prices (Descending Order): Date: $1.10 Cherry: $0.75 Banana: $0.35 Apple: $0.55
Explanation:
1. A custom Comparator is provided to the TreeMap using Comparator.reverseOrder(). This ensures the TreeMap will store its keys in descending order.
2. Four fruit-price pairs are added to the TreeMap.
3. The forEach method is used to iterate over the TreeMap and print each fruit and its associated price. Due to the custom Comparator, the fruits are displayed in descending alphabetical order.
Access Entries in a TreeMap
import java.util.TreeMap;
public class TreeMapAccessExample {
public static void main(String[] args) {
// Create and populate a TreeMap
TreeMap<String, Double> fruitPrices = new TreeMap<>();
fruitPrices.put("Apple", 0.55);
fruitPrices.put("Banana", 0.35);
fruitPrices.put("Cherry", 0.75);
fruitPrices.put("Date", 1.10);
// Find the size of the TreeMap
System.out.println("Size of the TreeMap: " + fruitPrices.size());
// Check if a given key exists in the TreeMap
System.out.println("Does the TreeMap contain 'Apple'?: " + fruitPrices.containsKey("Apple"));
System.out.println("Does the TreeMap contain 'Grape'?: " + fruitPrices.containsKey("Grape"));
// Retrieve the first entry in the TreeMap
System.out.println("First entry: " + fruitPrices.firstEntry());
// Retrieve the last entry in the TreeMap
System.out.println("Last entry: " + fruitPrices.lastEntry());
// Retrieve the entry whose key is just lower than the given key
System.out.println("Entry lower than 'Cherry': " + fruitPrices.lowerEntry("Cherry"));
// Retrieve the entry whose key is just higher than the given key
System.out.println("Entry higher than 'Banana': " + fruitPrices.higherEntry("Banana"));
}
}
Output:
Size of the TreeMap: 4 Does the TreeMap contain 'Apple'?: true Does the TreeMap contain 'Grape'?: false First entry: Apple=0.55 Last entry: Date=1.10 Entry lower than 'Cherry': Banana=0.35 Entry higher than 'Banana': Cherry=0.75
Explanation:
1. A TreeMap named fruitPrices is created and populated with four fruit-price pairs.
2. The size() method is called on the TreeMap to get its size.
3. The containsKey() method checks the presence of the specified keys in the TreeMap.
4. firstEntry() and lastEntry() methods are used to fetch the first and last entries respectively.
5. The lowerEntry() method retrieves the entry with the greatest key less than the given key.
6. The higherEntry() method retrieves the entry with the smallest key greater than the given key.
Remove Entries from a TreeMap
import java.util.TreeMap;
public class TreeMapRemovalExample {
public static void main(String[] args) {
// Create and populate a TreeMap
TreeMap<String, Double> fruitPrices = new TreeMap<>();
fruitPrices.put("Apple", 0.55);
fruitPrices.put("Banana", 0.35);
fruitPrices.put("Cherry", 0.75);
fruitPrices.put("Date", 1.10);
System.out.println("Original TreeMap: " + fruitPrices);
// Remove a key from the TreeMap
fruitPrices.remove("Banana");
System.out.println("After removing 'Banana': " + fruitPrices);
// Remove a key from the TreeMap only if it is associated with a given value
fruitPrices.remove("Cherry", 0.80); // Won't remove since value doesn't match
System.out.println("Trying to remove 'Cherry' with wrong price: " + fruitPrices);
fruitPrices.remove("Cherry", 0.75); // Will remove since value matches
System.out.println("After removing 'Cherry' with correct price: " + fruitPrices);
// Remove the first entry of the TreeMap
fruitPrices.pollFirstEntry();
System.out.println("After removing the first entry: " + fruitPrices);
// Remove the last entry of the TreeMap
fruitPrices.pollLastEntry();
System.out.println("After removing the last entry: " + fruitPrices);
}
}
Output:
Original TreeMap: {Apple=0.55, Banana=0.35, Cherry=0.75, Date=1.10}
After removing 'Banana': {Apple=0.55, Cherry=0.75, Date=1.10}
Trying to remove 'Cherry' with wrong price: {Apple=0.55, Cherry=0.75, Date=1.10}
After removing 'Cherry' with correct price: {Apple=0.55, Date=1.10}
After removing the first entry: {Date=1.10}
After removing the last entry: {}
Explanation:
1. A TreeMap named fruitPrices is created and populated with four fruit-price pairs.
2. The remove(Object key) method is used to remove a specified key-value pair from the TreeMap.
3. The remove(Object key, Object value) method checks both the key and the value before removing an entry.
4. The pollFirstEntry() method is called to remove and return the first (lowest) key-value pair.
5. The pollLastEntry() method removes and returns the last (highest) key-value pair.
Iterate Over a TreeMap – Different Ways
import java.util.TreeMap;
import java.util.Map;
public class TreeMapIterationExample {
public static void main(String[] args) {
// Create and populate a TreeMap
TreeMap<String, Double> fruitPrices = new TreeMap<>();
fruitPrices.put("Apple", 0.55);
fruitPrices.put("Banana", 0.35);
fruitPrices.put("Cherry", 0.75);
System.out.println("Original TreeMap: " + fruitPrices);
// 1. Iterate over a TreeMap using Java 8 forEach and lambda expression
System.out.println("\nUsing Java 8 forEach and lambda:");
fruitPrices.forEach((fruit, price) -> {
System.out.println(fruit + " costs " + price + " per piece.");
});
// 2. Iterate over a TreeMap’s entrySet using Java 8 forEach and lambda expression
System.out.println("\nUsing entrySet with Java 8 forEach and lambda:");
fruitPrices.entrySet().forEach(entry -> {
System.out.println(entry.getKey() + " costs " + entry.getValue() + " per piece.");
});
// 3. Iterate over a TreeMap’s entrySet using iterator()
System.out.println("\nUsing iterator over entrySet:");
for (Map.Entry<String, Double> entry : fruitPrices.entrySet()) {
System.out.println(entry.getKey() + " costs " + entry.getValue() + " per piece.");
}
// 4. Iterate over a TreeMap’s entrySet using iterator() and Java 8 forEachRemaining() method
System.out.println("\nUsing iterator with forEachRemaining:");
fruitPrices.entrySet().iterator().forEachRemaining(entry -> {
System.out.println(entry.getKey() + " costs " + entry.getValue() + " per piece.");
});
}
}
Output:
Original TreeMap: {Apple=0.55, Banana=0.35, Cherry=0.75}
Using Java 8 forEach and lambda:
Apple costs 0.55 per piece.
Banana costs 0.35 per piece.
Cherry costs 0.75 per piece.
Using entrySet with Java 8 forEach and lambda:
Apple costs 0.55 per piece.
Banana costs 0.35 per piece.
Cherry costs 0.75 per piece.
Using iterator over entrySet:
Apple costs 0.55 per piece.
Banana costs 0.35 per piece.
Cherry costs 0.75 per piece.
Using iterator with forEachRemaining:
Apple costs 0.55 per piece.
Banana costs 0.35 per piece.
Cherry costs 0.75 per piece.
Explanation:
1. A TreeMap named fruitPrices is created and populated with three fruit-price pairs.
2. The Java 8 forEach method is used with a lambda expression to iterate over the TreeMap and print its contents.
3. The entrySet() method returns a set of the map's entries, which is then iterated over using Java 8 forEach and a lambda expression.
4. The entrySet() is again used, but this time with an enhanced for-loop to iterate over and print the entries.
5. Lastly, the entrySet().iterator() method is combined with Java 8's forEachRemaining to loop through the map's entries.
Synchronize Access to TreeMap – Different Ways
import java.util.Collections;
import java.util.Map;
import java.util.TreeMap;
public class TreeMapSynchronizationExample {
public static void main(String[] args) {
// 1. Create a non-synchronized TreeMap
TreeMap<String, Integer> scoreMap = new TreeMap<>();
scoreMap.put("John", 85);
scoreMap.put("Anna", 90);
scoreMap.put("Mike", 75);
System.out.println("Original TreeMap: " + scoreMap);
// 2. Synchronize access to TreeMap using Collections.synchronizedSortedMap
Map<String, Integer> synchronizedScoreMap = Collections.synchronizedSortedMap(scoreMap);
// To show that it's synchronized, we'll use a simple thread to add an entry
Thread thread = new Thread(() -> {
synchronized (synchronizedScoreMap) {
synchronizedScoreMap.put("Derek", 88);
}
});
thread.start();
try {
thread.join(); // Wait for thread to complete
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("Synchronized TreeMap after thread execution: " + synchronizedScoreMap);
}
}
Output:
Original TreeMap: {Anna=90, John=85, Mike=75}
Synchronized TreeMap after thread execution: {Anna=90, Derek=88, John=85, Mike=75}
Explanation:
1. A non-synchronized TreeMap named scoreMap is created and populated with three student-score pairs.
2. Collections.synchronizedSortedMap is used to get a synchronized version of the TreeMap.
3. To demonstrate that the map is now synchronized, a new thread is used to add an entry to the synchronized map. The synchronized block ensures that the map remains thread-safe during the modification.
4. The thread.join() method is used to ensure the main thread waits for the spawned thread to complete its execution before proceeding.
5. After the thread completes, the updated synchronizedScoreMap is printed.
Phonebook Example Using TreeMap
import java.util.TreeMap;
public class PhonebookExample {
public static void main(String[] args) {
// Create a TreeMap to store names and phone numbers
TreeMap<String, String> phonebook = new TreeMap<>();
// Adding entries to the phonebook
phonebook.put("John Doe", "+1234567890");
phonebook.put("Alice Brown", "+0987654321");
phonebook.put("Charlie Smith", "+1122334455");
// Retrieving and displaying a phone number
String johnNumber = phonebook.get("John Doe");
System.out.println("John Doe's Phone Number: " + johnNumber);
// Display the first and last entries in the phonebook
Map.Entry<String, String> firstEntry = phonebook.firstEntry();
System.out.println("First Entry: " + firstEntry.getKey() + " - " + firstEntry.getValue());
Map.Entry<String, String> lastEntry = phonebook.lastEntry();
System.out.println("Last Entry: " + lastEntry.getKey() + " - " + lastEntry.getValue());
}
}
Output:
John Doe's Phone Number: +1234567890 First Entry: Alice Brown - +0987654321 Last Entry: Charlie Smith - +1122334455
Explanation:
1. A TreeMap named phonebook is created to store names as keys and phone numbers as values.
2. Three name-phone number pairs are added to the phonebook using the put method.
3. The get method is used to retrieve and display the phone number associated with "John Doe".
4. The firstEntry and lastEntry methods of TreeMap are used to retrieve the first and last entries in the sorted phonebook, and their values are then displayed.
Conclusion
In this tutorial, you learned what is a TreeMap, how to create a TreeMap, how to use a custom Comparator to alter the sorting order of a TreeMap, how to find the entries from a TreeMap, and how to remove entries from a TreeMap, andsynchronize access to TreeMap.