Java TreeMap - TreeMap in Java

What is TreeMap in Java?

TreeMap is designed to store key-value pairs in sorted order and allows rapid retrieval. TreeMap is based on Red-Black tree implementation. This map sorted according to the Comparable natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

Here is the topic that will cover in this post.

1. TreeMap class Declaration
2. TreeMap features
3. TreeMap constructors
4. TreeMap class Methods
5. Example
6. Iterate or Traverse over TreeMap
7. Difference between HashMap and TreeMap

Java TreeMap class Declaration

The TreeMap class extends AbstractMap and implements the NavigableMap interface. Unlike HashMap, a tree map guarantees that its elements will be sorted in ascending key order.

public class TreeMap<K,V> extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

Here, K specifies the type of keys, and V specifies the type of values.

Java TreeMap features

1. Java TreeMap inherits AbstractMap class.
2. Java TreeMap implements the NavigableMap interface
3. Java TreeMap does not permit null key, but any null values.
4. Java TreeMap provide guaranteed log(n) time cost for the containsKey, get, put and remove operations.
5. Java TreeMap guarantees that its elements will be sorted in ascending key order.
6. Java TreeMap can not be used for primitive types, like int, char, etc. We need to use wrapper classes.
7. Java TreeMap is not synchronized.
8. Java TreeMap is not thread-safe. You can make thread-safe by doing

   Map m = Collections.synchronizedSortedMap(new TreeMap(...));

9. The iterators returned by all of this class's "collection view methods" are fail-fast.
10. Comparision on all keys perform using compareTo and compare method based on Comparable natural ordering or Comparator accordingly.

Java TreeMap constructors

Java TreeMap have four constructors.

Constructor	Description
public TreeMap()	Constructs a new empty tree map using the natural ordering of its keys. All keys inserted into the map must implement the Comparable interface.
public TreeMap(Comparator<? super K> comparator)	Constructs a new empty tree map, ordered according to the given comparator.
public 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.
public TreeMap(Map<? extends K, ? extends V> m)	Constructs a new tree map containing the same mappings as the given map, ordered according to the natural ordering of its keys. All keys inserted into the new map must implement the Comparable interface.

Below code snippet show example to create TreeMap instances using it's constructors.

    TreeMap<Integer, String> treeMap1 = new TreeMap<>();

    MyComparator myComparator = new MyComparator();
    TreeMap<Integer, String> treeMap2 = new TreeMap<>(myComparator);

    TreeMap<Integer, String> treeMap3 = new TreeMap<>(treeMap1);

    HashMap<Integer, String> hashMap = new HashMap<>();
    TreeMap<Integer, String> treeMap4 = new TreeMap<>(hashMap);
    

Java TreeMap methods

Let's have a look on TreeMap methods before Java 8. TreeMap have implemented the NavigableMap, so all of the method of this map is also available in this class. I have already discussed the methods of NavigableMap.

Method	Description
public int size()	Returns the number of key-value mappings in this map.
public boolean isEmpty()	Returns true if this map contains no key-value mappings.
public V get(Object key)	Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
public K firstKey()	Returns first (lowest) key currently in this sorted map.
public K lastKey()	Returns last (highest) key currently in this sorted map.
public boolean containsKey(Object key)	Returns true if this map contains a mapping for the specified key.
public V put(K key, V value)	Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced.
public void putAll(Map<? extends K, ? extends V> m)	Copies all of the mappings from the specified map to this map. These mappings will replace any mappings that this map had for any of the keys currently in the specified map.
public V remove(Object key)	Removes the mapping for the specified key from this map if present, otherwise null if there was no mapping for key
public void clear()	Removes all of the mappings from this map. The map will be empty after this call returns.
public boolean containsValue(Object value)	Returns true if this map maps one or more keys to the specified value.
public Set<K> keySet()	Returns a Set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa.
public Collection<V> values()	Returns a Collection view of the values contained in this map. The collection is backed by the map, so changes to the map are reflected in the collection, and vice-versa.
public Set<Map.Entry<K,V>> entrySet()	Returns a Set view of the mappings contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa.
public Object clone()	Returns a shallow copy of this TreeMap instance: the keys and values themselves are not cloned.

There are many new methods in TreeMap which was introduced in Java 8

Method	Description
default V getOrDefault(Object key, V defaultValue)	Returns the value to which the specified key is mapped, or defaultValue if this map contains no mapping for the key.
default void forEach(BiConsumer<? super K, ? super V> action)	Performs the given action for each entry in this map until all entries have been processed or the action throws an exception. A ConcurrentModificationException will be thrown if an element is removed during the process.
default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function)	Replaces each entry's value with the result of invoking the given function on that entry until all entries have been processed or the function throws an exception. Exceptions thrown by the function are relayed to the caller.
default V putIfAbsent(K key, V value)	If the specified key is not already associated with a value (or is mapped to null) associates it with the given value and returns null, else returns the current value.
default boolean remove(Object key, Object value)	Removes the entry for the specified key only if it is currently mapped to the specified value.
default boolean replace(K key, V oldValue, V newValue)	If the key/value pair specified by key and oldValue is in the invoking map, the value is replaced by newValue and true is returned. Otherwise false is returned.
default V replace(K key, V value)	Replaces the entry for the specified key only if it is currently mapped to some value.
default V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)	If the specified key is not already associated with a value (or is mapped to null), attempts to compute its value using the given mapping function and enters it into this map unless null.
default V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)	If key is in the map, a new value is constructed through a call to remappingFunction and the new value replaces the old value in the map. In this case, the new value is returned. If the value returned by remappingFunction is null, the existing key and value are removed from the map and null is returned.
default V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)	Calls remappingFunction to construct a new value. If remappingFunction returns non-null, the new key/value pair is added to the map or any preexisting pairing is removed, and the new value is returned. If remappingFunction returns null, any preexisting pairing is removed, and null is returned.
default V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)	If the specified key is not already associated with a value or is associated with null, associates it with the given non-null value. Otherwise, replaces the associated value with the results of the given remapping function, or removes if the result is null.

Example

Here is a simple program of TreeMap using common methods.

package com.walking.techie;

import java.util.Collection;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;

public class TreeMapDemo {

  public static void main(String[] args) {
    TreeMap<Integer, String> httpStatusMap = new TreeMap<>();
    httpStatusMap.put(400, "Bad Request");
    httpStatusMap.put(401, "Unauthorized");
    httpStatusMap.put(405, "Method Not Allowed");
    httpStatusMap.put(500, "Server Error");
    httpStatusMap.put(503, "Service Unavailable");
    httpStatusMap.put(507, "Insufficient Storage");
    httpStatusMap.put(511, "Network Authentication Required");
    httpStatusMap.put(200, "OK");
    httpStatusMap.put(202, "Accepted");
    httpStatusMap.put(203, "Non Authoritative Information");
    httpStatusMap.put(300, "Multiple Choices");
    httpStatusMap.put(302, "Moved Temporarily");
    httpStatusMap.put(100, "Continue");
    httpStatusMap.put(101, "Switching Protocols");
    httpStatusMap.put(102, "Processing");

    // size of TreeMap
    System.out.println("Size of the Http Status Tree Map: " + httpStatusMap.size());

    // check TreeMap is empty or not
    System.out.println("Is TreeMap Empty? " + httpStatusMap.isEmpty());

    // get the value for given Key
    System.out.println("Http message for HttpStatus code 400 is " + httpStatusMap.get(400));
    System.out.println("Http message for HttpStatus code 403 is " + httpStatusMap.get(403));

    // check TreeMap contain mapping for given key
    System.out.println(
        "Is TreeMap contain mapping for HttpStatus code 500 is " + httpStatusMap.containsKey(500));
    System.out.println(
        "Is TreeMap contain mapping for HttpStatus code 403 is " + httpStatusMap.containsKey(403));

    Map<Integer, String> httpStatus = new TreeMap<>();
    httpStatus.put(424, "Failed Dependency");
    httpStatus.put(422, "Unprocessable Entity");
    httpStatus.put(429, "Too Many Requests");
    httpStatus.put(504, "Gateway Timeout");
    httpStatus.put(409, "Conflict");

    // copy all elements of httpStatus to httpStatusMap
    httpStatusMap.putAll(httpStatus);

    // print all the elements of the HttpStatusMap
    System.out.println("\n******All elements of the httpStatusMap");
    for (Integer code : httpStatusMap.keySet()) {
      System.out
          .println("Http Status Code : " + code + " Http Message : " + httpStatusMap.get(code));
    }

    // remove the mapping from the TreeMap for given key
    System.out.println("\nValue of the removed key (507) is : " + httpStatusMap.remove(507));

    // To check value is present is the TreeMap
    System.out.println("Too Many Requests is present in TreeMap : " + httpStatusMap
        .containsValue("Too Many Requests"));
    System.out.println("Upgrade Required is present in TreeMap : " + httpStatusMap
        .containsValue("Upgrade Required"));

    // Get collection view of this TreeMap
    Collection<String> httpStatusMessage = httpStatusMap.values();
    System.out.println("\n *****Http Status message of the collection view*****");
    for (String message : httpStatusMessage) {
      System.out.println("Http Status Message : " + message);
    }

    // Display key-value pair of element using EntrySet
    Set<Entry<Integer, String>> entrySet = httpStatusMap.entrySet();
    Iterator<Entry<Integer, String>> iterator = entrySet.iterator();
    System.out.println("\n *****Display Elements of the TreeMap using EntrySet*****");
    while (iterator.hasNext()) {
      Entry<Integer, String> entry = iterator.next();
      System.out
          .println("Http Status Code : " + entry.getKey() + " Http Message : " + entry.getValue());
    }
    // create clone of TreeMap
    Object clonedTreeMap = httpStatusMap.clone();
    System.out.println("\nCloned Tree Map : \n" + clonedTreeMap);

    // clear all elements of the TreeMap
    httpStatusMap.clear();
    System.out.println("\nSize of the httpStatusMap is " + httpStatusMap.size());

  }
}
    

Output of above program is shown below:

Size of the Http Status Tree Map: 15
Is TreeMap Empty? false
Http message for HttpStatus code 400 is Bad Request
Http message for HttpStatus code 403 is null
Is TreeMap contain mapping for HttpStatus code 500 is true
Is TreeMap contain mapping for HttpStatus code 403 is false

******All elements of the httpStatusMap
Http Status Code : 100 Http Message : Continue
Http Status Code : 101 Http Message : Switching Protocols
Http Status Code : 102 Http Message : Processing
Http Status Code : 200 Http Message : OK
Http Status Code : 202 Http Message : Accepted
Http Status Code : 203 Http Message : Non Authoritative Information
Http Status Code : 300 Http Message : Multiple Choices
Http Status Code : 302 Http Message : Moved Temporarily
Http Status Code : 400 Http Message : Bad Request
Http Status Code : 401 Http Message : Unauthorized
Http Status Code : 405 Http Message : Method Not Allowed
Http Status Code : 409 Http Message : Conflict
Http Status Code : 422 Http Message : Unprocessable Entity
Http Status Code : 424 Http Message : Failed Dependency
Http Status Code : 429 Http Message : Too Many Requests
Http Status Code : 500 Http Message : Server Error
Http Status Code : 503 Http Message : Service Unavailable
Http Status Code : 504 Http Message : Gateway Timeout
Http Status Code : 507 Http Message : Insufficient Storage
Http Status Code : 511 Http Message : Network Authentication Required

Value of the removed key (507) is : Insufficient Storage
Too Many Requests is present in TreeMap : true
Upgrade Required is present in TreeMap : false

 *****Http Status message of the collection view*****
Http Status Message : Continue
Http Status Message : Switching Protocols
Http Status Message : Processing
Http Status Message : OK
Http Status Message : Accepted
Http Status Message : Non Authoritative Information
Http Status Message : Multiple Choices
Http Status Message : Moved Temporarily
Http Status Message : Bad Request
Http Status Message : Unauthorized
Http Status Message : Method Not Allowed
Http Status Message : Conflict
Http Status Message : Unprocessable Entity
Http Status Message : Failed Dependency
Http Status Message : Too Many Requests
Http Status Message : Server Error
Http Status Message : Service Unavailable
Http Status Message : Gateway Timeout
Http Status Message : Network Authentication Required

 *****Display Elements of the TreeMap using EntrySet*****
Http Status Code : 100 Http Message : Continue
Http Status Code : 101 Http Message : Switching Protocols
Http Status Code : 102 Http Message : Processing
Http Status Code : 200 Http Message : OK
Http Status Code : 202 Http Message : Accepted
Http Status Code : 203 Http Message : Non Authoritative Information
Http Status Code : 300 Http Message : Multiple Choices
Http Status Code : 302 Http Message : Moved Temporarily
Http Status Code : 400 Http Message : Bad Request
Http Status Code : 401 Http Message : Unauthorized
Http Status Code : 405 Http Message : Method Not Allowed
Http Status Code : 409 Http Message : Conflict
Http Status Code : 422 Http Message : Unprocessable Entity
Http Status Code : 424 Http Message : Failed Dependency
Http Status Code : 429 Http Message : Too Many Requests
Http Status Code : 500 Http Message : Server Error
Http Status Code : 503 Http Message : Service Unavailable
Http Status Code : 504 Http Message : Gateway Timeout
Http Status Code : 511 Http Message : Network Authentication Required

Cloned Tree Map :
{100=Continue, 101=Switching Protocols, 102=Processing, 200=OK, 202=Accepted, 203=Non Authoritative Information, 300=Multiple Choices, 302=Moved Temporarily, 400=Bad Request, 401=Unauthorized, 405=Method Not Allowed, 409=Conflict, 422=Unprocessable Entity, 424=Failed Dependency, 429=Too Many Requests, 500=Server Error, 503=Service Unavailable, 504=Gateway Timeout, 511=Network Authentication Required}

Size of the httpStatusMap is 0

Iterate or Traverse over TreeMap

In this link I have discussed about different ways to traverse or Iterate over the TreeMap. you can find this post here.

What is difference between HashMap and TreeMap?

HashMap	TreeMap
HashMap can contain only one null key.	TreeMap can not contain any null key.
HashMap maintains no order.	TreeMap maintains ascending order on keys.
HashMap has implemented internally using Hashing.	TreeMap has implemented internally using Red-Black tree implementation.
HashMap take constant time performance for the basic operations like get and put i.e O(1).	TreeMap provides guaranteed log(n) time constant for the get and put method.
HashMap is much faster than TreeMap/	TreeMap is slower in comparison.
HashMap uses equals() method in comparison.	TreeMap uses compareTo and compare method based on Comparable natural ordering or Comparator accordingly.
HashMap is not reach in functionality as TreeMap. HashMap provides basic functionality.	TreeMap provides reach in functionality like pollFirstEntry() , pollLastEntry() , tailMap() , firstKey() , lastKey() etc.