TreeMap in Java


Java Java MapViews 1315

Java TreeMap is a class that implements the Map interface. It is a tree-based implementation that can store key-value data in sorted order efficiently. It is similar to HashMap but has a few differences which we will see towards the end of this tutorial.

TreeMap in Java

TreeMap stores values corresponding to its keys where the key should not be null while the values can be null if required. It maintains an ascending sorting order where the data should be unique and cannot contain duplicate values. It sorts in natural order based on the keys in ascending order. We can also sort the data using a comparator. It implements the Map and Navigable interface and extends the Abstract class.

TreeMap is not thread-safe since it is unsynchronized. It is present in the java.util where we need to import the java.util.TreeMap package to use the TreeMap.

TreeMap in Java

TreeMap constructor

The Java TreeMap class uses the below constructors:

ConstructorDescription
TreeMap()Creates an empty treeMap that will sorted in natural order using the keys
TreeMap(Comparator c)Creates an empty treeMap that will sort using the Comparator specified as parameter
TreeMap(Map m)Creates and initializes the treeMap with entries of Map m that is passed as parameter and sorts using the keys in natural order
TreeMap(SortedMap sm)Creates and initializes the treeMap with entries in the SortedMap sm and sorts in the same order as sm.

Example: TreeMap using map

The below example shows how to instantiate a treemap using Map. We can see that the entries are sorted in the ascending order based on the keys.

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class TreeMapConst {

  public static void main(String[] args) {
    Map<String,String> m = new HashMap<String,String>();
    m.put("red", "Apple");
    m.put("blue", "blueberry");
    m.put("green", "kiwi");

    TreeMap<String,String> tm = new TreeMap<String,String>(m);
    System.out.println(tm);

  }

}
{blue=blueberry, green=kiwi, red=Apple}

Example: TreeMap using SortedMap

The below example shows how to instantiate a treemap using SortedMap.

import java.util.SortedMap;
import java.util.TreeMap;
import java.util.concurrent.ConcurrentSkipListMap;

public class TreeMapConst {

  public static void main(String[] args) {
    
    SortedMap<String,String> sm = new ConcurrentSkipListMap<String,String>();
    sm.put("red", "Apple");
    sm.put("blue", "Blueberry");
    sm.put("green", "Kiwi");
    
    TreeMap<String,String> tm = new TreeMap<String,String>(sm);
    System.out.println(tm);
  }

}
{blue=Blueberry, green=Kiwi, red=Apple}

TreeMap Methods

The Java TreeMap supports the below methods.

MethodDescriptionParameters
Entry celingEntry(Integer key)Returns a key-value mapping of the least key that is greater than or equal to the specified key or returns null if there is no such keykey - key in the treemap that is used for comparing the greater key
Integer ceilingKey(Integer key)Returns the least key that is greater than or equal to the specified key or returns null if there is no such keykey - key in the treemap that is used for comparing the greater key
void clear()Removes all mapping in the TreeMap and it becomes empty
Object clone()Returns the shallow copy of the TreeMap
Comparator comparator()Returns the comparator used to order the keys else returns null if it uses natural sorting
boolean containsKey(Object key)Returns true if it contains mapping for the specified keykey - search key in the treemap
boolean containsValue(Object value)Returns true if the TreeMap contains mapping to the value with keyvalue - search value in the treemap
NavigableSet descendingKeySet()Returns a reverse order NaviagbleSet view of the keys in the TreeMap
NavigableMap descendingMap()Returns a reverse order view of the mappings in the treemap
Set<Entry> entrySet()Returns a set view of the mapping in the treemap
Entry firstEntry()Returns the key-value mapping of the least key in the treemap
Integer firstKey()Returns the first lowest key in the treemap
Entry floorEntry(Integer key)Returns the key-value mapping of the greatest key that is equal to less than the specified keykey - search key
Integer floorKey(Integer key)Returns the greatest key less than or equal to the specified keykey - search key
void forEach(Consumer action)Performs the specified action for each entry in the Treemapaction - action to be performed on each entry
String get(Object key)Returns the value associated with the specified key in the treemapkey - search key
String getOrDefault(Object key, String defaultValue)Returns the value associated with the specified key else returns the default string if not presentkey - search key
defaultValue - default value when key not found
SortedMap headMap(Integer toKey)Returns a view portion of the map whose key is strictly less than the specified toKeytoKey - search key
Navigable headMap(Integer toKey, Boolean inclusive)Returns a view portion of the map whose key is strictly less than or equal to the specified toKey
Entry higherKey(Integer key)Returns the mapping of the least key which is greater than or equal to the specified keykey - search key
Integer higherKey(Integer key)Returns the least key that is greater than or equal to the specified keykey - search key
Boolean isEmpty()Checks if the map is empty or not
Set keySet()Returns a set view of the keys in the treemap
Entry lastEntry()Returns the mapping of the greatest key in the treemap
Integer lastKey()Returns the greatest key in the treemap
Entry lowerEntry(Integer key)Returns the key-value of the greatest key less than the specified keykey - search key
Integer lowerKey(Integer key)Returns the greatest key less than the specified keykey - search key
NavigableSet navigableKeySet()Returns a NavigableSet view of the keys contained in the treemap
Entry pollFirstEntry()Removes and returns the mapping of the least key in the treemap
Entry pollLastEntry()Removes and returns the mapping of the highest key in the treemap
String put(Integer key, String value)Inserts the key-value mapping into the treemapkey - key to insert
value - value associated with the key
void putAll(Map m)Puts all the mapping of the entries specified in the mapm - map entries
String remove(Object key)Removes the mapping for the specified keykey - key to be removed
Boolean remove(Object key, Object value)Removes the entry for the specified key if it is mapped to any valuekey - key to be removed
value - value associated with the key
String replace(Integer key, String value)Replaces the mapping for the specified key only if it is mapped to a specific valuekey - search key
value - value to replace
boolean replace(Integer key,String oldValue,String newValue)Replaces the mapping for the specified key only if it is mapped to a specific valuekey - search key
oldValue - value of the key
newValue - value to replace
void replaceAll(BiFunction function)Replaces the value for each entry with the output of the functionfunction - function to compute the value
int size()Returns the size of the treemap which means the number of keys or entries
SortedMap subMap(Integer fromKey, Integer toKey)Returns a view of the portion of the map whose keys ranges from the fromKey inclusive to the toKey exclusivefromKey - starting key range (inclusive)
toKey - ending key range (exclusive)
NavigableMap subMap(Integer fromKey, boolean fromInclusive, Integer toKey, boolean toInclusive)Returns a view of the portion of the map whose keys ranges from the fromKey to the toKeyfromKey - starting key range
fromInclusive - denotes to include the fromKey
toKey - ending key range
toInclusive - denotes to include the toKey
SortedMap tailMap(Integer fromKey)Returns a view portion of the map whose keys are greater than the fromKeyfromKey - start key
NavigableMap tailMap(Integer fromKey, boolean inclusive)Returns a view portion of the map whose keys are greater than or equal to the fromKeyfromKey - start key
inclusive - denotes if from key has to be included in the range
Collection values()Returns a collection view of the values
String toString()Returns a string representation of the map

Example: Add elements to TreeMap

Below is the example that illustrates to add elements to a TreeMap using the put() method. As we saw earlier, the TreeMap displays the entries in the natural sorting order based on the keys.

import java.util.TreeMap;
public class TreeMapDemo {

  public static void main(String[] args) {
    TreeMap<Integer, String> tm = new TreeMap<Integer, String>();
    tm.put(111, "Aditya");
    tm.put(333, "Bharat");
    tm.put(222, "Dev");
    tm.put(555, "Hari");
    tm.put(444, "Charan");
    
    
    System.out.println(tm.toString());
  }

}
{111=Aditya, 222=Dev, 333=Bharat, 444=Charan, 555=Hari}

Example: Retrieve entries from TreeMap

In the below example, we can see how we can retrieve various entries in comparison with the specified key.

import java.util.Map.Entry;
import java.util.TreeMap;

public class RetrieveTreeMapEntries {

  public static void main(String[] args) {
    TreeMap<Integer, String> tm = new TreeMap<Integer, String>();
    tm.put(111, "Aditya");
    tm.put(333, "Bharat");
    tm.put(222, "Dev");
    tm.put(555, "Hari");
    tm.put(444, "Charan");
    Entry<Integer,String> eceiling = tm.ceilingEntry(222);
    System.out.println("Ceiling Entry: " + eceiling.getKey() + " " + eceiling.getValue());
    Entry<Integer,String> efloor = tm.floorEntry(222);
    System.out.println("Floor Entry: " + efloor.getKey() + " " + efloor.getValue());
    Entry<Integer,String> efirst = tm.firstEntry();
    System.out.println("First Entry: " + efirst.getKey() + " " + efirst.getValue());	
    Entry<Integer,String> elast = tm.lastEntry();
    System.out.println("Last Entry: " + elast.getKey() + " " + elast.getValue());	
    Entry<Integer,String> ehigh = tm.higherEntry(222);
    System.out.println("Higher Entry: " + ehigh.getKey() + " " + ehigh.getValue());
    Entry<Integer,String>elower = tm.lowerEntry(222);
    System.out.println("Lower Entry: " + elower.getKey() + " " + elower.getValue());
  }

}
Ceiling Entry: 222 Dev
Floor Entry: 222 Dev
First Entry: 111 Aditya
Last Entry: 555 Hari
Higher Entry: 333 Bharat
Lower Entry: 111 Aditya

Example: Retrieve keys in Java TreeMap

The below example shows you how to retrieve keys from a Java TreeMap in comparison with the specified key.

import java.util.TreeMap;
import java.util.Map.Entry;

public class RetrieveTreeMapKeys {

  public static void main(String[] args) {
    TreeMap<Integer, String> tm = new TreeMap<Integer, String>();
    tm.put(111, "Aditya");
    tm.put(333, "Bharat");
    tm.put(222, "Dev");
    tm.put(555, "Hari");
    tm.put(444, "Charan");
    
    System.out.println("Ceiling Key: " + tm.ceilingKey(222));
    System.out.println("Floor Key: " + tm.floorKey(222));
    System.out.println("First Key: " + tm.firstKey());
    System.out.println("Last Key: " + tm.lastKey());	
    System.out.println("Higher Key: " + tm.higherKey(222));
    System.out.println("Lower Key: " + tm.lowerKey(222));
   
  }

}
Ceiling Key: 222
Floor Key: 222
First Key: 111
Last Key: 555
Higher Key: 333
Lower Key: 111

Example: Remove entries from Java TreeMap

The below example illustrates how to remove entries from TreeMap using the remove() method. We can also remove the first and last entry alone using the pollFirstEntry() and pollLastEntry() methods.

import java.util.TreeMap;

public class RemoveEntriesTreeMap {

  public static void main(String[] args) {
    TreeMap<Integer, String> tm = new TreeMap<Integer, String>();
    tm.put(111, "Aditya");
    tm.put(333, "Bharat");
    tm.put(222, "Dev");
    tm.put(555, "Hari");
    tm.put(444, "Charan");
    
    System.out.println("Poll First Entry: " + tm.pollFirstEntry());
    System.out.println("Poll Last Entry: " + tm.pollLastEntry());
    
    System.out.println("Remove Key 222: " + tm.remove(222));
    System.out.println("Remove Entry 333: " + tm.remove(333, "Bharat"));
    
    System.out.println("Entries in the TreeMap after remove operation: " + tm);

  }

}
Poll First Entry: 111=Aditya
Poll Last Entry: 555=Hari
Remove Key 222: Dev
Remove Entry 333: true
Entries in the TreeMap after remove operation: {444=Charan}

Example: Check and retrieve key-value from Java TreeMap

The below example shows how to check if a treemap contains a given key or value using the containsKey() and containsValue() method. We can get a specific value using the get() or getOrDefault()and get all values using the values() method.

 import java.util.TreeMap;

public class TreeMapContains {

  public static void main(String[] args) {
    TreeMap<Integer, String> tm = new TreeMap<Integer, String>();
    tm.put(111, "Aditya");
    tm.put(333, "Bharat");
    tm.put(222, "Dev");
    tm.put(555, "Hari");
    tm.put(444, "Charan");
    
    System.out.println("Contains key: " + tm.containsKey(333));
    System.out.println("Contains key: " + tm.containsKey(123));
    System.out.println("Contains Value: " + tm.containsValue("Dev"));
    System.out.println("Contains Value: " + tm.containsValue("aaa"));
    System.out.println("Get: " + tm.get(555));
    System.out.println("Get or default: " + tm.getOrDefault(444, "Test"));
    System.out.println("Get or default: " + tm.getOrDefault(123, "Test"));
    System.out.println("Values: " + tm.values());

  }

}
Contains key: true
Contains key: false
Contains Value: true
Contains Value: false
Get: Hari
Get or default: Charan
Get or default: Test
Values: [Aditya, Dev, Bharat, Charan, Hari]

Example: Descending sorting

TreeMap sorts the data by default in the ascending order of keys. But we can sort them in descending order using the descendingKeySet() to sort the keys in reverse order and descendingMap() to sort the key-value pairs in the reverse order.

import java.util.TreeMap;

public class DescendingTreeMap {

  public static void main(String[] args) {
    TreeMap<Integer, String> tm = new TreeMap<Integer, String>();
    tm.put(111, "Aditya");
    tm.put(333, "Bharat");
    tm.put(222, "Dev");
    tm.put(555, "Hari");
    tm.put(444, "Charan");
    
    System.out.println(tm.descendingKeySet());
    System.out.println(tm.descendingMap());

  }

}
[555, 444, 333, 222, 111]
{555=Hari, 444=Charan, 333=Bharat, 222=Dev, 111=Aditya}

Example: Iterate through Java TreeMap

We can iterate through all entries in the TreeMap by using the entrySet() method. To get only the keys, we can use either the keySet() method or the navigableKeySet() method.

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

public class IterateTreeMap {

  public static void main(String[] args) {
    TreeMap<Integer, String> tm = new TreeMap<Integer, String>();
    tm.put(111, "Aditya");
    tm.put(333, "Bharat");
    tm.put(222, "Dev");
    tm.put(555, "Hari");
    tm.put(444, "Charan");
    
    System.out.println("Iterate using Entry Set:");
    for(Map.Entry<Integer,String> m: tm.entrySet())
      System.out.println(m.getKey() + " " + m.getValue());
    
    System.out.println("Iterate using KeySet: ");
    for(Integer i: tm.keySet())
      System.out.println(i + " " + tm.get(i));
    
    System.out.println("Iterate through NavigableKeySet: ");
    System.out.println(tm.navigableKeySet());
    
  }

}
Iterate using Entry Set:
111 Aditya
222 Dev
333 Bharat
444 Charan
555 Hari
Iterate using KeySet: 
111 Aditya
222 Dev
333 Bharat
444 Charan
555 Hari
Iterate through NavigableKeySet: 
[111, 222, 333, 444, 555]

Example: headMap, subMap and tailMap methods of Java TreeMap

Below is the example to retrieve a portion of the mapping of the given TreeMap. When we use headMap() method, it retrieves all the entries from the start until the specified key. The tailMap()method retrieves all the entries from the specified key until the end of the map. To retrieve a portion of the mapping entries, we use the subMap() method which returns the entries from the start to the end range specified.

import java.util.TreeMap;

public class TreeMapMethods {

  public static void main(String[] args) {
    TreeMap<Integer, String> tm = new TreeMap<Integer, String>();
    tm.put(111, "Aditya");
    tm.put(333, "Bharat");
    tm.put(222, "Dev");
    tm.put(555, "Hari");
    tm.put(444, "Charan");
    
    System.out.println("Output of headMap method:");
    System.out.println(tm.headMap(333));
    System.out.println(tm.headMap(333, true));
    System.out.println(tm.headMap(333, false));
    
    System.out.println("Output of tailMap method: ");
    System.out.println(tm.tailMap(333));
    System.out.println(tm.tailMap(333, true));
    System.out.println(tm.tailMap(333, false));
    
    System.out.println("Output of subMap method: ");
    System.out.println(tm.subMap(222, 444));
    System.out.println(tm.subMap(222, true, 444, true));
    System.out.println(tm.subMap(222, false, 444, false));
    System.out.println(tm.subMap(222, false, 444, true));
    System.out.println(tm.subMap(222, true, 444, false));

  }

}
Output of headMap method:
{111=Aditya, 222=Dev}
{111=Aditya, 222=Dev, 333=Bharat}
{111=Aditya, 222=Dev}
Output of tailMap method: 
{333=Bharat, 444=Charan, 555=Hari}
{333=Bharat, 444=Charan, 555=Hari}
{444=Charan, 555=Hari}
Output of subMap method: 
{222=Dev, 333=Bharat}
{222=Dev, 333=Bharat, 444=Charan}
{333=Bharat}
{333=Bharat, 444=Charan}
{222=Dev, 333=Bharat}

Example: Replace values in a Java TreeMap

We can replace a particular value in a Java treemap using the replace() method. If the specified key is not found, it does not replace the value and ignores the statement.

import java.util.TreeMap;

public class ReplaceTreeMap {

  public static void main(String[] args) {
    TreeMap<Integer, String> tm = new TreeMap<Integer, String>();
    tm.put(111, "Aditya");
    tm.put(333, "Bharat");
    tm.put(222, "Dev");
    tm.put(555, "Hari");
    tm.put(444, "Charan");
    
    tm.replace(333, "Banu");
    tm.replace(444, "Charan", "Chandru");
    tm.replace(123, "Test");
    System.out.println("Values after replace method: \n" + tm);

  }

}
Values after replace method: 
{111=Aditya, 222=Dev, 333=Banu, 444=Chandru, 555=Hari}

Difference between TreeMap and HashMap in Java

TreeMapHashMap
Maintains ascending orderDoes not maintain any order
Cannot contain null keyCan contain one null key
It is a tree structure based implementationIt is a hashtable based implementation
It does not allow null valuesIt allows multiple null values
Sorting is slowerSorting is faster
Uses red-black tree data structureIt uses a hashtable data structure

Reference

Translate ยป