TreeMap In Java – Tutorial With Java TreeMap Examples

This Java TreeMap Tutorial Discusses TreeMap Class, Iteration, TreeMap Examples, Implementation, Java Hashmap vs Treemap, TreeMap API Methods etc.:

A TreeMap data structure is a collection that stores key-value pairs in a naturally sorted order. A TreeMap is a part of the Java Collections Framework and is a map implementation.

=> Check ALL Java Tutorials Here.

TreeMap in Java

Java TreeMap

Some of the major characteristics of TreeMap in Java are as follows:

  • The TreeMap class that implements treemap in Java is a part of java.util package. It implements the Map interface.
  • The TreeMap class extends AbstractMap class and also implements the NavigableMap and SortedMap (indirectly) interface.
  • TreeMap is not synchronized.
  • By default, TreeMap elements are in ascending order by default.
  • TreeMap does not allow duplicate elements.
  • TreeMap allows null values but not null keys.

The below diagram shows the class hierarchy for the TreeMap class.

class hierarchy

As already mentioned, TreeMap class implements a NavigableMap interface that in turn extends the SortedMap class. SortedMap further inherits the map interface.

Declaration Of TreeMap Class

The general declaration of the TreeMap class is given below:

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

where K=> type of keys maintained by TreeMap

V=> type of the mapped values

TreeMap Example

The below program shows a simple example of a TreeMap data structure.

import java.util.*;  
class Main{  
 public static void main(String args[]){  
    //declare a TreeMap and initialize it
    TreeMap&lt;Integer,String&gt; cities_map=new TreeMap&lt;Integer,String&gt;();    
    cities_map.put(100,"Pune");    
    cities_map.put(102,"Jaipur");    
    cities_map.put(101,"Hyderabad");    
    cities_map.put(103,"Bangaluru");    
    //print the TreeMap contents using forEach
    System.out.println("Contents of TreeMap:");
    System.out.print("{");
    for(Map.Entry entries:cities_map.entrySet()){    
       System.out.print(entries.getKey()+" = "+entries.getValue() + " ");    
    }    
 
    System.out.println("}");
 }  
}  

Output:

Contents of TreeMap:
{100 = Pune 101 = Hyderabad 102 = Jaipur 103 = Bangaluru }

Output - TreeMap

In this program, we have defined a simple TreeMap object named, cities_map, and then using the put method, we have initialized it to key-value pairs.

Then we use the entrySet () method of TreeMap class and iterate over this set using a forEach loop to print the key-value pairs. For printing key-value pairs, we use getKey () and getValue () methods respectively.

TreeMap API Methods & Constructors

In this section, we will discuss the various constructors and methods provided by the TreeMap class.

Constructors

Constructor PrototypeDescription
TreeMap()Default constructor to create an empty TreeMap with natural ordering.
TreeMap ( Comparator < ? super K > comparator )Constructs an empty TreeMap which is sorted based on the specified comparator.
TreeMap ( Map < ? extends K,? extends V > m )Constructs a TreeMap and initialized it with the elements of the specified map, m. Ordering is natural.
TreeMap (SortedMap m )Constructs a TreeMap and initialized it with SortedMap entries. Ordering is the same as sortedMap.

Methods

MethodMethod PrototypeDescription
ceilingEntryMap.Entry < K,V > ceilingEntry ( K key )Returns the least key-value pair such that key is greater than or equal to specified key; null if there is no key
ceilingKeyK ceilingKey ( K key )Returns the key that is least and greater than the given key; returns null if no key.
clearvoid clear ()Deletes all the key-value pairs from the Treemap.
cloneObject clone ()Makes a shallow copy of TreeMap instance.
comparatorComparator < ? super K > comparator ()Returns a comparator used to arrange the keys. null if ordering is natural
descendingKeySetNavigableSet < K > descendingKeySet ()Returns NavigableSet view of the TreeMap keys in reverse order.
descendingMapNavigableMap < K,V > descendingMap ()Returns given key-value pairs in reverse order.
firstEntryMap.Entry firstEntry ()Returns the least key-value pair.
floorEntryMap.Entry < K,V > floorEntry (K key)Returns greatest key which is less than or equal to a given key; null if no such key
forEachvoid forEach (BiConsumer < ? super K,? super V > action )The given action is performed for each entry in the TreeMap.
headMapSortedMap < K,V > headMap (K toKey)Used to return a key-value pair such that the returned key is strictly less than toKey
headMapNavigableMap < K,V > headMap (K toKey, boolean inclusive )Returns key-value pairs of those keys that are less than the toKey or equal to if inclusive.
higherEntryMap.Entry < K,V > higherEntry (K key)Returns the least key or null. The returned key is strictly greater than the given key.
higherKeyK higherKey (K key)Returns the key if the mapping is present for the given key in the Treemap.
keySetSet keySet ()Returns the set collection of the keys in the TreeMap.
lastEntryMap.Entry < K,V > lastEntry ()Returns the key-value pair such that the key is the greatest key. Returns null if the key does not exist.
lowerEntryMap.Entry< K,V > lowerEntry (K key)Returns the key-value pair such that the key is greatest and strictly less than the given key. Returns null if the key does not exist.
lowerKeyK lowerKey (K key)Returns the greatest key or null. The returned key is strictly less than the given key.
navigableKeySetNavigableSet < K > navigableKeySet ()Returns the ‘NavigableSet’ of keys in the TreeMap.
pollFirstEntryMap.Entry < K,V > pollFirstEntry ()Removes and then returns the least key’s key-value pair.
pollLastEntryMap.Entry < K,V > pollLastEntry()Removes and returns the greatest key’s key-value pair.
putV put (K key, V value)Adds given key and value to the TreeMap.
putAllvoid putAll (Map < ? extends K,? extends V > map )All the key-value pairs from the given map are copied to the TreeMap.
replaceV replace ( K key, V value )Replaces or changes the value of the given key with the given value.
replaceboolean replace ( K key, V oldValue, V newValue )Replaces oldValue of the given key with newValue.
replaceAllvoid replaceAll ( BiFunction < ? super K, ? super V, ? extends V > function )Invokes the given function and replaces all the entries with the result of the function.
subMapNavigableMap < K,V > subMap (K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)Returns the key-value pairs of keys from ‘fromKey’ to ‘toKey’.
SortedMapSortedMap < K,V > subMap (K fromKey, K toKey)Returns key-value pairs for the range fromKey (inclusive) to toKey (exclusive).
tailMapSortedMap < K,V > tailMap (K fromKey)Returns key-value pairs such that the keys are greater than or equal to fromKey.
tailMapNavigableMap < K,V > tailMap (K fromKey, boolean inclusive)Returns key-value pairs for the keys equal to fromKey (inclusive = true) or greater than fromKey.
containsKeyboolean containsKey (Object key)Checks if there is a mapping for the given key in the Treemap. Returns true if yes.
containsValueboolean containsValue (Object value)Checks if there is a key mapped with the given value. Returns yes if true.
firstKeyK firstKey ()Returns the lowest key or the first key in the Sorted Map
getV get (Object key)Retrieves the value mapped to the given key
lastKeyK lastKey ()Returns last key or highest key in the sorted map.
removeV remove (Object key)Deletes the key-value pair for the given key in the TreeMap
entrySetSet < Map.Entry < K,V > > entrySet ()Returns the set for the given TreeMap.
sizeint size ()Returns size or the total number of key-value pairs in the TreeMap.
valuesCollection values ()Returns collection of the values for the TreeMap.

Iterating Through TreeMap

TreeMap consists of Key-value pairs. TreeMap class provides a method ‘entrySet’ that returns key-value pairs in the map. We can iterate through these entries using the forEach loop and display keys and values using getKey () and getValue () methods respectively.

This is shown in the below Java program:

import java.util.Map; 
import java.util.TreeMap; 
  
class Main { 
    public static void main(String[] arg){
        //declare and initialize TreeMap
        Map&lt;String, String&gt; colorsTree 
            = new TreeMap&lt;String, String&gt;(); 
        colorsTree.put("R", "Red"); 
        colorsTree.put("G", "Green"); 
        colorsTree.put("B", "Blue"); 
        colorsTree.put("M", "Magenta"); 
        System.out.println("The contents of TreeMap:");
        // retrieve set of map entries  using entrySet method
        for (Map.Entry&lt;String, String&gt; Map_entry : colorsTree.entrySet()) 
            //print key-value pairs using getKey() and getValue()
            System.out.println( "[" + Map_entry.getKey() 
                + "=&gt;" + Map_entry.getValue() + "]"); 
    } 
}

Output:

The contents of TreeMap:
[B=>Blue]
[G=>Green]
[M=>Magenta]
[R=>Red]

output

TreeMap Implementation In Java

The following Java program demonstrates the main method of the TreeMap class discussed above.

import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;
public class Main {
	public static void main(String[] args) {
		//declare a TreeMap Object and initialize it with values
		TreeMap&lt;Integer,String&gt; map = new TreeMap&lt;&gt;();
		for(int i=1;i&lt;=10;i++) {
			map.put(i, (i*i)+"");
		}
		System.out.println("Original Map:" + map);
		
		//lowerEntry, higherEntry
		Entry&lt;Integer,String&gt; entry = map.lowerEntry(4);
		System.out.println("Closest Lower Entry than 4:"+entry);
		entry = map.higherEntry(4);
		System.out.println("Closest Higher Entry than 4:"+entry);
		System.out.println("Closest Lower key than 4 :"+map.lowerKey(4));
		
		entry = map.floorEntry(6);
		System.out.println("Closest floor entry than 6: "+entry);
		entry = map.ceilingEntry(6);
		System.out.println("Closest ceiling Entry than 6 :"+entry);
		entry = map.firstEntry();
		System.out.println("TreeMap First Entry:"+entry);
		entry = map.lastEntry();
		System.out.println("TreeMap Last Entry:"+entry);
		Map&lt;Integer, String&gt; reversedMap = map.descendingMap();
		System.out.println("Reversed TreeMap: "+reversedMap);
		//pollFirstEntry, pollLastEntry
		entry = map.pollFirstEntry();
		System.out.println("TreeMap First Entry:"+entry);
		entry = map.pollLastEntry();
		System.out.println("TreeMap Last Entry:"+entry);
		//subMap
		Map&lt;Integer, String&gt; subMap = map.subMap(2, true, 6, true);
		System.out.println("Submap from 2 to 6: "+subMap);

		//headMap
		subMap = map.headMap(5, true);
		System.out.println("HeadMap: "+subMap);
        		//tailMap
		subMap = map.tailMap(5, true);
		System.out.println("TailMap: "+subMap);
	}
}

Output:

Original Map:{1=1, 2=4, 3=9, 4=16, 5=25, 6=36, 7=49, 8=64, 9=81, 10=100}
Closest Lower Entry than 4:3=9
Closest Higher Entry than 4:5=25
Closest Lower key than 4 :3
Closest floor entry than 6: 6=36
Closest ceiling Entry than 6 :6=36
TreeMap First Entry:1=1
TreeMap Last Entry:10=100
Reversed TreeMap: {10=100, 9=81, 8=64, 7=49, 6=36, 5=25, 4=16, 3=9, 2=4, 1=1}
TreeMap First Entry:1=1
TreeMap Last Entry:10=100
Submap from 2 to 6: {2=4, 3=9, 4=16, 5=25, 6=36}
HeadMap: {2=4, 3=9, 4=16, 5=25}
TailMap: {5=25, 6=36, 7=49, 8=64, 9=81}

output - Treemap Implementation

Sort TreeMap By Value

By Default, TreeMap is sorted based on the keys according to natural ordering. But if we want to sort the TreeMap according to the values, then we have to make use of the comparator to define the sorting.

The below Java program sorts the TreeMap by value.

import java.util.*;
class Main {
  //Method for sorting the TreeMap based on values
  public static &lt;K, V extends Comparable&lt;V&gt;&gt; Map&lt;K, V&gt; 
    sortTreeMap(final Map&lt;K, V&gt; map) {
    //define a comaprator to sort TreeMap on values
    Comparator&lt;K&gt; valueComparator = new Comparator&lt;K&gt;() {
      public int compare(K k1, K k2) {
        int compare = 
              map.get(k1).compareTo(map.get(k2));
        if (compare == 0) 
          return 1;
        else 
          return compare;
      }
    };
    //use the comparator to sort the TreeMap and return sortedTreeMap
    Map&lt;K, V&gt; sortedTreeMap = new TreeMap&lt;K, V&gt;(valueComparator);
    sortedTreeMap.putAll(map);
    return sortedTreeMap;
  }
  public static void main(String args[]) {
     //define and initialize the TreeMap
    TreeMap&lt;String, String&gt; treemap = new TreeMap&lt;String, String&gt;();
    treemap.put("R", "Red");
    treemap.put("G", "Green");
    treemap.put("B", "Blue");
    treemap.put("C", "Cyan");
    treemap.put("M", "Magenta");
     // call method sortTreeMap to sort the TreeMap
    Map sortedTreeMap = sortTreeMap(treemap);
     // Retrieve set of the entries on the sorted map
    Set set = sortedTreeMap.entrySet();
    System.out.println("The sorted TreeMap based on Values:");
    // Now define iterator on this set
    Iterator i = set.iterator();
    // Print TreeMap elements
    while(i.hasNext()) {
      Map.Entry me = (Map.Entry)i.next();
      System.out.print(me.getKey() + ": ");
      System.out.println(me.getValue());
    }
  }
}

Output:

The sorted TreeMap based on Values:
B: Blue
C: Cyan
G: Green
M: Magenta
R: Red

output - Sort by Value

Java Hashmap vs Treemap

Let’s see some of the major differences between a HashMap and TreeMap.

The below table shows these differences.

HashMapTreeMap
Implements the Map interface.Implements NavigableMap interface.
Uses hashing implementation techniqueUse a red-black tree for implementation
Does not maintain any order of containing elementsThe Keys in the treemap are already ordered as per natural ordering
Allows one null key and many null valuesAllows only null values but keys cannot be null
Performs basic operations, put and get in constant time.Take log (n) time to perform put and get operations
HashMap has limited functionality.TreeMap class provides lots of additional functionality that help us manipulate the data structure.
HashMap is much faster than TreeMap.TreeMap is slower
Uses equals () method for comparing.Uses compareTo () method for comparing.

Frequently Asked Questions

Q #1) What is TreeMap in Java?

Answer: TreeMap in Java is a collection of key-value pairs that are already sorted. It uses a red-black tree for implementation purposes. Java TreeMap implements the NavigableMap interface apart from the Map interface and also extends AbstractMap class.

Q #2) Why do we use TreeMap in Java?

Answer: The TreeMap is used in Java for implementing Map and NavigableMap interfaces and AbstractMap class. As the TreeMap keys are sorted as per the natural ordering, we can use this data structure for storing directory structure, tree hierarchies, etc.

Q #3) Which is better – HashMap or TreeMap?

Answer: HashMap is better than TreeMap. HashMap always takes constant time to perform basic operations while TreeMap takes log (n) time to perform these operations. When larger data objects are involved, HashMap performs faster when compared to TreeMap.

Q #4) Is TreeMap sorted?

Answer: Yes, the key entries in TreeMap are sorted according to natural ordering. TreeMap class also allows us to use a custom comparator to sort the TreeMap based on values.

Q #5) Is TreeMap thread-safe?

Answer: No, TreeMap is not a thread-safe collection.

Conclusion

In this tutorial, we discussed TreeMap in Java in detail. TreeMap is a collection of key-value pairs that implements map interface. It also implements a NavigableMap interface. The elements of the TreeMap are unique and no duplicates are allowed.

We saw the constructors and methods of TreeMap. We also implemented the TreeMap program and demonstrated the major methods of the TreeMap class. Then we discussed the differences between HashMap and TreeMap.

=> Visit Here To See The Java Training Series For All.