Difference between Hashtable, HashMap, TreeMap and LinkedHashMap

Difference between Hashtable, HashMap, TreeMap and LinkedHashMap

TreeMap  

Map is one of the most important data structures and when we talk about Map all these 4 implementation classes (Hashtable, HashMap, TreeMap and LinkedHashMap) are most used. Hashtable, HashMap and LinkedHashMap are directly implements Map interface, but TreeMap implements Map interface through implementing SortedMap. Below are the few differences between these classes

• HashMap implemented as same as Hashtable except it is unsynchronized and permits null. As common both HashMap and Hashtable won't have any ordering on keys or values.
• TreeMap implemented based on red-black tree structure and it follows natural ordering on key. 
• LinkedHashMap is a subclass of HashMap and inherits all properties of HashMap class and additionally its ordering will based on insertion order.

NOTE:

• If we use any Map implementation classes and if the key is user-defined class Object then we need to override hashcode() and equals() methods. 
• Next when we use TreeMap, by default they are sorted by keys. If we use user-defined class Object for key, then to compare with each other we need to implement Comparable interface.

Next lets see simple examples for each classes. 

Hashtable:

import java.util.Hashtable;
import java.util.Iterator;
import java.util.Map;

public class MapTest {

 public static void main(String[] args) {

  Map<String, String> map = new Hashtable<String, String>();
  map.put("1", "one");
  map.put("2", "two");
  map.put("3", "three");
  map.put("4", "four");
  map.put("5", "five");

  Iterator<?> itr = map.entrySet().iterator();
  while (itr.hasNext()) {
   Map.Entry myMap = (Map.Entry) itr.next();
   System.out.println(myMap.getKey() + " : " + myMap.getValue());
  }
 }
}

OUTPUT:

5 : five
4 : four
3 : three
2 : two
1 : one

HashMap:

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class MapTest {

 public static void main(String[] args) {

  Map<String, String> map = new HashMap<String, String>();
  map.put("1", "one");
  map.put("2", "two");
  map.put("3", "three");
  map.put("4", "four");
  map.put("5", "five");

  Iterator<?> itr = map.entrySet().iterator();
  while (itr.hasNext()) {
   Map.Entry myMap = (Map.Entry) itr.next();
   System.out.println(myMap.getKey() + " : " + myMap.getValue());
  }
 }
}

OUPTUT:

3 : three
2 : two
1 : one
5 : five
4 : four

TreeMap:

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

public class MapTest {

 public static void main(String[] args) {

  Map<String, String> map = new TreeMap<String, String>();
  map.put("2", "two");
  map.put("3", "three");
  map.put("1", "one");
  map.put("4", "four");
  map.put("5", "five");

  Iterator<?> itr = map.entrySet().iterator();
  while (itr.hasNext()) {
   Map.Entry myMap = (Map.Entry) itr.next();
   System.out.println(myMap.getKey() + " : " + myMap.getValue());
  }
 }
}

OUTPUT:

1 : one
2 : two
3 : three
4 : four
5 : five

LinkedHashMap:

import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;

public class MapTest {

 public static void main(String[] args) {

  Map<String, String> map = new LinkedHashMap<String, String>();
  map.put("2", "two");
  map.put("3", "three");
  map.put("1", "one");
  map.put("4", "four");
  map.put("5", "five");

  Iterator<?> itr = map.entrySet().iterator();
  while (itr.hasNext()) {
   Map.Entry myMap = (Map.Entry) itr.next();
   System.out.println(myMap.getKey() + " : " + myMap.getValue());
  }
 }
}

OUTPUT:

2 : two
3 : three
1 : one
4 : four
5 : five

Sorting duplicate elements in single array

Sorting duplicate elements in single array

TreeMap  

There are lot of sorting algorithms like bubble sort, quick sort, insertion sort, rad-ix sort etc., But all these sorting algorithm gives array of elements in an ascending or descending order.  In point of interview if they ask to sort the array with all the duplicate elements should be placed at end of the array again with sorted sub arrays.

For example 

Input array : { 5, 6, 2, 4, 8, 3, 5, 1, 3, 4, 5, 2, 1, 5, 3 }

Output array : {1, 2, 3, 4, 5, 6, 8,    1, 2, 3, 4, 5,    3, 5,   5 }

If we see above output, input array has been sorted with sub arrays with all duplicate elements at last. So lets see simple java code with the help of Collection API to sort the given array as per above problem

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

public class DuplicateArraySort {

 public static void main(String[] args) {

  int array[] = { 5, 6, 2, 4, 8, 3, 5, 1, 3, 4, 5, 2, 1, 5, 3 };

  System.out.print("Before array sorting : ");
  printArray(array);

  Map<Integer, Integer> myMap = generateMap(array);
  Set<Integer> set = (Set<Integer>) myMap.keySet();

  for (int i = 0; i < array.length;) {

   Iterator<Integer> itr = set.iterator();

   while (itr.hasNext()) {
    int key = itr.next();
    if ((myMap.get(key)) > 0) {
     myMap.put(key, (myMap.get(key) - 1));
     array[i] = key;
     i++;
    }
   }
  }

  System.out.print("\nAfter array sorting : ");
  printArray(array);
 }

 public static Map<Integer, Integer> generateMap(int[] array) {

  Map<Integer, Integer> myMap = new TreeMap<Integer, Integer>();
  for (int i : array) {
   if (myMap.containsKey(i)) {
    myMap.put(i, myMap.get(i) + 1);
   } else {
    myMap.put(i, 1);
   }
  }
  return myMap;
 }

 public static void printArray(int[] array) {
  for (int i : array) {
   System.out.printf("%d, ", i);
  }
 }
}

OUTPUT:

Before array sorting : 5, 6, 2, 4, 8, 3, 5, 1, 3, 4, 5, 2, 1, 5, 3, 

After array sorting : 1, 2, 3, 4, 5, 6, 8, 1, 2, 3, 4, 5, 3, 5, 5, 

TreeMap using custom object sorting

TreeMap using custom object sorting

TreeMap  

We know that by default TreeMap will sort the values using key. Suppose if we need to sort the TreeMap using object stored in key part then we need to implement the Comparator interface and we need to @Override compare() method which will sort 2 Objects of key path and will give us the sorted output. 

Below single example will show you how to use custom Object sorting in TreeMap. TreeMap will take "Worker class instance" as key and "String name" as value. Where we need to sort the values using key based on the member variables in the Worker class. 

Class "MyNameComp" which implements the Comparator interface on "Worker" class and used to sort TreeMap based on name or salary. Below example will gives you sort on salary. Suppose if we need output based on name sorted then we need to un-comment "return obj1.getName().compareTo(obj2.getName());"

public class TreeMapUsingObjectSorting {
 
 public static void main(String a[]){
  TreeMap<Worker,String> map = new TreeMap<Worker, String>(new MyNameComp());
  map.put(new Worker("david",5000), "david");
  map.put(new Worker("joy",2000), "joy");
  map.put(new Worker("abel",7000), "abel");
  map.put(new Worker("ruby",9000), "ruby");
  
  for (Map.Entry<Worker, String> entry : map.entrySet()) {
   System.out.println("KEY : "+ entry.getKey() +" \t VALUE : "+entry.getValue());
  }
 }
}

public class Worker{
    
    private String name;
    private int salary;
    
    public Worker(String name, int salary){
        this.name = name;
        this.salary = salary;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getSalary() {
        return salary;
    }
    public void setSalary(int salary) {
        this.salary = salary;
    }
    /* Called by entry.getKey() 
       Overriding toString() method from super class Object
       Since key is Object we are return our own key value
    */
    public String toString(){
     //return super.toString();
     return "("+this.name+":"+this.salary+")";
    }
}

public class MyNameComp implements Comparator<Worker>{

 @Override
 public int compare(Worker obj1, Worker obj2) {
        
  // Sort TreeMap based on name
  //return obj1.getName().compareTo(obj2.getName());
  
  // Sort TreeMap based on salary
  if(obj1.getSalary() > obj2.getSalary()) return 1;
  else if(obj1.getSalary() < obj2.getSalary()) return -1;
  else return 0;
    } 
}

OUTPUT:

KEY : (joy:2000)   VALUE : joy
KEY : (david:5000)   VALUE : david
KEY : (abel:7000)   VALUE : abel
KEY : (ruby:9000)   VALUE : ruby

Using Java TreeMap

Using Java TreeMap

TreeMap  

Today we will see about one of the important interface in Java called Map interface. Map interface and derived classes are in java.util.Map package and Map uses simple data structure that contains Key and Value. Always key must be unique Object and its uses Hashing to identify the correct Key and corresponding Value in the Sequential array (Used to call as bucket). 

Under Map interface lot of derived classes and lets see TreeMap in this tutorial.

TreeMap:
       TreeMap is an important class which implements the Map interface. As same as HashMap TreeMap also uses the Key/ Value to store the data in a sorted order. TreeMap can be created in 2 ways as natural sorted order or custom sorted order by using Comparator. Below we will see small examples for all these types.

Example: TreeMap using natural sort.

public class TreeMapTest {
 public static void main(String[] args) {
  TreeMap<String, String> map = new TreeMap<String, String>();
  map.put("4", "Delhi");
  map.put("3", "Mumbai");
  map.put("5", "Chennai");
  map.put("1", "Culcutta");
  map.put("2", "Bangalore");
  
  // Sorted TreeMap
  System.out.println("Sorted TreeMap values....");
  for (Map.Entry<String, String> entry : map.entrySet()) {
   System.out.println("KEY : "+entry.getKey() +" - VALUE : "+entry.getValue());
  }
  
  // Getting size TreeMap
  System.out.println("\nSize of TreeMap :: "+map.size());
  
  // Contains Key in TreeMap
  System.out.println("\nKey Contains (15) : "+map.containsKey("15"));
  System.out.println("Key Contains (4) : "+map.containsKey("4"));
    
  // Contains Value in TreeMap
  System.out.println("\nValue Contains (Delhi) : "+map.containsValue("Delhi"));
  System.out.println("Value Contains (Ney York) : "+map.containsValue("New York"));
    
  // Getting Reversing TreeMap
  NavigableMap<String, String> revMap = map.descendingMap();
  System.out.println("\nReverse TreeMap values....");
  for (Map.Entry<String, String> entry : revMap.entrySet()) {
   System.out.println("KEY : "+entry.getKey() +" - VALUE : "+entry.getValue());
  }
  
  // Get sub portion of map to subMap
  SortedMap<String, String> subMap = map.subMap("2","4");
  System.out.println("\nSub portion TreeMap values....");
  for (Map.Entry<String, String> entry : subMap.entrySet()) {
   System.out.println("KEY : "+entry.getKey() +" - VALUE : "+entry.getValue());
  }
  
  // Getting first Key and Entry in TreeMap
  System.out.println("\nFirst Key in TreeMap : "+map.firstKey());
  System.out.println("First Entry in TreeMap : "+map.firstEntry());
  
  // Getting last Key and Entry in TreeMap
  System.out.println("\nLast Key in TreeMap : "+map.lastKey());
  System.out.println("Last Entry in TreeMap : "+map.lastEntry());
  
  // Removing data from TreeMap
  map.remove("3");
  System.out.println("\nTreeMap size after removing 1 element : "+map.size());
  
  // Checking TreeMap is empty or not
  System.out.println("\nTreeMap empty or not : "+map.isEmpty());
  
  // Clearing complete TreeMap
  map.clear();
  System.out.println("\nTreeMap size after clearing all values : "+map.size());
  System.out.println("TreeMap empty or not : "+map.isEmpty());
  
 }
}

OUTPUT:

Sorted TreeMap values....
KEY : 1 - VALUE : Culcutta
KEY : 2 - VALUE : Bangalore
KEY : 3 - VALUE : Mumbai
KEY : 4 - VALUE : Delhi
KEY : 5 - VALUE : Chennai

Size of TreeMap :: 5

Key Contains (15) : false
Key Contains (4) : true

Value Contains (Delhi) : true
Value Contains (Ney York) : false

Reverse TreeMap values....
KEY : 5 - VALUE : Chennai
KEY : 4 - VALUE : Delhi
KEY : 3 - VALUE : Mumbai
KEY : 2 - VALUE : Bangalore
KEY : 1 - VALUE : Culcutta

Sub portion TreeMap values....
KEY : 2 - VALUE : Bangalore
KEY : 3 - VALUE : Mumbai

First Key in TreeMap : 1
First Entry in TreeMap : 1=Culcutta

Last Key in TreeMap : 5
Last Entry in TreeMap : 5=Chennai

TreeMap size after removing 1 element : 4

TreeMap empty or not : false

TreeMap size after clearing all values : 0
TreeMap empty or not : true

In above example we can see automatically TreeMap sorted and also other methods in TreeMap class.

Next we will see simple example using custom sorting using Comparator.

Example: TreeMap using custom sort - Comparator.

public class TreeMapUsingCustomComparator {
 
 public static void main(String a[]){
  TreeMap<Worker,String> map = new TreeMap<Worker, String>(new MyNameComp());
  map.put(new Worker("david",5000), "david");
  map.put(new Worker("joy",2000), "joy");
  map.put(new Worker("abel",7000), "abel");
  map.put(new Worker("ruby",9000), "ruby");
  
  for (Map.Entry<Worker, String> entry : map.entrySet()) {
   System.out.println("KEY : "+ entry.getKey() +" \t VALUE : "+entry.getValue());
  }
 }
}

public class Worker{
    
    private String name;
    private int salary;
    
    public Worker(String name, int salary){
        this.name = name;
        this.salary = salary;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getSalary() {
        return salary;
    }
    public void setSalary(int salary) {
        this.salary = salary;
    }
    public String toString(){
        return "("+this.name+":"+this.salary+")";
    }
}

public class MyNameComp implements Comparator<Worker>{
    public int compare(Worker obj1, Worker obj2) {
        return obj1.getName().compareTo(obj2.getName());
    }
}

OUTPUT: 

KEY : (abel:7000)   VALUE : abel
KEY : (david:5000)   VALUE : david
KEY : (joy:2000)   VALUE : joy
KEY : (ruby:9000)   VALUE : ruby