What Is TreeMap?
TreeMap is a Red-Black tree-based map implementation. The map is sorted according to the natural ordering of its keys (for Integer as key natural order is ascending order, for String as key natural order is alphabetical order), or by a Comparator provided at map creation time, depending on which constructor is used.
This implementation of TreeMap provides guaranteed log(n) time cost for the containsKey, get, put and removeoperations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest’s Introduction to Algorithms.
TreeMap class that extends AbstractMap and implements NavigableMap.
TreeMap Default Sorting:
Let’s create a basic
TreeMap and add some items to it and see how it stores them.import java.util.TreeMap;
public class TestTreeMap {
public static void main(String[] args) {
TreeMap<Integer, String> studentBranch = new TreeMap<Integer, String>();
studentBranch.put(101, "Computer");
studentBranch.put(105, "Mechanical");
studentBranch.put(102, "Electrical");
studentBranch.put(103, "Chemical");
studentBranch.put(104, "Civil");
System.out.println("Student Ids : " + studentBranch.keySet());
}
}Output:
Student Ids : [101, 102, 103, 104, 105]In this example, we added 5 items to the TreeMap in a non-orderly manner. But when we tried to retrieve the keys from the Map we can see they are returned in an ordered manner on keys. Note that keys are Integers and hence default sorting order is ascending.
Similar logic is applied to String keys. They are sorted and stored in alphabetic order.
import java.util.TreeMap;
public class TestTreeMap {
public static void main(String[] args) {
TreeMap<String, Integer> groceryItems = new TreeMap<String, Integer>();
groceryItems.put("Maggie", 2);
groceryItems.put("Chocolate", 5);
groceryItems.put("Salt", 1);
groceryItems.put("Sugar", 3);
groceryItems.put("Biscuit", 4);
System.out.println("Groceries Items : " + groceryItems.keySet());
}
}Output:
Groceries Items : [Biscuit, Chocolate, Maggie, Salt, Sugar]Reverse Sorting in TreeMap:
A HashMap does not guarantee the order of keys stored in the map but TreeMap guarantees that the keys will always be stored in sorted order as per the order specified while creating TreeMap.
import java.util.Comparator;
import java.util.TreeMap;
public class TestTreeMap {
public static void main(String[] args) {
TreeMap<String, Integer> groceryItems = new TreeMap<String, Integer>(Comparator.<String>reverseOrder());
groceryItems.put("Maggie", 2);
groceryItems.put("Chocolate", 5);
groceryItems.put("Salt", 1);
groceryItems.put("Sugar", 3);
groceryItems.put("Biscuit", 4);
System.out.println("Groceries Items : " + groceryItems.keySet());
}
}Output:
Groceries Items : [Sugar, Salt, Maggie, Chocolate, Biscuit]In the above example, entries are stored in TreeMap based on the reversed order of the keys.
Why Do We Need TreeMap?
There are multiple reasons why we need TreeMap.
- As the entries are stored in the map in sorted order, we can get the first and last entries very easily.
- Many inbuilt functions can be used to get part of the map.
import java.util.Comparator;
import java.util.TreeMap;
public class TestTreeMap {
public static void main(String[] args) {
TreeMap<String, Integer> groceryItems =
new TreeMap<String, Integer>(Comparator.<String>naturalOrder());
groceryItems.put("Maggie", 2);
groceryItems.put("Chocolate", 5);
groceryItems.put("Salt", 1);
groceryItems.put("Sugar", 3);
groceryItems.put("Biscuit", 4);
System.out.println("First Entry : " + groceryItems.firstEntry());
System.out.println("Last Entry : " + groceryItems.lastEntry());
System.out.println("First Key : " + groceryItems.firstKey());
System.out.println("First Key : " + groceryItems.lastKey());
System.out.println("Map content : " + groceryItems.entrySet());
System.out.println("First 3 Entries : " +
groceryItems.headMap("Salt").entrySet());
}
}Output :
First Entry : Biscuit=4
Last Entry : Sugar=3
First Key : Biscuit
First Key : Sugar
Map content : [Biscuit=4, Chocolate=5, Maggie=2, Salt=1, Sugar=3]
First 3 Entries : [Biscuit=4, Chocolate=5, Maggie=2]How Does TreeMap Work?
Internally TreeMap uses RedBlack Tree which is a self-balancing BST. In the case of the red-black tree the operations like
search, get, put and remove are performed in O(log n) because the max length of any branch is log n .In the worst-case scenario, the max length of any branch of the RedBlack tree can be
log(n) as opposed to the BST where there can be a skewed branch of length n. Hence worst case time complexity of TreeMap is O(log(n)).Note: if we think to use
TreeMap in a multi-threaded environment:- Note that this implementation is not synchronized. 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:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(…)); - 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 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.
Post a Comment