Java The TreeMap Class
The TreeMap class in Java is an implementation of the Map interface, similar to the HashMap class. It stores its entries in ascending order, sorted based on the natural ordering of the keys or a specified Comparator if provided during initialization. Unlike LinkedHashMap and HashMap, TreeMap does not rely on hashing to store keys. Instead, it utilizes a data structure known as a Red-Black tree.
Key points about TreeMap:
- Sorted Order: TreeMap maintains the keys in a sorted order. The sorting is based on either the natural ordering of the keys (if they implement the Comparable interface) or a custom Comparator provided at the time of TreeMap creation.
- Key-Value Mapping: TreeMap stores elements as key-value pairs, where each key is unique. It allows efficient retrieval, insertion, deletion, and modification of elements based on their keys.
- Red-Black Tree: TreeMap internally uses a self-balancing binary search tree called a red-black tree. This data structure ensures that the elements are always balanced, providing efficient search, insertion, and deletion operations with a time complexity of O(log n).
- Null Keys: Unlike HashMap, TreeMap does not allow null keys because it relies on the ordering of the keys. However, it can have null values associated with the keys.
- Iteration Order: When iterating over the elements of a TreeMap, they are returned in ascending order based on the keys' sorting criteria.
- Performance: TreeMap provides efficient operations for searching, insertion, and deletion, with a time complexity of O(log n) for most operations. However, these operations are slower than their counterparts in HashMap, as TreeMap needs to maintain the sorted order of the keys.
The following Java program illustrates several of the methods supported by this TreeMap collection Framework:
Red–Black tree
- Every node is either red or black.
- Root of tree is always black.
- Every leaf (NULL) is black.
- If a node is red, then both its children are black.
- Every path from root to a NULL node has same number of black nodes.
TreeMap Implementation and Key Sorting in Java
The implementation of TreeMap in Java is not synchronized. When multiple threads access a TreeMap concurrently and if any of the threads modify the structure of the TreeMap, it is important to synchronize it externally to ensure thread-safety.
One of the notable features of the TreeMap class is its ability to maintain keys in a sorted order. This makes TreeMap perfect for scenarios where you need to traverse the keys in a specific order. The sorting of keys can be achieved by either implementing the Comparable interface in the key objects or by providing a custom Comparator implementation during the creation of the TreeMap.
By specifying a Comparator, you have control over the sorting order of the keys in the TreeMap. This allows you to define your own criteria for sorting, overriding the natural ordering of the keys.
Additionally, TreeMap provides several useful methods. The firstKey() method returns the first (smallest) key in the map, while the lastKey() method returns the last (largest) key in the map. The headMap(toKey) method returns a portion of the map that contains keys less than the specified toKey, and the tailMap(fromKey) method returns a portion of the map that contains keys greater than or equal to the specified fromKey.
These features make TreeMap a powerful data structure for organizing and manipulating key-value pairs in a sorted manner, providing convenient access to specific portions of the map based on key ranges.
Conclusion
The TreeMap class in Java is an implementation of the SortedMap interface, which means it maintains the elements in a sorted order based on their keys. It uses a red-black tree data structure to store the key-value pairs, providing efficient retrieval and manipulation operations.