Java Treemap

Hey guys!! Welcome to flower brackets blog. Today we are going to learn java treemap.

Basically a treemap is a map. So a map is one where we support different kinds of operations like get, put, remove, getvalue etc.

It allows you to put things in a key value pair and all operations are based on the keys. This is basically what a map is.

Well let’s first understand what exactly term “map” means and then later we learn about treemap.

What is map?

Map is an object. In map we can store key value pair.

Treemap In Java

Here you can see the example of map. Here key is “Player Code” value is “Player Name”.

For key 01 corresponding value is Mahendra Singh dhoni, for key 02 corresponding value is virat kohli, for key 03 corresponding value is rohit sharma and for key 04 corresponding value is shikhar dhawan.

Read Also – Parameter Passing And Returning A Value From A Method In Java

Each row is called a key value pair. First key value pair is ( 01, Mahendra singh dhoni ), second key value pair is ( 02, Virat Kohli ), third key value pair is ( 03, rohit sharma ) and fourth key value pair is ( 03, shikhar dhawan ).

By default treemap will arrange the key value pairs in ascending order of keys. Using key we can identify the corresponding value. Each key value pair is called entry.

Key should be unique. We cannot put duplicate key in the map.


Introduction : java treemap

Treemap is used to store key value pair. Each row is called key value pair. By default treemap will arrange the key value pairs in ascending order.

Treemap is one of the implementations of map. The most famous map implementation is hashmap but hashmap is one where the values are not stored in a sorted order.

That is where exactly treemap is different from a hashmap. Treemap on the other hand stores values in a sorted order.

It’s not the values actually the keys in a sorted order.

Hierarchy of Treemap Class

java treemap

Treemap class implements navigablemap interface. Navigablemap interface extends sortedmap interface. Sortedmap interface extends map interface.

Treemap class belongs to java.util package.

Class TreeMap< K,V >

Here you can see K comma V. K is a type of keys which we are planning to maintain in the treemap.

V is a type of values which we are planning to maintain in the treemap.

java.lang.Object
     java.util.AbstractMap<K,V>
          java.util.TreeMap<K,V>

Treemap class extends abstractmap class, abstractmap class extends object class.

Serializable, Cloneable, Map<K,V>, NavigableMap<K,V>, SortedMap<K,V>

Treemap features

Treemap class implements serializable interface, cloneable interface, map interface, navigablemap interface and sortedmap interface.

Tree map is used to store key and value pairs. For a given key we can find the corresponding value. Key must be unique but the values can be duplicated.

Treemap is same as hashmap. The only difference is treemap maintains ascending order and treemap is sorted according to the natural ordering of its keys.

If you want to sort using different order then you need to provide your own comparator at map creation time.

Treemap java won’t allow null key but it will allow multiple null values. Treemap implementation is not synchronized and treemap is red black tree based navigablemap implementation.

Treemap in java is not thread safe. It should be synchronized externally using Collections.synchronizedSortedMap(map) method. Hence affecting performance.

Treemap methods while getting key and values return iterator method which are fail-fast and if the map is structurally modified will throw a ConcurrentModificationException.


Java treemap example

In this treemap java example let’s see how to create simple treemap and add few key value pairs,

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

public class TreemapJavaExample 
{
   public static void main(String[] args) 
   {
      // here we are declaring TreeMap
      TreeMap<Integer, String> tmfruits = new TreeMap<Integer, String>();

      // here we are adding elements to TreeMap
      tmfruits.put(10, "Cherries");
      tmfruits.put(32, "Dewberries");
      tmfruits.put(80, "Apricots");
      tmfruits.put(44, "Bananas");
      tmfruits.put(24, "Eggfruit");

      // here we are displaying content using Iterator
      Set set = tmfruits.entrySet();
      Iterator iterate = set.iterator();
      System.out.println("Java treemap example : ");
      System.out.println("-------------------------------------");
      while(iterate.hasNext()) 
      {
         Map.Entry me = (Map.Entry)iterate.next();
         System.out.print("TreeMap key is : " + me.getKey() + " & TreeMap value is : ");
         System.out.println(me.getValue());
      }
   }
}

Output :

Java treemap example : 
-------------------------------------
TreeMap key is : 10 & TreeMap value is : Cherries
TreeMap key is : 24 & TreeMap value is : Eggfruit
TreeMap key is : 32 & TreeMap value is : Dewberries
TreeMap key is : 44 & TreeMap value is : Bananas
TreeMap key is : 80 & TreeMap value is : Apricots


Methods of treemap

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.

Methods inherited from class java.util.AbstractMap

equals, hashCode, isEmpty, toString

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Map

equals, hashCode, isEmpty


Treemap java constructors

Here we will discuss treemap constructors. Below is the first treemap constructor,

public TreeMap()

This (above) is the default one. Using this constructor we can create empty treemap and once you create empty treemap we can add key and values.

What treemap will do is, it will automatically arrange key and values in ascending order of keys. Here’s an example,

import java.util.TreeMap;

public class TreemapConstructorDemo 
{
   public static void main(String[] args) 
   {
      TreeMap<Integer, String> tm = new TreeMap<Integer, String>();
      tm.put(100, "Cherries");
      tm.put(300, "Dewberries");
      tm.put(400, "Apricots");
      tm.put(200, "Bananas");

      System.out.println("Java treemap examples : " + tm); 
   }
}

Output :

Java treemap examples : {100=Cherries, 200=Bananas, 300=Dewberries, 400=Apricots}


Second treemap constructor which accepts map

public TreeMap(Map<? extends K, ? extends V> m)

Map can be hashmap or linkedhashmap. Here’s an example,

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

public class TreemapConstructorExample 
{
   public static void main(String[] args) 
   {
      HashMap<Integer, String> hm = new HashMap<Integer, String>();
      hm.put(100, "Cherries");
      hm.put(300, "Dewberries");
      hm.put(400, "Apricots");
      hm.put(200, "Bananas");

      System.out.println("Java hashmap examples : " + hm + "\n");

      TreeMap<Integer, String> tm = new TreeMap<Integer, String>(hm);
      System.out.println("Java treemap examples : " + tm);
   }
}

Output :

Java hashmap examples : {400=Apricots, 100=Cherries, 200=Bananas, 300=Dewberries}

Java treemap examples : {100=Cherries, 200=Bananas, 300=Dewberries, 400=Apricots}


Third treemap constructor which accepts sortedmap

public TreeMap(SortedMap<K, ? extends V> m)

SortedMap can be treemap or ConcurrentSkipListMap.

Fourth treemap constructor which accepts Comparator object

public TreeMap(Comparator<? super K> comparator)

This treemap constructor create empty treemap instance and after that if we add a key value pairs then what this treemap will do is it will order the key and values in descending order of keys.

Because comparator has logic to arrange the keys in descending order.


Treeset – custom comparator (descending order)

Let’s learn treemap comparator example that orders treemap entries in descending order of keys. Here’s an example on how to create treemap,

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

public class TreemapComparatorDemo 
{
   public static void main(String[] args) 
   {
      // here we are creating a treemap
      // with a custom comparator - descending order
      SortedMap<String, String> country = new TreeMap<>(new Comparator<String>() 
      {
         @Override
         public int compare(String s1, String s2) 
         {
            return s2.compareTo(s1);
         }
      });

      // here we are adding new key-value pairs to a treemap
      country.put("CN", "CHINA");
      country.put("BE", "BELGIUM");
      country.put("AF", "AFGHANISTAN");
      country.put("DK", "DENMARK");
      country.put("FI", "FINLAND");

      // here we are printing the treemap
      // keys will be sorted based on the supplied comparator
      System.out.println(country);
   }
}

Output :

{FI=FINLAND, DK=DENMARK, CN=CHINA, BE=BELGIUM, AF=AFGHANISTAN}


Treeset – custom comparator (case insensitive order)

Here I’m going to demonstrate how to create case insensitive map by passing custom CASE_INSENSITIVE_ORDER comparator to given treemap ignoring case,

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

public class TreemapInsensitiveDemo 
{
   public static void main(String[] args) 
   {
      // here treemap with keys are sorted by ignoring case
      SortedMap<String, String> country = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
      country.put("CHINA", "cn");
      country.put("be", "belgium");
      country.put("AFGHANISTAN", "af");
      country.put("Denmark", "dk");

      // here keys will be sorted ignoring the case
      System.out.println(country);
   }
}

Output :

{AFGHANISTAN=af, be=belgium, CHINA=cn, Denmark=dk}


How to access entries of a TreeMap?

In this segment we going to look example on how to access entries of a treemap using treemap methods.

These are few methods namely size, key exists, first entry, last entry, lower than key and many more.

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

public class TreemapMethodsDemo 
{
   public static void main(String[] args) 
   {
      TreeMap<Integer, String> animal = new TreeMap<>();

      animal.put(10, "Rhinoceros");
      animal.put(50, "Hyena");
      animal.put(30, "Cheetah");
      animal.put(40, "Bear");
      animal.put(20, "Antelope");

      System.out.println("Java treemap example : " + animal);

      // here we are finding size of a treemap
      System.out.println("Total number of animals : " + animal.size());

      // here we are checking if a given key exists in a treemap
      Integer num = 40;
      if(animal.containsKey(num)) 
      {
         // getting value associated with a given key in a treemap
         String name = animal.get(num);
         System.out.println("Animal with num " + num + " : " + name);
      }
      else
      {
         System.out.println("Animal does not exist with num : " + num);
      }

      // here we are finding first and last entry
      System.out.println("First entry in animal treemap : " + animal.firstEntry());
      System.out.println("Last entry in animal treemap : " + animal.lastEntry());

      // here we are finding entry whose key is just less than the given key
      Map.Entry<Integer, String> meLow = animal.lowerEntry(20);
      System.out.println("Animal just below num 20 : " + meLow);

      // here we are finding entry whose key is just higher than the given key
      Map.Entry<Integer, String> meHigh = animal.higherEntry(20);
      System.out.println("Animal just above num 20 : " + meHigh);
   }
}

Output :

Java treemap example : {10=Rhinoceros, 20=Antelope, 30=Cheetah, 40=Bear, 50=Hyena}
Total number of animals : 5
Animal with num 40 : Bear
First entry in animal treemap : 10=Rhinoceros
Last entry in animal treemap : 50=Hyena
Animal just below num 20 : 10=Rhinoceros
Animal just above num 20 : 30=Cheetah


Treemap remove

In the below example we are going to learn removing entries from treemap using treemap methods namely remove key, remove first entry, remove last entry and many more.

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

public class TreemapRemoveDemo 
{
   public static void main(String[] args) 
   {
      TreeMap<String, String> subjectCodes = new TreeMap<>();

      subjectCodes.put("Technology", "TECN");
      subjectCodes.put("Computer Studies", "COMP");
      subjectCodes.put("Food Technology", "FOTE");
      subjectCodes.put("Art History", "ARTH");
      subjectCodes.put("Social Studies", "SOST");
      subjectCodes.put("Economics", "ECON");

      System.out.println("Java treemap example : " + subjectCodes);

      // here we are removing the mapping for a given key
      String subjectName = "Economics";
      String subjectCode = subjectCodes.remove(subjectName);
      if(subjectCode != null) 
      {
         System.out.println("Removed (" + subjectName + " => " + subjectCode + ") from the TreeMap. New TreeMap " + subjectCodes);
      } 
      else
      {
         System.out.println(subjectName + " does not exist, or it is mapped to a null value");
      }

      // here we are removing the mapping for the given key 
      // only if it is mapped to the given value
      subjectName = "Technology";
      boolean checkRemoved = subjectCodes.remove(subjectName, "TALN");
      System.out.println("Was the mapping removed for " + subjectName + "? : " + checkRemoved);

      // here we are removing first entry from the TreeMap
      Map.Entry<String, String> subFirst = subjectCodes.pollFirstEntry();
      System.out.println("Removed firstEntry : " + subFirst + ", New TreeMap : " + subjectCodes);

      // here we are removing last entry from the TreeMap
      Map.Entry<String, String> subLast = subjectCodes.pollLastEntry();
      System.out.println("Removed lastEntry : " + subLast + ", New TreeMap : " + subjectCodes);
   }
}

Output :

Java treemap example : {Art History=ARTH, Computer Studies=COMP, Economics=ECON, Food Technology=FOTE, Social Studies=SOST, Technology=TECN}
Removed (Economics => ECON) from the TreeMap. New TreeMap {Art History=ARTH, Computer Studies=COMP, Food Technology=FOTE, Social Studies=SOST, Technology=TECN}
Was the mapping removed for Technology? : false
Removed firstEntry : Art History=ARTH, New TreeMap : {Computer Studies=COMP, Food Technology=FOTE, Social Studies=SOST, Technology=TECN}
Removed lastEntry : Technology=TECN, New TreeMap : {Computer Studies=COMP, Food Technology=FOTE, Social Studies=SOST}


conclusion

So this is about treemap in java treemap. I will covering methods in treemap in coming posts.

You can subscribe to my blog flower brackets if you haven’t already.


Reference – Oracle help centre

Related Posts