Deep Dive into Java 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:

code// 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:

1. TreeMap() : Constructs an empty tree map that will be sorted by using the natural order of its keys.

2. TreeMap(Comparator<? super K> comparator) : Constructs an empty tree map that will be sorted by using the Comparator.

3. 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.

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.

Adding Elements to TreeMap

To add elements to a TreeMap, you can use the put(key, value) method:

codeTreeMap<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:

codeString 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:

codetreeMap.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:

codefor (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:

codeTreeMap<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, or null if the map is empty.

• lastEntry() : Returns a key-value mapping associated with the greatest key in this map, or null if the map is empty.

• higherEntry(Key key) : Returns a key-value mapping associated with the least key greater than the given key, or null if there is no such key.

• lowerEntry(Key key) : Returns a key-value mapping associated with the greatest key less than the given key, or null if 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, or null if 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, or null if 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:

codeSortedMap 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

• Java - The TreeMap Class
• TreeMap in Java