Saturday 25 November 2017

Internal Implementation of TreeMap in Java

      We learned the internal working of HashMap in post of How HashMap works internally.  In this post, we can discuss about the internal working of TreeMap in Java.

What is TreeMap ? 

    TreeMap class is a like HashMap which stores a key-value pairs. The major difference is that TreeMap sorts the key in ascending order.

   TreeMap is sorted according to the natural ordering of it's keys, or by a Comparator provided at map creation time, depending on which constructor is used. There are mainly two types of
constructor in TreeMap, 

         TreeMap();
         TreeMap(Comparator comp);

How TreeMap works internally ?


         TreeMap is Red-Black tree based NavigableMap implementation. In other words, it sorts the TreeMap object keys using Red-Black tree algorithm.

Red-Black Tree algorithm:--

       Red-Black tree is a self balancing Binary Search Tree(BST) where every node follows some rules,
  • Every node has color either Red or Black.
  • Root of tree is always black.
  • There are no two adjacent red nodes.
  • Every path from root to a null node has same number of black nodes.  

Red-Black Tree
Red-Black Tree

          Time Complexity of TreeMap of search i.e  get, put and remove is O(log n) . 
         Being a self balancing, we keep inserting and deleting entries, tree growing longer on one edge or shorter on the other side.
         This would mean that an operation would take a shorter time on the shorter branch and longer time on the other branch which is furthest from the root, something we would not want to happen. Therefore this is taken care of in the design of Red-Black trees.


TreeMap Examples :


Simple String as key example,

package com.test;

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

public class TreeMapEx {
    public static void main(String[] args) {
         TreeMap<String, Integer> treeMap = new TreeMap<String, Integer>();
         treeMap.put("Mahesh", 1);
         treeMap.put("Anil", 9);
         treeMap.put("John", 3);
         for(Map.Entry<String, Integer> map : treeMap.entrySet()) {
              System.out.println(map.getKey());
         }
    }
}
 
Output :-- Anil
           John
           Mahesh

 

Example to sort keys in TreeMap using Comparator with custom object.


package com.test;

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

public class TreeMapSorting {
      public static void main(String[] args) {
           TreeMap<Employee, String> treeMap = new TreeMap<Employee, String>(new MyNameComp());
           treeMap.put(new Employee(10,  "Anil"), "one");
           treeMap.put(new Employee(10,  "Mahesh"), "two");
           treeMap.put(new Employee(10,  "John"), "three");
           treeMap.put(new Employee(10,  "Nagesh"), "four");
           for (Map.Entry<Employee, String> map : treeMap.entrySet()) {
                   System.out.println("Key : ("+map.getKey()+ "), Value : "+ map.getValue());
           }
      }
}
 
class Employee {
      private Integer id;
      private String name;
      public Employee(Integer id, String name) {
           this.id = id;
           this.name = name;
      }
      public Integer getId() {
           return id;
      }
      public void setId(Integer id) {
           this.id = id;
      }
      public String getName() {
           return name;
      }
      public void setName(String name) {
           this.name = name;
      }
      public String toString() {
           return this.name+":"+id;
      }
}

class MyNameComp implements Comparator<Employee> {

        public int compare(Employee o1, Employee o2) {
               return o1.getName().compareTo(o2.getName());
        }
 
}
 
Output :--  
Key : (Anil:10), Value : one
Key : (John:10), Value : three
Key : (Mahesh:10), Value : two
Key : (Nagesh:10), Value : four 
 


Related Posts:-- 
1) How HashMap works internally in Java? 
2) Internal implementation of ArrayList in Java  
3) Collection Related Interview Questions and Answers in Java(List,Map & Set)
4) Internal Implementation of LinkedList in Java 
5) Difference between Loose Coupling and Tight Coupling in Java With Examples.
6) String Interview Questions and Answers 
7) Factory Design Pattern in Java

2 comments:

  1. Hi There,


    Nice to be visiting your blog again, it has been months for me. Well this article that i’ve been waited for so long.

    I created a GUI with NetBeans.
    When I run the program in XP and the program changes the button colors, the whole button changes color. In this case, from "background" to "Green".
    When I run the program under Windows 8 only the border of the button becomes green.

    See attached.

    NetBeans seems to use the Look and Feel "nimbus". I single stepped through the program on both computers and it looks like a request for nimbus does not cause an exception on either computer.

    Any ideas?






    It was cool to see your article pop up in my google search for the process yesterday. Great Guide.
    Keep up the good work!



    Thank you,
    Irene Hynes

    ReplyDelete
  2. well explained .There is also good treemap exaples visit Treemap Tutorial

    ReplyDelete