Deep Dive into Java TreeMap
Welcome! In today's blog post, we are going to explore one of the most useful data structures available in Java, the TreeMap.
Introduction to TreeMap
In Java, a TreeMap is part of the Collections Framework and is a member of the Map family. TreeMap implements the NavigableMap interface and extends AbstractMap which extends Map interface.
The TreeMap data structure stores key-value pairs in a sorted order on the basis of the key. Internally, it uses a Red-Black tree, which is a type of self-balancing binary search tree. The sorting order follows the natural ordering of its keys, or by a custom Comparator provided at map creation time, depending on which constructor is used.
Creating a TreeMap
You can create a TreeMap in Java using its constructors:
// Creating an empty TreeMap
TreeMap<Integer, String> treeMap = new TreeMap<>();
// Creating a TreeMap with a Custom Comparator
TreeMap<Integer, String> treeMap = new TreeMap<>(Comparator.reverseOrder()); The TreeMap class provides four constructors:
TreeMap(): Constructs an empty tree map that will be sorted by using the natural order of its keys.TreeMap(Comparator<? super K> comparator): Constructs an empty tree map that will be sorted by using the Comparator.TreeMap(Map<? extends K,? extends V> m): Constructs a new tree map containing the same mappings as the given map, sorted according to the natural ordering of its keys.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.
Adding Elements to TreeMap
To add elements to a TreeMap, you can use the put(key, value) method:
TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(3, "Three");
treeMap.put(2, "Two");
treeMap.put(1, "One"); In the above code, we've added three key-value pairs to the TreeMap. The keys are Integers and the values are Strings.
Accessing Elements from TreeMap
To access elements from a TreeMap, you can use the get(key) method:
String value = treeMap.get(1); // It will return "One" If the specified key is not present in the TreeMap, the get(key) method will return null .
Removing Elements from TreeMap
To remove elements from a TreeMap, you can use the remove(key) method:
treeMap.remove(1); // It will remove the key-value pair with key = 1 The remove(key) method removes the mapping for this key from this TreeMap if present.
Iterating through a TreeMap
You can iterate through a TreeMap using entrySet() with for-each loop:
for (Map.Entry<Integer, String> entry : treeMap.entrySet()) { System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue()); } TreeMap Methods
The TreeMap class provides several useful methods:
clear(): Removes all mappings from this TreeMap.containsKey(Object key): Returns true if this map contains a mapping for the specified key.containsValue(Object value): Returns true if this map maps one or more keys to the specified value.entrySet(): Returns a Set view of the mappings contained in this map.firstKey(): Returns the first (lowest) key currently in this map.lastKey(): Returns the last (highest) key currently in this map.size(): Returns the number of key-value mappings in this map.
Working with a Custom Comparator in TreeMap
In addition to natural ordering, TreeMap allows you to define your own rules for ordering the keys by using a comparator during the construction of the TreeMap.
Here's an example of a TreeMap with a custom comparator that sorts the keys in reverse order:
TreeMap<Integer, String> treeMap = new TreeMap<>(Comparator.reverseOrder()); treeMap.put(3, "Three"); treeMap.put(2, "Two"); treeMap.put(1, "One"); for (Map.Entry<Integer, String> entry : treeMap.entrySet()) {
System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
} In this example, the output will be sorted in reverse order of the keys.
Navigating through TreeMap
The TreeMap class provides several methods for navigating the TreeMap:
firstEntry(): Returns a key-value mapping associated with the least key in this map, ornullif the map is empty.lastEntry(): Returns a key-value mapping associated with the greatest key in this map, ornullif the map is empty.higherEntry(Key key): Returns a key-value mapping associated with the least key greater than the given key, ornullif there is no such key.lowerEntry(Key key): Returns a key-value mapping associated with the greatest key less than the given key, ornullif there is no such key.floorEntry(Key key): Returns a key-value mapping associated with the greatest key less than or equal to the given key, ornullif there is no such key.ceilingEntry(Key key): Returns a key-value mapping associated with the least key greater than or equal to the given key, ornullif there is no such key.
These methods return Map.Entry objects, from which you can retrieve the key and value using getKey() and getValue() methods respectively.
Thread Safety with TreeMap
TreeMap is not synchronized, which means it's not suitable for thread-safe operations until unless synchronized explicitly.
If you need to use this Map implementation in a multi-threading environment with the following conditions:
- Multiple threads are accessing the map.
- At least one thread is updating (inserting or removing) entries.
Then you should synchronize it externally:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...)); Conclusion
TreeMap in Java provides an efficient means of storing key-value pairs in sorted order. The ability to rapidly search for a key, delete an entry, or find the smallest or largest key is what makes this data structure powerful. Now you have a good understanding of how to create, manipulate, and access data in a TreeMap. Enjoy coding with Java TreeMap!
References