TreeMap in Java is used to store key-value pairs very similar to HashMap class. Difference is that TreeMap provides an efficient way to store key/value pairs in sorted order. It is a red-Black tree based NavigableMap implementation.
In this Java TreeMap tutorial, we will learn about TreeMap class, it’s methods, usecases and other important details.
Table of Contents 1. TreeMap Hierarchy 2. TreeMap Features 3. TreeMap Constructors 4. TreeMap Methods 5. TreeMap Example 6. TreeMap Usecases 7. TreeMap Performance 8. Concurrency in TreeMap 9. Conclusion
1. TreeMap Hierarchy
The TreeMap class is declared as following in Java. It extends AbstractMap class and implements NavigableMap interface. Here 'K' is the type of keys and 'V' is the type of mapped values to keys.
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
//implementation
}
2. TreeMap Features
The important points about Java TreeMap class are:
- It stores key-value pairs similar to like HashMap.
- It allows only distinct keys. Duplicate keys are not possible.
- It cannot have
nullkey but can have multiplenullvalues. - It stores the keys in sorted order (natural order) or by a
Comparatorprovided at map creation time. - It provides guaranteed log(n) time cost for the
containsKey,get,putandremoveoperations. - It is not synchronized. Use
Collections.synchronizedSortedMap(new TreeMap())to work in concurrent environment. - The iterators returned by the
iteratormethod are fail-fast.
3. TreeMap Constructors
The TreeMap has five types of constructors:
- TreeMap(): creates a new, empty tree map, using the natural ordering of its keys.
- TreeMap(Comparator c): creates a new, empty tree map, ordered according to the given comparator.
- TreeMap(Map map): creates a new tree map containing the same mappings as the given map, ordered according to the natural ordering of its keys.
- TreeMap(SortedMap map): creates a new tree map containing the same mappings and using the same ordering as the specified sorted map.
4. TreeMap Methods
The important methods we should learn about TreeMap are as follows:
- void clear(): It removes all the key-value pairs from the map.
- void size(): It returns the number of key-value pairs present in this map.
- void isEmpty(): It returns true if this map contains no key-value mappings..
- boolean containsKey(Object key): It returns
'true'if a specified key is present in the map. - boolean containsValue(Object key): It returns
'true'if a specified value is mapped to at least one key in the map. - Object get(Object key): It retrieves the
valuemapped by the specifiedkey, or null if this map contains no mapping for the key. - Object remove(Object key): It removes the key-value pair for the specified key from the map if present.
- Comparator comparator(): It returns the comparator used to order the keys in this map, or null if this map uses the natural ordering of its keys.
- Object firstKey(): It returns the first (least) key currently in the tree map.
- Object lastKey(): It returns the last (greatest) key currently in the tree map.
- Object ceilingKey(Object key): It returns the least key greater than or equal to the given key, or null if there is no such key.
- Object higherKey(Object key): It returns the least key strictly greater than the specified key.
- NavigableMap descendingMap(): It returns a reverse order view of the mappings contained in this map.
5. Java TreeMap Example
5.1. TreeMap Example with Natural Ordering
Java program to demonstrate the usages of TreeMap methods with natual ordering.
import java.util.Iterator;
import java.util.TreeMap;
public class LinkedHashMapExample
{
public static void main(String[] args)
{
//Natual ordering by deafult
TreeMap<Integer, String> pairs = new TreeMap<>();
pairs.put(2, "B");
pairs.put(1, "A");
pairs.put(3, "C");
String value = pairs.get(3); //get method
System.out.println(value);
value = pairs.getOrDefault(5, "oops"); //getOrDefault method
System.out.println(value);
//Iteration example
Iterator<Integer> iterator = pairs.keySet().iterator();
while(iterator.hasNext()) {
Integer key = iterator.next();
System.out.println("Key: " + key + ", Value: " + pairs.get(key));
}
//Remove example
pairs.remove(3);
System.out.println(pairs);
System.out.println(pairs.containsKey(1)); //containsKey method
System.out.println(pairs.containsValue("B")); //containsValue method
System.out.println(pairs.ceilingKey(2));
}
}
Program Output.
C
oops
Key: 1, Value: A
Key: 2, Value: B
Key: 3, Value: C
{1=A, 2=B}
true
true
2
5.2. TreeMap Example with Custom Ordering using Comparator
import java.util.Iterator;
import java.util.TreeMap;
public class LinkedHashMapExample
{
public static void main(String[] args)
{
//Sort keys in reverse order
TreeMap<Integer, String> pairs = new TreeMap<>(Collections.reverseOrder());
pairs.put(2, "B" );
pairs.put(1, "A");
pairs.put(3, "C");
System.out.println(pairs);
}
}
Program Output.
{3=C, 2=B, 1=A}
6. TreeMap Usecases
Whether using default ordering or custom ordering using comparator, TreeMap provides an efficient method to store and retrieve the information contained within in a sorted manner. This makes it excellent tool to be used in scenarios where information needs to displayed in sorted order. For example, employees information based on their age or phone numbers in in any mobile application.
Another useful usecase can be a dictionary where information is recorded and displayed in sorted fashion.
In fact, they are useful any place where the information needs to be sorted and where quick random access is necessary. If random access is not needed then rather use sorted set or list.
7. TreeMap Performance
TreeMap provides the performance of log(n) for most operations like add(), remove() and contains(). HashMap performs with constant-time performance O(1) for same operations. In that way, HashMap performs much better than TreeMap.
TreeMap has better performance in memory management as it does not maintain an array internally to store key-value pairs. In HashMap, array size is determined while initialization or resizing which if is often more than needed at the time. It waste the memory. There is no such problem with TreeMap.
8. Concurrency in TreeMap
Both versions of Map, HashMap and TreeMap aren’t synchronized and the programmer need to manage concurrent access on the maps.
We can get the synchronized view of the treemap explicitly using Collections.synchronizedSortedMap(new TreeMap()).
Map<Integer, String> syncTreeMap = Collections.synchronizedSortedMap(new TreeMap<Integer, String>()); syncTreeMap.put(1, "A"); syncTreeMap.put(2, "B" ); syncTreeMap.put(3, "C");
9. Conclusion
In this tutorial, we learned about Java TreeMap class and it’s internals. We saw how it stores key-value pairs in sorted manner – either in natural ordering (default) or in some custom ordering of keys (using provided comparator).
We discussed how and when we should use TreeMap in real time applications. We compared the performance of TreeMap with HashMap to bettter understand when to use which version of Map.
Drop me your questions related to working with TreeMap in Java in comments section.
Happy Learning !!
Reference:
Ask Questions & Share Feedback