HashMap vs. TreeMap vs. Hashtable vs. LinkedHashMap

Map is one of the most important data structures in Java. In this post, we will see that how to use different types of maps, such as HashMap, TreeMap, HashTable and LinkedHashMap.

1. Overview Of Map:

There are 4 commonly used implementations of Map in Java SE - HashMap, TreeMap, Hashtable and LinkedHashMap. The implementations can be described as follows:

HashMap class:

  • A HashMap contains values based on the key. It implements the Map interface and extends AbstractMap class.
  • It contains only unique keys.
  • It may have one null key and multiple null values.
  • There is no ordering on keys or values.

LinkedHashMap class:

  • A LinkedHashMap contains values based on the key. It implements the Map interface and extends HashMap class.
  • LinkedHashMap preserves the insertion order.
  • It may have one null key and multiple null values.

TreeMap class:

  • A TreeMap contains values based on the key. It implements the NavigableMap interface and extends AbstractMap class.
  • TreeMap is implemented based on red-black tree structure, and it is ordered by the key.
  • It cannot have null key but can have multiple null values.

HashTable class:

  • Hashtable is synchronized, in contrast to HashMap. It has an overhead for synchronization. This is the reason that HashMap should be used if the program is thread-safe.
  • Hashtable doesn't allow key or value as null.

Now let us check some examples of each of these implementations:

1. HashMap

If the key of a HashMap is a self-defined object, then the equals() and hashCode() contract need to be followed.

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

class Car {
 String color;
 Car(String c) {
  color = c;
 }
 @Override
 public String toString() {
  return "Car color :: " + color;
 }
}

public class TestHashMap {
  public static void main(String[] args) {
	Map carMap = new HashMap();
	Car c1 = new Car("Red");
	Car c2 = new Car("White");
	Car c3 = new Car("Gray");
	Car c4 = new Car("White");

	carMap.put(c1, 10);
	carMap.put(c2, 15);
	carMap.put(c3, 5);
	carMap.put(c4, 20);

	// loop HashMap
	for (Entry entry : carMap.entrySet()) {
	  System.out.println(entry.getKey().toString() + " - " + entry.getValue());
    }
  }
}

Output:

Car color :: Gray - 5
Car color :: Red - 10
Car color :: White - 15
Car color :: White - 20

Note here, we added “White Car" twice by mistake, but the HashMap accepts it .By default, the hashCode() and equals() methods implemented in the Object class are used. The default hashCode() method gives distinct integers for distinct objects, and the equals() method only returns true when two references refer to the same object. Check out the hashCode() and equals() contract if this is not obvious to you.

Here Java treated c2 and c4 as different Objects as Object class’s default hashCode() and equals() methods identified them as different Objects.

The Car class should be defined as follows :

class Car {
 String color;
 Car(String c) {
	color = c;
 } 
 @Override
 public String toString() {
	return "Car color :: " + color;
 }
 @Override
 public int hashCode() {
  final int prime = 31;
  int result = 1;
  result = prime * result + ((color == null) ? 0 : color.hashCode());
  return result;
 }
 
 @Override
 public boolean equals(Object obj) {
	if (this == obj)
	  return true;
	if (obj == null)
	  return false;
	if (getClass() != obj.getClass())
	  return false;
	Car other = (Car) obj;
	if (color == null) {
	  if (other.color != null)
		return false;
	} else if (!color.equals(other.color))
	    return false;
	return true;
 }
}

Now the output is:

Car color :: Red - 10
Car color :: White - 20
Car color :: Gray - 5
Here c2 and c4 are identified as same objects. In this case Java uses our implementation of hashCode() and equals() methods from Car class. And as a result c2 is overwritten by c4.

2. TreeMap

A TreeMap is sorted by keys. Let's first take a look at the following example to understand the "sorted by keys" idea.

class Car{
  String color;
 
  Car(String c) {
	color = c;
  }
  public boolean equals(Object o) {
	return ((Car) o).color.equals(this.color);
  }
 
  public int hashCode() {
	return color.length();
  }
  public String toString(){	
	return color + " Car";
  }
}
 
public class TestTreeMap {
	public static void main(String[] args) {
	  Car c1 = new Car("red");
	  Car c2 = new Car("black");
	  Car c3 = new Car("white");
	  Car c4 = new Car("white");
 
	  Map<Car, Integer> treeMap = new TreeMap<Car, Integer>();
	  treeMap.put(c1, 10);
	  treeMap.put(c2, 15);
	  treeMap.put(c3, 5);
	  treeMap.put(c4, 20);
 
	  for (Entry<Car, Integer> entry : treeMap.entrySet()) {
		System.out.println(entry.getKey() + " - " + entry.getValue());
	  }
  }
}

Output:

Exception in thread "main" java.lang.ClassCastException: test.Car cannot be cast to java.lang.Comparable
	at java.util.TreeMap.put(Unknown Source)
	at collection.TestHashMap.main(TestHashMap.java:35)

Since TreeMaps are sorted by keys, the object for key has to be able to compare with each other, that's why it has to implement Comparable interface. For example, you use String as key, because String implements Comparable interface.

Let's change the Car, and make it comparable.

class Car implements Comparable{ 
  String color; 
  int price;   

  Car(String c, int p) { 
    color = c; 
    price = p; 
  }   
  public boolean equals(Object o) { 
   return ((Car) o).color.equals(this.color); 
  }   
  public int hashCode() { 
   return color.length(); 
  } 
  public String toString(){ 
   return color + " Car"; 
  }

  @Override 
  public int compareTo(Car o) { 
     return o.price - this.price; 
  } 
}   

public class TestTreeMap {
   public static void main(String[] args) { 
       Car c1 = new Car("red"); 
       Car c2 = new Car("black"); 
       Car c3 = new Car("white"); 
       Car c4 = new Car("white");   

       Map treeMap = new TreeMap(); 
       treeMap.put(c1, 10); 
       treeMap.put(c2, 15); 
       treeMap.put(c3, 5); 
       treeMap.put(c4, 20);  

       for (Entry entry : treeMap.entrySet()) { 
            System.out.println(entry.getKey() + " - " + entry.getValue());
       } 
   } 
}
red Car - 10
black Car - 15
white Car - 20

It is sorted by key, i.e., Car price in this case.

The reason is that TreeMap now uses compareTo() method to compare keys. Different prices make different cars!

3. Hashtable

The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.

4. LinkedHashMap

This class extends HashMap and maintains a linked list of the entries in the map, in the order in which they were inserted. This allows insertion-order iteration over the map. That is, when iterating a LinkedHashMap, the elements will be returned in the order in which they were inserted. You can also create a LinkedHashMap that returns its elements in the order in which they were last accessed. Check here the  LRU cache using LinkedHashMap

LinkedHashMap Example :

In this example we will show how to use the java.util.LinkedHashMap class. LinkedHashMap is an implementation of java.util.Map interface with predictable iteration order (the order of insertion) i.e. LinkedHashMap will iterate in the order in which the entries were put into the map.

This implementation differs from HashMap in the way that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map. The insertion order is not affected if a key is re-inserted into the map. Performance of LinkedHashMap is slightly below than that of HashMap, due to the added expense of maintaining the linked list.

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

public class LinkedHashMapExample {
  public static void main(String[] args) {

	// Map representing (Student, Total marks) as (key, value) pair
	Map linkedHashMap = new LinkedHashMap();
	linkedHashMap.put("Jonhy", new Double(91.98));
	linkedHashMap.put("Dijja", new Double(86.76));
	linkedHashMap.put("Tom", new Double(70.47));
	linkedHashMap.put("Chu Lien", new Double(93.91));
	linkedHashMap.put("Askiu", new Double(81.71));

	// Displaying the contents of the LinkedHashMap
	System.out.println("Contents of LinkedHashMap : " + linkedHashMap);

	// One of the ways of iterating over the map
	// Notice the order of the elements is same as the order of insertion
	System.out.println("\nValues of map after iterating over it : ");
	for (String key : linkedHashMap.keySet()) {
	  System.out.println(key + ":\t" + linkedHashMap.get(key));
	}

	// Getting the value for a particular key
	System.out.println("\nTotal marks of Askiu is : " + linkedHashMap.get("Askiu"));

	// Getting the size of the LinkedHashMap
	System.out.println("\nThe size of the LinkedHashMap is : " + linkedHashMap.size());

	// Checking whether the LinkedHashMap is empty
	System.out.println("\nIs LinkedHashMap empty? : " + linkedHashMap.isEmpty());

	// Checking whether Map contains a particular key or value
	System.out.println("\nLinkedHashMap contains Tom's marks ? : " + linkedHashMap.containsKey("Tom"));
	System.out.println("LinkedHashMap contains 99.0 as value? : " + linkedHashMap.containsValue(99.0));

	// Removing a particular value
	System.out.println("\nRemove entry for Tom : " + linkedHashMap.remove("Tom"));
	System.out.println("Content of LinkedHashMap removing Tom: " + linkedHashMap);

	// Clearing the LinkedHashMap
	linkedHashMap.clear();
	System.out.println("\nContent of LinkedHashMap after clearing: " + linkedHashMap);
  }
}

The output is:

Contents of LinkedHashMap : {Jonhy=91.98, Dijja=86.76, Tom=70.47, Chu Lien=93.91, Askiu=81.71}

Values of map after iterating over it : 
Jonhy:	91.98
Dijja:	86.76
Tom:	70.47
Chu Lien:	93.91
Askiu:	81.71

Total marks of Askiu is : 81.71

The size of the LinkedHashMap is : 5

Is LinkedHashMap empty? : false

LinkedHashMap contains Tom's marks ? : true
LinkedHashMap contains 99.0 as value? : false

Remove entry for Tom : 70.47
Content of LinkedHashMap removing Tom: {Jonhy=91.98, Dijja=86.76, Chu Lien=93.91, Askiu=81.71}

Content of LinkedHashMap after clearing: {}

 

 

MAP COLLECTIONS