Treemap in java

Let’s learn treemap in java.

Treemap in java

  • TreeMap class is member of java collection framework.
  • TreeMap class implements Map interface.
  • TreeMap retain ascending order.
  • Treemap implementation in java: TreeMap is red black tree based implementation and it is considered as complex algorithm.
  • TreeMap don’t allow “null” keys. Meanwhile different keys are related to various 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)


Let’s see a java program on treemap,

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

public class TreeMapExample 
{
   public static void main(String[] args) 
   {
      TreeMap tm = new TreeMap();    
      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

Object firstKey(): returns the first (lowest) key currently in this sorted map.

Object get(Object key): returns the value to which this map maps the specified key.

Object clone(): This method returns a shallow copy of this TreeMap instance.

void clear(): This method removes all mappings from this TreeMap and clears the map.

boolean containsKey(Object key): Returns true if this map contains a mapping for the specified key.

Also read – interface in java

boolean containsValue(Object value): Returns true if this map contains a mapping for the specified value.

NavigableSet descendingKeySet(): Returns a reverse order NavigableSet view of the keys contained in this map.

NavigableMap descendingMap(): Returns a reverse order view of the mappings contained in this map.

Set entrySet(): returns a Set() view of the mappings contained in this map.

Map.Entry firstEntry(): Returns a key value mapping associated with the least key in this map or null if the map is empty.

Map.Entry floorEntry(K key): Returns a key value mapping associated with the greatest key <= the given key or null if there is no such key.

K floorKey(K key): Returns the greatest key <= the given key or null if there is no such key.

Also read – treeset in java

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 headMap(K toKey): Returns a view of the portion of this map whose keys are strictly less than toKey.

NavigableMap 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.

Map.Entry higherKey(K key): Returns a key-value mapping associated with the least key strictly greater than the given key or null if there is no such key.

K higherKey(K key): Returns the least key strictly greater than the given key or null if there is no such key.

Set keySet(): Returns a Set view of the keys contained in this map.

Map.Entry lastEntry(): Returns a key-value mapping associated with the greatest key in this map or null if the map is empty.

Object lastKey(): Returns the last(highest) key currently in this map.

Map.Entry 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 navigableKeySet(): Returns a NavigableSet view of the keys contained in this map.

Map.Entry 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 pollLastEntry(): Removes and returns a key value mapping associated with the greatest key in this map or null if the map is empty.

Object put(Object key, Object value): This method is used to insert a mapping into a map.

void putAll(Map map): Copies all of the mappings from the specified map to this map.

Object 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 subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive): Returns a view of the portion of this map whose keys range fromKey to toKey.

SortedMap subMap(K fromKey, K toKey): Returns a view of the portion of this map whose keys range from fromKey, inclusive to toKey, exclusive.

SortedMap tailMap(K fromKey): Returns a view of the portion of this map whose keys are greater than or equal to fromKey.

NavigableMap 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.

Collection values()


Constructors:

  • TreeMap()

empty treemap is constructed. It will be sorted using natural order of its keys.


  • TreeMap(Map m)

used to initialize treemap with entries from ‘m’ and sorted using natural order of keys.


  • TreeMap(SortedMap sm)

this initializes treemap with entries from ‘sm’. It will be sorted in the same order as ‘sm’.


  • TreeMap(Comparator comp)

this constructs empty tree-based map which will be sorted using Comparator ‘comp’ object.


SortedMap example:

import java.util.SortedMap;
import java.util.TreeMap;

public class TreeMapDemo 
{
   public static void main(String[] args) 
   {
      SortedMap<Integer,String> sm = new TreeMap<Integer,String>(); 
      sm.put(100,"Ajinkya"); 
      sm.put(102,"Ravichandran"); 
      sm.put(101,"Virat"); 
      sm.put(103,"Ravindra"); 
      // return key-value pairs where keys are < specified key 
      System.out.println("headMap : " + sm.headMap(102)); 
      // return key-value pairs whose keys are >= specified key
      System.out.println("tailMap : " + sm.tailMap(102)); 
      // return key-value pairs existing in between the specified key 
      System.out.println("subMap : " + sm.subMap(100, 102));
   }
}



Output:

headMap : {100=Ajinkya, 101=Virat}
tailMap : {102=Ravichandran, 103=Ravindra}
subMap : {100=Ajinkya, 101=Virat}


NavigableMap example

import java.util.NavigableMap;
import java.util.TreeMap;

public class TreeMapExample 
{
   public static void main(String[] args) 
   {
      NavigableMap<Integer,String> nm = new TreeMap<Integer,String>(); 
      nm.put(100,"Ajinkya");
      nm.put(102,"Ravichandran"); 
      nm.put(101,"Virat"); 
      nm.put(103,"Ravindra"); 
      // descending order 
      System.out.println("descendingMap : " + nm.descendingMap()); 
      // return key-value pairs whose keys are < specified key 
      System.out.println("headMap : " + nm.headMap(102, true)); 
      // return key-value pairs whose keys are >= specified key 
      System.out.println("tailMap : " + nm.tailMap(102, true)); 
      // return key-value pairs existing in between specified key 
      System.out.println("subMap : " + nm.subMap(100, false, 102, true));
   }
}



Output:

descendingMap : {103=Ravindra, 102=Ravichandran, 101=Virat, 100=Ajinkya}
headMap : {100=Ajinkya, 101=Virat, 102=Ravichandran}
tailMap : {102=Ravichandran, 103=Ravindra}
subMap: {101=Virat, 102=Ravichandran}


remove() method example:

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

public class RemoveDemo 
{
   public static void main(String[] args) 
   {
      TreeMap<Integer,String> tm = new TreeMap<Integer,String>(); 
      tm.put(100,"Ajinkya"); 
      tm.put(102,"Ravichandran"); 
      tm.put(101,"Virat"); 
      tm.put(103,"Ravindra"); 
      System.out.println("Before using remove() method"); 
      for(Map.Entry m:tm.entrySet()) 
      { 
         System.out.println(m.getKey() + " " + m.getValue()); 
      } 
      tm.remove(102); 
      System.out.println("After using remove() method"); 
      for(Map.Entry m:tm.entrySet()) 
      { 
         System.out.println(m.getKey() + " " + m.getValue()); 
      }
   }
}



Output:

Before using remove() method
100 Ajinkya
101 Virat
102 Ravichandran
103 Ravindra
After using remove() method
100 Ajinkya
101 Virat
103 Ravindra


java treemap comparator

comparator method 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 comparator method (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 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 use comparator and some logic. 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 sortedByValues = new TreeMap(com);
      sortedByValues.putAll(m);
      return sortedByValues;
   }

   public static void main(String[] args) 
   {
      TreeMap fruits = new TreeMap();
      fruits.put("K1", "Jackfruit");
      fruits.put("K2", "Raspberry");
      fruits.put("K3", "Kiwifruit");
      fruits.put("K4", "Tangerine");
      fruits.put("K5", "Strawberry");
      // calling sortvalues method
      Map 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

treemap floorkey

Syntax:

public K floorKey(K key)

Returns:

the greatest key less than or equal to the given key,or null if there is no such key.

Throws:

ClassCastException – if the specified key cannot be compared with the keys currently in the map.

NullPointerException – if the specified key is nulland this map uses natural ordering, or its comparator does not permit null keys.

Example:

import java.util.TreeMap;

public class TreeMapFloorkeyExample 
{
   public static void main(String[] args) 
   {
      TreeMap<Integer, String> tm = new TreeMap<Integer, String>();
      tm.put(60, "apple"); 
      tm.put(10, "banana"); 
      tm.put(50, "cherry"); 
      tm.put(30, "fig"); 
      tm.put(80, "grape"); 
      tm.put(90, "kiwifruit"); 

      // printing values of TreeMap 
      System.out.println("TreeMap: " + tm.toString());
      // 110 is not available it returns 10 
      System.out.print("Floor entry of element 110 is: "); 
      System.out.println(tm.floorKey(110));
      // returns null
      System.out.print("Floor entry of element 0 is: "); 
      System.out.println(tm.floorKey(0));
   }
}


Output:

TreeMap: {10=banana, 30=fig, 50=cherry, 60=apple, 80=grape, 90=kiwifruit}
Floor entry of element 110 is: 90
Floor entry of element 0 is: null

Example on NullPointerException

import java.util.TreeMap;

public class TreeMapFloorkeyExample 
{
   public static void main(String[] args) 
   {
      TreeMap<Integer, String> tm = new TreeMap<Integer, String>();
      tm.put(60, "apple"); 
      tm.put(10, "banana"); 
      tm.put(50, "cherry"); 
      tm.put(30, "fig"); 
      tm.put(80, "grape"); 
      tm.put(90, "kiwifruit"); 
      // printing values of TreeMap 
      System.out.println("TreeMap: " + tm.toString());
      try 
      { 
         // passing null as parameter 
         // to floorKey() method
         System.out.println(tm.floorKey(null)); 
      } 
      catch (Exception ex) 
      { 
         System.out.println("Exception: " + ex); 
      }
   }
}


Output:

TreeMap: {10=banana, 30=fig, 50=cherry, 60=apple, 80=grape, 90=kiwifruit}
Exception: java.lang.NullPointerException

treemap ceilingkey

ceilingKey() method returns the least key greater than or equal to the given key,or null if there is no such key. Here’s the example,

import java.util.NavigableMap;
 import java.util.TreeMap;
 public class TreeMapCeilingkeyDemo 
 {
     public static void main(String[] args) 
     {
         NavigableMap<Integer, String> nm = new TreeMap<Integer, String>(); 
         nm.put(10, "apple");
         nm.put(20, "banana"); 
         nm.put(30, "cherry"); 
         nm.put(40, "fig"); 
         nm.put(60, "grape"); 
         nm.put(70, "kiwifruit");
         // 60 is least value > 5,
         // returned as key.
         System.out.println("Ceiling key for 50: " + nm.ceilingKey(50));
     }
 }


Output:

Ceiling key for 50: 60

Reference – Oracle Docs