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 in HashTable all the methods are synchronized making the Collection threadsafe and it is a good candidate to be used in multithreaded applications. However the HashTable performance is slower than the HashMap. The HashTable acheives concurrency by making each method synchronized.

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

Hash table and linked list implementation of the Map interface, with predictable iteration order.

  • This implementation differs from HashMap in 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 (insertion-order).
  • Like HashMap, it provides constant-time performance 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