1. Introduction
A Tree Map is a red-black tree-based NavigableMap implementation. A NavigableMap is a SortedMap with some navigation methods – this returns the closest match for given search targets. The sorting is done according to the natural ordering of the keys present in the map. If a Comparator is provided at the creation time then it overrides the natural ordering. This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.
Note that the ordering maintained by a treemap, like any sorted map, and whether or not an explicit comparator is provided, must be consistent with equals if this sorted map is to correctly implement the Map interface. This is so because the Map interface is defined in terms of the equals operation, but a sorted map performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this method are, from the standpoint of the sorted map, equal. The behavior of a sorted map is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Map interface.
2. Thread Safety
TreeMap is not a thread-safe collection implicitly – you have to make it if any of the thread is modifying the map structurally. If multiple threads access a map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with an existing key is not a structural modification. This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be “wrapped” using the Collections.synchronizedSortedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map:
final SortedMap sortedMap = Collections.synchronizedSortedMap(new TreeMap());
3. Iteration
The iterators returned by the iterator method of the collections returned by all of this class’s “collection view methods” are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator’s own remove method, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future. Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.
4. Constructor
TreeMap class has four constructors. These can be used according to the requirements.
4.1 TreeMap()
This constructor constructs a new, empty treemap, using the natural ordering of its keys. All keys inserted into the map must implement the Comparable interface. Furthermore, all such keys must be mutually comparable: k1.compareTo(k2) must not throw a ClassCastException for any keys k1 and k2 in the map. If the user attempts to put a key into the map that violates this constraint (for example, the user attempts to put a string key into a map whose keys are integers), the put(Object key, Object value) call will throw a ClassCastException
4.2 TreeMap(Comparator<? super K> comparator)
This constructs a new, empty treemap, ordered according to the given comparator. All keys inserted into the map must be mutually comparable by the given comparator: comparator.compare(k1, k2) must not throw a ClassCastException for any keys k1 and k2 in the map. If the user attempts to put a key into the map that violates this constraint, the put(Object key, Object value) call will throw a ClassCastException
4.3 TreeMap(Map<? extends K, ? extends V> m)
Constructs a new tree map containing the same mappings as the given map, ordered according to the natural ordering of its keys. All keys inserted into the new map must implement the Comparable interface. Furthermore, all such keys must be mutually comparable: k1.compareTo(k2) must not throw a ClassCastException for any keys k1 and k2 in the map. This method runs in n*log(n) time. If the map passed as the argument to the method is null then this will throw NullPointerException.
4.4 TreeMap(SortedMap<K, ? extends V> m)
Constructs a new tree map containing the same mappings and using the same ordering as the specified sorted map. This method runs in linear time.
5. Methods
In this section, we will look into some of the important and most commonly used methods of Tree Map class.
containsKey(Object key)
Returns true if this map contains a mapping for the specified key. This method throws ClassCastException if the specified key cannot be compared with the keys currently in the map. It throws NullPointerException if the specified key is null and this map uses natural ordering, or its comparator does not permit null keys.
containsValue(Object value)
Returns true if this map maps one or more keys to the specified value. More formally, returns true if and only if this map contains at least one mapping to a value v such that (value==null ? v==null : value.equals(v)). This operation will probably require time linear in the map size for most implementations.
get(Object key)
Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key. If this map contains a mapping from a key k to a value v such that key compares equal to k according to the map’s ordering, then this method returns v; otherwise it returns null. A return value of null does not necessarily indicate that the map contains no mapping for the key; it’s also possible that the map explicitly maps the key to null. This method throws ClassCastException if the specified key cannot be compared with the keys currently in the map.
putAll(Map map)
Copies all of the mappings from the specified map to this map. These mappings replace any mappings that this map had for any of the keys currently in the specified map.
put(K Key, V value)
Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced. This method throws ClassCastException if the specified key cannot be compared with the keys currently in the map.
6. Tree Map Example
TreeMapExample.java
package org.javacodegeeks.treemap;
import java.util.*;
public class TreeMapExample {
public static void main(String[] args) {
TreeMapExample treeMapExample = new TreeMapExample();
treeMapExample.constructor1();
treeMapExample.constructor2();
treeMapExample.constructor3();
treeMapExample.clear();
treeMapExample.containsKey();
treeMapExample.containsValue();
treeMapExample.removeAndReplace();
}
/** Constructs a new, empty tree map, using the natural ordering of its keys */
private void constructor1() {
TreeMap<Integer, String> treeMap = new TreeMap();
treeMap.put(1, "one");
treeMap.put(2, "two");
System.out.println("Constructor1: " + treeMap);
}
/** Constructs a new, empty tree map, ordered according to the given comparator */
private void constructor2() {
TreeMap<Integer, String> treeMap = new TreeMap(Comparator.reverseOrder());
treeMap.put(2, "two");
treeMap.put(1, "one");
System.out.println("Constructor2: " + treeMap);
}
/** Constructs a new tree map containing the same mappings as the given map, ordered according to the natural ordering of its keys */
private void constructor3() {
Map<String, Integer> map = Map.of("one", 1, "two", 2, "three", 3, "four", 4);
TreeMap<Integer, String> treeMap = new TreeMap(map);
System.out.println("Constructor3: " + treeMap);
}
// #####################################################################
// ################# Important methods #################################
// #####################################################################
private TreeMap<String, Integer> constructTreeMap() {
TreeMap<String, Integer> treeMap = new TreeMap();
treeMap.put("one", 1);
treeMap.put("two", 2);
treeMap.put("three", 3);
treeMap.put("four", 4);
treeMap.put("five", 5);
return treeMap;
}
private void clear() {
TreeMap<String, Integer> treeMap = constructTreeMap();
System.out.println("\nBefore Clearing: " + treeMap);
treeMap.clear();
System.out.println("After Clearing: " + treeMap);
}
private void containsKey() {
TreeMap<String, Integer> treeMap = constructTreeMap();
System.out.println("\nContains key four: " + treeMap.containsKey("four"));
System.out.println("Does not contains key six: " + treeMap.containsKey("six"));
}
private void containsValue() {
TreeMap<String, Integer> treeMap = constructTreeMap();
System.out.println("\nContains value 4: " + treeMap.containsValue(4));
System.out.println("Does not contains value 6: " + treeMap.containsValue(6));
}
private void removeAndReplace() {
TreeMap<String, Integer> treeMap = constructTreeMap();
treeMap.remove("four");
System.out.println("\nContains key four: " + treeMap.containsKey("four"));
treeMap.replace("five", 6);
System.out.println("Value of five replaced with: " + treeMap.get("five"));
}
}
When you run the code above you will see something like below:
Constructor1: {1=one, 2=two}
Constructor2: {2=two, 1=one}
Constructor3: {four=4, one=1, three=3, two=2}
Before Clearing: {five=5, four=4, one=1, three=3, two=2}
After Clearing: {}
Contains key four: true
Does not contains key six: false
Contains value 4: true
Does not contains value 6: false
Contains key four: false
Value of five replaced with: 6
Process finished with exit code 0
7. Summary
In this article, we looked at one of the collection classes of Java – Tree Map. We looked at different ways of constructing the object and why we will use them. We also discussed some of the most common methods available in this class. We also discussed how to make this a thread-safe collection and also how we can iterate the elements in this object.
8. Download
This was an example of using TreeMap collection in Java
You can download the full source code of this example here: TreeMap in Java
