Introduction
TreeMap
in Java is part of the Java Collections Framework and implements the NavigableMap
interface, which is a subtype of the SortedMap
interface. It is a collection that uses a Red-Black tree structure to store key-value pairs. TreeMap
ensures that the keys are stored in a sorted order, and it provides guaranteed log(n) time cost for the basic operations (get, put, remove).
Table of Contents
- What is TreeMap?
- Key Points About TreeMap
- Creating a TreeMap and Adding Elements
- Accessing Elements in a TreeMap
- Modifying Elements in a TreeMap
- Removing Elements from a TreeMap
- Iterating Over a TreeMap
- Searching for Elements in a TreeMap
- TreeMap of User-Defined Objects
- Common TreeMap Methods
- Difference Between TreeMap and HashMap
- Conclusion
1. What is TreeMap?
A TreeMap
is a collection that stores key-value pairs in a sorted order based on the keys. It is based on a Red-Black tree, which is a type of self-balancing binary search tree. The keys are ordered according to their natural ordering or by a Comparator
provided at map creation time, depending on which constructor is used.
2. Key Points About TreeMap
- Key-Value Pairs: Stores data in key-value pairs.
- Null Keys and Values: Does not allow null keys but allows multiple null values.
- Order: Maintains keys in a sorted order.
- NavigableMap: Implements the
NavigableMap
interface, providing additional methods to navigate the map. - Performance: Provides guaranteed log(n) time cost for basic operations (get, put, remove).
- Non-Synchronized: Not thread-safe by default.
3. Creating a TreeMap and Adding Elements
To create a TreeMap
, you can use the TreeMap
constructor. You can then use methods such as put
to add key-value pairs to the map.
Example:
In this example, we create a TreeMap
of strings and integers and add a few key-value pairs to it.
import java.util.TreeMap;
import java.util.Map;
public class TreeMapExample {
public static void main(String[] args) {
// Creating a TreeMap
Map<String, Integer> map = new TreeMap<>();
// Adding elements to the TreeMap
map.put("Apple", 1);
map.put("Banana", 2);
map.put("Cherry", 3);
// map.put(null, 4); // Null key (uncommenting this line will throw a NullPointerException)
map.put("Date", null); // Null value
// Displaying the TreeMap
System.out.println("TreeMap: " + map);
}
}
Output:
TreeMap: {Apple=1, Banana=2, Cherry=3, Date=null}
4. Accessing Elements in a TreeMap
You can access elements in a TreeMap
using the get
method by providing the key.
Example:
In this example, we demonstrate how to access elements in a TreeMap
.
import java.util.TreeMap;
import java.util.Map;
public class AccessTreeMap {
public static void main(String[] args) {
// Creating a TreeMap
Map<String, Integer> map = new TreeMap<>();
map.put("Apple", 1);
map.put("Banana", 2);
map.put("Cherry", 3);
// Accessing elements
System.out.println("Value for 'Banana': " + map.get("Banana"));
System.out.println("Value for 'Mango': " + map.get("Mango")); // Key not present
}
}
Output:
Value for 'Banana': 2
Value for 'Mango': null
5. Modifying Elements in a TreeMap
You can modify elements in a TreeMap
using the put
method, which will replace the value for the given key if it already exists.
Example:
In this example, we demonstrate how to modify elements in a TreeMap
.
import java.util.TreeMap;
import java.util.Map;
public class ModifyTreeMap {
public static void main(String[] args) {
// Creating a TreeMap
Map<String, Integer> map = new TreeMap<>();
map.put("Apple", 1);
map.put("Banana", 2);
map.put("Cherry", 3);
// Modifying an element
map.put("Banana", 4); // Updating value for key "Banana"
// Displaying the updated TreeMap
System.out.println("Updated TreeMap: " + map);
}
}
Output:
Updated TreeMap: {Apple=1, Banana=4, Cherry=3}
6. Removing Elements from a TreeMap
You can remove elements from a TreeMap
using methods such as remove
and clear
.
Example:
In this example, we demonstrate how to remove elements from a TreeMap
.
import java.util.TreeMap;
import java.util.Map;
public class RemoveTreeMap {
public static void main(String[] args) {
// Creating a TreeMap
Map<String, Integer> map = new TreeMap<>();
map.put("Apple", 1);
map.put("Banana", 2);
map.put("Cherry", 3);
// Removing an element
map.remove("Banana");
// Displaying the TreeMap after removal
System.out.println("TreeMap after removal: " + map);
// Clearing the TreeMap
map.clear();
System.out.println("TreeMap after clearing: " + map);
}
}
Output:
TreeMap after removal: {Apple=1, Cherry=3}
TreeMap after clearing: {}
7. Iterating Over a TreeMap
You can iterate over a TreeMap
using various methods such as a simple for-each loop, entrySet
, and keySet
.
Example:
In this example, we demonstrate different ways to iterate over a TreeMap
.
import java.util.TreeMap;
import java.util.Map;
public class IterateTreeMap {
public static void main(String[] args) {
// Creating a TreeMap
Map<String, Integer> map = new TreeMap<>();
map.put("Apple", 1);
map.put("Banana", 2);
map.put("Cherry", 3);
// Using for-each loop with entrySet
System.out.println("Using for-each loop with entrySet:");
for (Map.Entry<String, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
// Using for-each loop with keySet
System.out.println("Using for-each loop with keySet:");
for (String key : map.keySet()) {
System.out.println(key + ": " + map.get(key));
}
// Using forEach method (Java 8 and later)
System.out.println("Using forEach method:");
map.forEach((key, value) -> System.out.println(key + ": " + value));
}
}
Output:
Using for-each loop with entrySet:
Apple: 1
Banana: 2
Cherry: 3
Using for-each loop with keySet:
Apple: 1
Banana: 2
Cherry: 3
Using forEach method:
Apple: 1
Banana: 2
Cherry: 3
8. Searching for Elements in a TreeMap
You can search for elements in a TreeMap
using methods such as containsKey
and containsValue
.
Example:
In this example, we demonstrate how to check if a TreeMap
contains a specific key or value.
import java.util.TreeMap;
import java.util.Map;
public class SearchTreeMap {
public static void main(String[] args) {
// Creating a TreeMap
Map<String, Integer> map = new TreeMap<>();
map.put("Apple", 1);
map.put("Banana", 2);
map.put("Cherry", 3);
// Check if the TreeMap contains a specific key
System.out.println("Does the TreeMap contain 'Banana'? " + map.containsKey("Banana"));
System.out.println("Does the TreeMap contain 'Mango'? " + map.containsKey("Mango"));
// Check if the TreeMap contains a specific value
System.out.println("Does the TreeMap contain value 3? " + map.containsValue(3));
System.out.println("Does the TreeMap contain value 4? " + map.containsValue(4));
}
}
Output:
Does the TreeMap contain 'Banana'? true
Does the TreeMap contain 'Mango'? false
Does the TreeMap contain value 3? true
Does the TreeMap contain value 4? false
9. TreeMap of User-Defined Objects
You can use TreeMap
to store user-defined objects as keys or values. This involves creating a class for the objects you want to store and ensuring that the class implements the Comparable
interface or providing a Comparator
at the time of TreeMap
creation.
Example:
In this example, we create a Person
class and then create a TreeMap
to store Person
objects as keys.
import java.util.TreeMap;
import java.util.Map;
class Person implements Comparable<Person> {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public int compareTo(Person other) {
return Integer.compare(this.age, other.age);
}
@Override
public String toString() {
return "Person{name='" + name + "', age=" + age + "}";
}
}
public class UserDefinedObjectTreeMap {
public static void main(String[] args) {
// Creating a TreeMap with Person objects as keys
Map<Person, String> map = new TreeMap<>();
map.put(new Person("Alice", 30), "Engineer");
map.put(new Person("Bob", 25), "Designer");
map.put(new Person("Charlie", 35), "Manager");
// Displaying the TreeMap
for (Map.Entry<Person, String> entry : map.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
}
}
Output:
Person{name='Bob', age=25}: Designer
Person{name='Alice', age=30}: Engineer
Person{name='Charlie', age=35}: Manager
10. All TreeMap Class Methods
- Java TreeMap put() Method
- Java TreeMap remove() Method
- Java TreeMap get() Method
- Java TreeMap containsKey() Method
- Java TreeMap containsValue() Method
- Java TreeMap size() Method
- Java TreeMap firstKey() Method
- Java TreeMap lastEntry() Method
- Java TreeMap subMap() Method
- Java TreeMap headMap() Method
- Java TreeMap tailMap() Method
- Java TreeMap values() Method
- Java TreeMap keySet() Method
- Java TreeMap ceilingKey() Method
- Java TreeMap floorEntry() Method
- Java TreeMap lowerKey() Method
- Java TreeMap higherEntry() Method
- Java TreeMap pollLastEntry() Method
- Java TreeMap navigableKeySet() Method
- Java TreeMap putAll() Method
- Java TreeMap merge() Method
- Java TreeMap descendingMap() Method
- Java TreeMap descendingKeySet() Method
- Java TreeMap computeIfPresent() Method
- Java TreeMap ceilingEntry() Method
- Java TreeMap floorKey() Method
- Java TreeMap clear() Method
- Java TreeMap firstEntry() Method
- Java TreeMap putFirst() Method
- Java TreeMap putLast() Method
- Java TreeMap lowerEntry() Method
11. Conclusion
TreeMap
is a powerful and versatile data structure in Java that provides a way to store key-value pairs in a sorted order. It ensures that keys are stored in ascending order according to their natural ordering or by a specified Comparator
. Understanding how to create, manipulate, and iterate over TreeMap
can help you effectively manage collections of sorted key-value pairs in your Java applications. With methods for adding, removing, accessing, and searching elements, TreeMap
offers a comprehensive solution for managing sorted maps of data.
By using TreeMap
, you can ensure that your collections maintain a predictable and sorted order, which can be crucial for applications that require ordering, such as sorted views, navigation, and range queries. It combines the features of a balanced tree and map, providing efficient data storage and retrieval with sorted keys.