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 is red black tree based implementation.
  • 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).

Hierarchy

treemap in java

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


Declaration:

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


Let’s see a java program storing key and value in treemap,

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

public class TreemapExample
{ 
   public static void main(String[] args) 
   {
      // declaring TreeMap
      TreeMap<Integer, String> tm = new TreeMap<Integer, String>();
      // adding elements to TreeMap
      tm.put(101, "Sachin");
      tm.put(203, "Virat");
      tm.put(700, "Dhoni");
      tm.put(401, "Shami");
      tm.put(201, "Rahul");
      // java treemap iterator
      Set set = tm.entrySet();
      Iterator iterate = set.iterator();
      while(iterate.hasNext()) 
      {
         Map.Entry mentry = (Map.Entry)iterate.next();
         System.out.print("Key : " + mentry.getKey() + " and Value : ");
         System.out.println(mentry.getValue());
      }
   }
}


Output :

Key : 101 and Value : Sachin
Key : 201 and Value : Rahul
Key : 203 and Value : Virat
Key : 401 and Value : Shami
Key : 700 and Value : Dhoni


Methods

Methods - modifierDescription
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.
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.
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()Returns a Collection view of the values contained in this map.

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


Reference – Oracle Docs

Also read – interface in java