TreeMap in java

Let’s learn treemap in java.

TreeMap in java

  • TreeMap is a member of java collections framework.
  • TreeMap implements Map interface.
  • TreeMap maintain its entries in ascending order.
  • Treemap implementation in java: TreeMap is red black tree based NavigableMap implementation.
  • TreeMap doesn’t allow null key. However allow multiple null values.
  • TreeMap is sorted according to natural ordering of its keys and it is sorted in ascending order of its keys.
  • TreeMap contain only unique elements.
  • TreeMap implementation is not synchronized. Because if map access multiple threads concurrently then one of the threads should be accessed externally using SortedMap sm = Collections.synchronizedSortedMap(new TreeMap).

Declaration: TreeMap class

java.util.TreeMap class

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

Parameters

K: type of keys.

V: type of mapped values.


Hierarchy

treemap in java

Treemap class belongs to java.util package. This class implements NavigableMap and SortedMap and extends AbstractMap.


treemap complexity

treemap complexity of O(logN) for lookup and insertion.


Let’s see TreeMap in java with example.

import java.util.Map;
import java.util.TreeMap;
public class TreeMapExample
{
   public static void main(String[] args) 
   {
      TreeMap<Integer, String> tm = new TreeMap<Integer, String>();    
      tm.put(1000, "Apple");    
      tm.put(1002, "Raspberry");    
      tm.put(1001, "Velvet apple");    
      tm.put(1003, "Banana");    
      for(Map.Entry obj : tm.entrySet())
      {    
         System.out.println(obj.getKey() + " " + obj.getValue());    
      }
   }
}


Output:

1000 Apple
1001 Velvet apple
1002 Raspberry
1003 Banana


Methods of treemap

MethodDescription
K firstKey()returns the first (lowest) key currently in this map.
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.
Object clone()returns a shallow copy of this TreeMap instance.
void clear()removes all of the mappings from this map.
boolean containsKey(Object key)returns true if this map contains a mapping for the specified key.
boolean containsValue(Object value)returns true if this map maps one or more keys to the specified value.
NavigableSet<K> descendingKeySet()Returns a reverse order NavigableSet view of the keys contained in this map.
NavigableMap<K,V> descendingMap()returns a reverse order view of the mappings contained in this map.
Set<Map.Entry<K,V>> entrySet()returns a Set view of the mappings contained in this map.
Map.Entry<K,V> firstEntry()returns a key-value mapping associated with the least key in this map, or null if the map is empty.
Map.Entry<K,V> floorEntry(K key)returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.
K floorKey(K key)returns the greatest key less than or equal to the given key, or null if there is no such key.
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.
SortedMap<K,V> headMap(K toKey)returns a view of the portion of this map whose keys are strictly less than toKey.
NavigableMap<K,V> headMap(K toKey, boolean inclusive)returns a view of the portion of this map whose keys are less than (or equal to, if inclusive is true) toKey.
K higherKey(K key)returns the least key strictly greater than the given key, or null if there is no such key.
Set<K> keySet()returns a Set view of the keys contained in this map.
Map.Entry<K,V> lastEntry()returns a key-value mapping associated with the greatest key in this map, or null if the map is empty.
K lastKey()returns the last (highest) key currently in this map.
Map.Entry<K,V> lowerEntry(K key)returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key.
K lowerKey(K key)returns the greatest key strictly less than the given key, or null if there is no such key.
NavigableSet<K> navigableKeySet()returns a NavigableSet view of the keys contained in this map.
Map.Entry<K,V> pollFirstEntry()removes and returns a key-value mapping associated with the least key in this map, or null if the map is empty.
Map.Entry<K,V> pollLastEntry()removes and returns a key-value mapping associated with the greatest key in this map, or null if the map is empty.
V put(K key, V value)Associates the specified value with the specified key in this map.
void putAll(Map<? extends K,? extends V> map)copies all of the mappings from the specified map to this map.
V remove(Object key)removes the mapping for this key from this TreeMap if present.
int size()returns the number of key-value mappings in this map.
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)returns a view of the portion of this map whose keys range from fromKey to toKey.
SortedMap<K,V> subMap(K fromKey, K toKey)returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive.
SortedMap<K,V> tailMap(K fromKey)returns a view of the portion of this map whose keys are greater than or equal to fromKey.
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive)returns a view of the portion of this map whose keys are greater than (or equal to, if inclusive is true) fromKey.
K ceilingKey(K key)returns the least key greater than or equal to the given key, or null if there is no such key.

Also read – interface in java

Also read – treeset in java


Treemap constructors

TreeMap(): empty treemap is constructed. It will be sorted using natural order of its keys.

Let’s see an example on TreeMap() constructor.

import java.util.TreeMap;
public class TreemapConstructor
{
   static void ConstructorDemo()
   {
      // creating an empty TreeMap
      TreeMap<Integer, String> tm = new TreeMap<Integer, String>();
      tm.put(14, "Hello");
      tm.put(23, "World");
      tm.put(32, "Java");
      tm.put(41, "Flower");
      tm.put(50, "Brackets");
      // printing TreeMap
      System.out.println("TreeMap: " + tm);
   }
   public static void main(String[] args)
   {
      System.out.println("TreeMap() constructor example: ");
      ConstructorDemo();
   }
}


Output:

TreeMap() constructor example:
TreeMap: {14=Hello, 23=World, 32=Java, 41=Flower, 50=Brackets}


TreeMap(Map m): used to initialize treemap with entries from ‘m’ and sorted using natural order of keys.

Example:

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
public class TreemapConstructor
{
   static void ConstructorDemo()
   {
      // creating a Map
      Map<Integer, String> hm = new HashMap<Integer, String>();
      hm.put(14, "Hello");
      hm.put(23, "World");
      hm.put(32, "Java");
      hm.put(41, "Flower");
      hm.put(50, "Brackets");
      // creating TreeMap using Map
      TreeMap<Integer, String> tm = new TreeMap<Integer, String>(hm);
      // printing TreeMap
      System.out.println("TreeMap: " + tm);
   }
   public static void main(String[] args)
   {
      System.out.println("TreeMap(Map) constructor example: ");
      ConstructorDemo();
   }
}


Output:

TreeMap(Map) constructor example:
TreeMap: {14=Hello, 23=World, 32=Java, 41=Flower, 50=Brackets}


TreeMap(SortedMap sm): this constructor initializes treemap with entries from ‘sm’. It will be sorted in the same order as ‘sm’.

Example:

import java.util.SortedMap;
import java.util.TreeMap;
import java.util.concurrent.ConcurrentSkipListMap;
public class TreemapConstructor
{
   static void ConstructorDemo()
   {
      SortedMap<Integer, String> sm = new ConcurrentSkipListMap<Integer, String>();
      sm.put(14, "Hello");
      sm.put(23, "World");
      sm.put(32, "Java");
      sm.put(41, "Flower");
      sm.put(50, "Brackets");
      // creating TreeMap using SortedMap
      TreeMap<Integer, String> tm = new TreeMap<Integer, String>(sm);
      // printing TreeMap
      System.out.println("TreeMap: " + tm);
   }
   public static void main(String[] args)
   {
      System.out.println("TreeMap(SortedMap sm) example: ");
      ConstructorDemo();
   }
}


Output:

TreeMap(SortedMap sm) example:
TreeMap: {14=Hello, 23=World, 32=Java, 41=Flower, 50=Brackets}


TreeMap(Comparator comp): this constructor constructs empty tree-based map which will be sorted using Comparator ‘comp’ object.

Example:

import java.util.Comparator;
import java.util.TreeMap;
class Employee
{
   int ID;
   String name, address;
   // Constructor
   public Employee(int ID, String name, String address)
   {
      this.ID = ID;
      this.name = name;
      this.address = address;
   }
   // display employee details in main()
   public String toString()
   {
      return this.ID + " " + this.name + " " + this.address;
   }
}
// Comparator implementation
class SortbyID implements Comparator<Employee>
{
   // sorting in ascending order of ID
   public int compare(Employee a, Employee b)
   {
      return a.ID - b.ID;
   }
}
public class TreemapConstructor
{
   // second constructor
   static void ConstructorDemo()
   {
      TreeMap<Employee, Integer> tm = new TreeMap<Employee, Integer>(new SortbyID());
      tm.put(new Employee(230, "virat", "bengaluru"), 2);
      tm.put(new Employee(410, "rohit", "chennai"), 3);
      tm.put(new Employee(140, "dhoni", "mumbai"), 1);
      System.out.println("TreeMap: " + tm);
   }
   public static void main(String[] args)
   {
      System.out.println("TreeMap(Comparator comp) example: ");
      ConstructorDemo();
   }
}


Output:

TreeMap(Comparator comp) example:
TreeMap: {140 dhoni mumbai=1, 230 virat bengaluru=2, 410 rohit chennai=3}


java treemap comparator

TreeMap comparator() method in java returns the comparator used to order the keys in this map, or null if this map uses the natural ordering of its keys.

Here’s the example on java TreeMap comparator() method for natural ordering.

import java.util.Comparator;
import java.util.NavigableMap;
import java.util.TreeMap;
public class TreemapComparatorExample 
{
   public static void main(String[] args) 
   {
      NavigableMap<Integer, String> nm = new TreeMap<Integer, String>();
      // populating tree map
      nm.put(101, "apple"); 
      nm.put(102, "banana"); 
      nm.put(103, "apricot"); 
      nm.put(104, "blackberry"); 
      nm.put(105, "avocado"); 
      // printing TreeMap 
      System.out.println("TreeMap: " + nm);
      // using comparator() method
      Comparator c = nm.comparator();
      // print comparator value
      System.out.println("Comparator value: " + c);
   }
}


Output:

TreeMap: {101=apple, 102=banana, 103=apricot, 104=blackberry, 105=avocado}
Comparator value: null


Now let’s learn above example in reverse order.

import java.util.Collections;
import java.util.Comparator;
import java.util.NavigableMap;
import java.util.TreeMap;
public class TreemapComparatorExample 
{
   public static void main(String[] args) 
   {
      NavigableMap<Integer, String> nm = new TreeMap<Integer, String>(Collections.reverseOrder());
      // populating tree map
      nm.put(101, "apple"); 
      nm.put(102, "banana"); 
      nm.put(103, "apricot"); 
      nm.put(104, "blackberry"); 
      nm.put(105, "avocado"); 
      // printing TreeMap 
      System.out.println("TreeMap: " + nm);
      // using comparator() method
      Comparator c = nm.comparator();
      // print comparator value
      System.out.println("Comparator value: " + c);
   }
}


Output:

TreeMap: {105=avocado, 104=blackberry, 103=apricot, 102=banana, 101=apple}
Comparator value: java.util.Collections$ReverseComparator@15db9742


java treemap sort by value

To sort a treemap by value we have to build some logic using comparator. Here’s the example,

import java.util.Comparator;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
public class TreeMapByValue 
{
   public static <K, V extends Comparable<V>> Map<K, V> sortValues(final Map<K, V> m) 
   {
      Comparator<K> com = new Comparator<K>()
      {
         public int compare(K k1, K k2) 
         {
            int compare = m.get(k1).compareTo(m.get(k2));
            if(compare == 0)
            {
               return 1;
            }
            else
            {
               return compare;
            }
         }
      };
      Map<K, V> sortedByValues = new TreeMap<K, V>(com);
      sortedByValues.putAll(m);
      return sortedByValues;
   }
   public static void main(String[] args) 
   {
      TreeMap<String, String> fruits = new TreeMap<String, String>();
      fruits.put("K1", "Jackfruit");
      fruits.put("K2", "Raspberry");
      fruits.put("K3", "Kiwifruit");
      fruits.put("K4", "Tangerine");
      fruits.put("K5", "Strawberry");
      // calling sortvalues method
      Map<String, String> sortedMap = sortValues(fruits);
      Set set = sortedMap.entrySet();
      Iterator iterate = set.iterator();
      // print elements
      while(iterate.hasNext()) 
      {
         Map.Entry ma = (Map.Entry)iterate.next();
         System.out.print(ma.getKey() + ": ");
         System.out.println(ma.getValue());
      }
   }
}


Output:

K1: Jackfruit
K3: Kiwifruit
K2: Raspberry
K5: Strawberry
K4: Tangerine


iterate treemap in java

Let’s learn how to iterate treemap in java. We cannot iterate TreeMap in java.

Since TreeMap is not a collection. To iterate use entrySet() method of TreeMap class.

import java.util.Map;
import java.util.TreeMap;
public class IterateTreeMap
{
   public static void main(String[] args)
   {
      Map<String, String> tm = new TreeMap<String, String>();
      tm.put("Audi", "Audi A8 L");
      tm.put("BMW", "BMW 5 Series");
      tm.put("Mercedes-Benz", "Mercedes-Benz V-Class");
      tm.put("Bugatti", "Bugatti Chiron");
      // using for-each loop iterate over TreeMap using entrySet() method
      for(Map.Entry<String, String> entry : tm.entrySet())
         System.out.println("[" + entry.getKey() + ", " + entry.getValue() + "]");
   }
}


Output:

[Audi, Audi A8 L]
[BMW, BMW 5 Series]
[Bugatti, Bugatti Chiron]
[Mercedes-Benz, Mercedes-Benz V-Class]


Reference – Oracle Docs