Difference between hashmap, hashtable, linkedhashmap and treemap

Java collections Map Interface have multiple implementations. Different types of maps, such as HashMap, TreeMap, HashTable and LinkedHashMap.

java Map interface hierarchy

What is Map?

  • Map is an interface which is used to store key, value pairs.
  • The typical operation for a Map is get() and put().
  • To store and get the element Map uses hashcode() and equal() method. How hashcode and equals work
  • If a same key is used multiple times for put() method the value will be overwritten at each operation.

HashMap

It is most commonly used and basic implementation of Map interface. While traversing the Map, the order of traversal is not same as insertion. So there is not gurantee of order. The get() and put() takes O(1) time whereas traversal of all elements is done using java.util.Iterator in O(n) time.

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

public class UseHashMap {

	public static void main(String[] args) {
		//Create a HashMap and store elements in the Map
		 Map<String, Integer> days = new HashMap<String, Integer>();
		 days.put("Sunday", 1);
		 days.put("Monday", 2);
		 days.put("Tuesday", 3);
		 days.put("Wednesday", 4);
		 days.put("Thursday", 5);
		 days.put("Friday", 6);
		 days.put("Saturday", 7);
		 
		 //get elements from the Map
		 System.out.println("Sunday is " + days.get("Sunday"));
		 System.out.println("If key not present value is " + days.get("ABC"));
		 
		 //Iterate all elements
		 for(Entry<String, Integer> entry : days.entrySet()) {
		   System.out.println(entry.getKey() + "\t" + entry.getValue());
		 }
		 //Iterate using keys
		 Iterator<String> keys = days.keySet().iterator();
		 while(keys.hasNext()) {
		   String key = keys.next();
		   System.out.println(key +"\t" + days.get(key));
		 }
	}

}
Sunday is 1
If key not present value is null

Saturday	7
Thursday	5
Monday	2
Tuesday	3
Wednesday	4
Friday	6
Sunday	1

Saturday	7
Thursday	5
Monday	2
Tuesday	3
Wednesday	4
Friday	6
Sunday	1

HashTable

HashTable behaves very similar to HashMap but hashtable is thread-safe, all the methods are declared with synchronized keyword making the collection threadsafe and a good candidate to be used in multithreaded applications. However because of this additional wrapper the HashTable performance is slower than the HashMap. This means that in a multithreaded application, only one thread can gets access to a hashtable object and do an operation on it.

TreeMap

The Map which stores key in sorted manner, such that while traversal the keys are sorted. This implementation provides guaranteed log(n) time cost for the containsKey(), get(), put() and remove() operations. The tree implementation is Red-Black Tree. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

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

public class UseTreeMap {

	public static void main(String[] args) {
		//Create a store elements in the Map
		 Map<String, Integer> days = new TreeMap<String, Integer>();
		 days.put("Sunday", 1);
		 days.put("Monday", 2);
		 days.put("Tuesday", 3);
		 days.put("Wednesday", 4);
		 days.put("Thursday", 5);
		 days.put("Friday", 6);
		 days.put("Saturday", 7);
		 
		 //Iterate all elements
		 for(Entry<String, Integer> entry : days.entrySet()) {
		  System.out.println(entry.getKey() + "\t" + entry.getValue());
		 }
	}
}

//output
Friday	6
Monday	2
Saturday	7
Sunday	1
Thursday	5
Tuesday	3
Wednesday	4

LinkedHashMap

LinkedHashMap is a combination of hashmap and linked list, with predictable iteration order.

  • In the LinkedHashMap implementation, the LinkedHashMap.Entry class extends the HashMap.Entry class, by adding before and after fields. These fields are used to assemble the LinkedHashMap.Entry objects into an independent doubly-linked list that records the insertion order. So, in the LinkedHashMap class, the entry objects are in two distinct chains:
    • a singly linked hash chain that is accessed via the main hash array, and
    • a separate doubly linked list of all entries that is kept in entry insertion order.
  • Like HashMap, it provides constant-time performance O(1) for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets.
  • Performance is likely to be just slightly below that of HashMap, due to the added expense of maintaining the linked list, with one exception: Iteration over the collection-views of a LinkedHashMap requires time proportional to the size of the map, regardless of its capacity. Iteration over a HashMap is likely to be more expensive, requiring time proportional to its capacity.
  • import java.util.LinkedHashMap;
    import java.util.Map;
    import java.util.Map.Entry;
    import java.util.TreeMap;
    
    public class UseLinkedHashMap {
    
    	public static void main(String[] args) {
    		 Map<String, Integer> days = new LinkedHashMap<String, Integer>();
    		 days.put("Sunday", 1);
    		 days.put("Monday", 2);
    		 days.put("Tuesday", 3);
    		 days.put("Wednesday", 4);
    		 days.put("Thursday", 5);
    		 days.put("Friday", 6);
    		 days.put("Saturday", 7);
    		 
    		 //Iterate all elements
    		 for(Entry<String, Integer> entry : days.entrySet()) {
    	       System.out.println(entry.getKey() + "\t" + entry.getValue());
    		 }
    	}
    
    }
    //output 
    Sunday	1
    Monday	2
    Tuesday	3
    Wednesday	4
    Thursday	5
    Friday	6
    Saturday	7
    

Subscribe to get latest updates.

© 2015 Java Questions | Sitemap