TreeMap in Java

Read Time:7 Minute, 10 Second

Table of Contents

Besides the AbstractMap Class, Java’s TreeMap discreetly implements the Map interface and NavigableMap. Depending on which constructor is used, the map is sorted either by the natural ordering of its keys or by a Comparator specified at map creation time.

This is an effective method of sorting and storing key-value pairs. Regardless of the specified comparators, the treemap’s storage order must be consistent with equals, just like any other sorted map. The implementation of a treemap is presented as not synchronized because a map must be synchronized externally if it is used by multiple threads concurrently, and at least one of the threads modifies the map fundamentally.

Class declaration for TreeMap

Let’s look at the java.util.TreeMap class declaration.

Class parameters for TreeMap

Let’s look at the java.util.TreeMap class’s parameters.

SUGGESTED READ

  • This map’s kind of keys is designated by the letter K.
  • The type of mapped value is V.

TreeMap Characteristics

The following are some of the treemap’s key features:

  • The Java Collections Framework includes this class.
  • The class extends AbstractMap and implements Map interfaces such as NavigableMap and SortedMap.
  • Because TreeMap (unlike Map) does not accept null keys, a NullPointerException is raised.
  • On the other hand, multiple null values can be associated with separate keys.
  • The entry pairs given by this class’s methods and views are snapshots of mappings taken when they were created.
  • The Entry.setValue method is not supported.

Now it’s time to talk about Synchronized TreeMap. The TreeMap implementation is not synchronized. This means that if multiple threads visit a tree set simultaneously and at least one of the updates it, the set must be externally synchronized. The Collections.synchronizedSortedMap method is commonly used to accomplish this. This should be done at the creation time to avoid unintentional unsynchronized access to the set. This can be accomplished by:

You’re probably wondering how the TreeMap works on the inside.

The methods in a TreeMap return an Iterator that is fail-safe for getting keyset and values. ConcurrentModificationException will be thrown for any concurrent modification. The data structure of a TreeMap is a red-black tree. Each node in the tree has the following properties:

TreeMap constructors

When creating a TreeMap, we must first create a TreeMap object. The TreeMap class contains several constructors that allow the TreeMap to be created. The constructors available in this class are as follows:

SUGGESTED READ

  • TreeMap()
  • TreeMap(Comparator comp)
  • TreeMap(Map M)
  • TreeMap(SortedMap sm)

Let’s go over each one individually before implementing each constructor:

The first constructor: TreeMap

This constructor creates an empty treemap that will be sorted according to its keys’ natural order. Example :

The second Constructor: TreeMap(Comparator comp)

This constructor is responsible for creating an empty TreeMap object with nodes that require an external sorting order specification.

The third Constructor: TreeMap (Map M)

This constructor is used to populate a TreeMap with entries from a specified map ‘M’, which will be sorted following the keys’ natural order.

Example

SUGGESTED READ

The fourth Constructor: TreeMap(SortedMap sm)

This constructor fills a TreeMap with the items from the specified sorted map, stored in the same order as the sorted map.

The TreeMap Class’s methods

clear()

The method clears the map and removes all mappings from the TreeMap.

clone()

A shallow copy of this TreeMap is returned by this method.

containsKey(Object key)

If this map has a mapping for the supplied key, it returns true.

containsValue(Object value)

If this map is responsible for mapping one or more keys to the supplied value, it returns true.

SUGGESTED READ

entrySet()

This method is responsible for returning a set view of the mappings in this map.

firstKey()

Returns the current sorted map’s first (lowest) key.

get(Object key)

Returns the value to which this map maps the supplied key.

headMap(Object key_value)

The method returns a view of the map section that is strictly less than the key_value parameter.

keySet()

The method returns a Set representation of the treemap’s keys.

SUGGESTED READ

lastKey()

Returns the current sorted map’s last (highest) key.

put(Object key, Object value)

A mapping is inserted into a map using this way.

putAll(Map map)

All mappings from the specified map are copied to this map.

remove(Object key)

If this TreeMap has a mapping for this key, it is removed.

size()

The number of key-value mappings in this map is returned.

SUGGESTED READ

subMap((K startKey, K endKey)

The method returns the map portion with keys ranging from startKey to endKey, inclusive and exclusive.

values()

This method is tasked with returning a collection view of the values in this map.

The following programs will show you how to create, insert, and navigate through the TreeMap implementation.

Example: Program for Illustrating the Operations in TreeMap

Using TreeMap to Perform Various Operations

It is now possible to limit the kind of object that can be put in the TreeMap thanks to the advent of Generics in Java 1.5. Let’s look at using the TreeMap to accomplish a few common operations.

SUGGESTED READ

Operation One: Adding Elements

The put() method can add an element to the TreeMap. In the TreeMap, however, the insertion order is not preserved. Internally, the keys are compared and sorted in ascending order for each element. The common methods for adding elements include:

  • put() -Puts the provided key/value mapping (entry) into the map.
  • PutAll() -Puts all the entries from a specified map into this map.
  • PutIfAbsent() – If the supplied key is not present in the map, putIfAbsent() adds the specified key/value mapping to the map.

Operation Two: TreeMap Element Access

Using values(), keySet(), and entrySet()
  • entrySet() – returns a collection of all the key/value mappings (entry) for a treemap key.
  • keySet()- returns a collection of all the keys in a treemap.
  • values() – delivers a collection of a tree map’s maps.
Using the functions get() and getOrDefault()
  • get() – Returns the value that corresponds to the supplied key. If the key cannot be retrieved, null is returned.
  • getOrDefault() – Gets the default value for the provided key. If the key cannot be discovered, the default value is returned.

For instance,

The getOrDefault() method fails to locate the key Ten in this case. As a result, the default number 10 is returned.

Operation Three: Changing Elements

If we want to update an element after it has been added, we can do it by using the put() method to add it again. Because the keys are used to index the items in the treemap, the value of the key can be altered by simply adding the updated value for the key we want to change.

Operation Four: Element Removal

The remove() method can delete an element from the TreeMap. If the key value is present in the map, this method removes the mapping for the key from the treemap.

SUGGESTED READ

Example

Operation Five: Iterating through the TreeMap

There are several methods for iterating through the Map. The most well-known method is to utilize a for-each loop to obtain the keys. The getValue() method is designated for determining the key’s value.

Example

Comparator for TreeMaps

Treemap elements are arranged organically in all of the instances above (in ascending order). We can, however, change the sequence of the keys. We’ll need to make our comparator class depending on how a treemap’s keys are arranged. For instance,

Example: Java TreeMap

Example: Java TreeMap remove()

Example: Java TreeMap NavigableMap

Example: Java TreeMap SortedMap

Example: Java TreeMap Laptop

Conclusion

With the help of examples, we have learned about the Java TreeMap class and its actions in this article. The tree data structure is implemented by the Java collections framework’s TreeMap class. Further, the NavigableMap interface is implemented.

SUGGESTED READ

The TreeMap class uses a tree to implement the Map interface. A TreeMap is an effective way to store key/value pairs in sorted order and retrieve them quickly. It’s worth noting that, unlike a hash map, a treemap ensures that the items are ordered in ascending key order. In addition, the Java TreeMap class implements a red-black tree model. It facilitates the storage of key-value pairs in sorted order quickly.

Source: https://www.codeunderscored.com/treemap-in-java/

WP Ad Inserter plugin for WordPress