Concrete maps in Java JDK 1.8
class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
Below is the summary of differences between HashMap, LinkedHashMap, TreeMap, and Hashtable in Java:
(Source: javarevisited.blogspot.com)
- If we need to get the key back in insertion order, then use LinkedHashMap.
- If we need to get the key back in their true/natural order, then use TreeMap.
- Otherwise, HashMap is best because it is typically faster and requires less overhead.
An example of using LinkedHashMap, TreeMap and HashMap in Java
HashMap
/* HashMap: Put, Get, Remove is O(1); Not synchronized; Allow null key and value; Not guaranteed order. */ Map<Integer, String> hashMap = new HashMap<>(); hashMap.put(2,"Peter"); hashMap.put(1,"Marry"); hashMap.put(3,"Gayle"); hashMap.put(null, null); hashMap.put(null, "Unknown"); hashMap.put(null, null); System.out.println("Size of hashMap: " +hashMap.size()); System.out.println("Look up a value:" + hashMap.get(1)); System.out.println("Look up by null key " + hashMap.get(null)); // iterate through all entries System.out.println("Order of Entries in HashMap - Not guaranteed"); for(Map.Entry<Integer, String> entry : hashMap.entrySet()) { System.out.println("Key:" + entry.getKey() + " Value:" + entry.getValue()); }
Actually HashMap can’t keep duplicates within it. Whenever there is a duplicate key added to the map it overrides the existing one. So each time there will be only one key available with that name. Output in console showed below:
Size of hashMap: 4 Look up a value:Marry Look up by null key null Order of Entries in HashMap - Not guaranteed Key:null Value:null Key:1 Value:Marry Key:2 Value:Peter Key:3 Value:Gayle
TreeMap
/* TreeMap: Put, Get, Remove is O(log(n)); Not synchronized; NOT Allow null key and value; Sorted in order */ Map<Integer, String> treeMap = new TreeMap<>(); treeMap.put(2, "Jack"); treeMap.put(3, "Haney"); treeMap.put(0, "Barron"); System.out.println("Order of Entries in TreeMap - Sorted in natural order"); for(Map.Entry<Integer, String> entry : treeMap.entrySet()) { System.out.println("Key:" + entry.getKey() + " Value:" + entry.getValue()); } //Using TreeMap to create a sorted hashMap, sorting keys on natural order SortedMap<Integer, String> sortedMap = new TreeMap<>(Comparator.naturalOrder()); // TreeMap is not allow null Key and Value so remove all null entries in hashMap hashMap.remove(null); sortedMap.putAll(hashMap); System.out.println("Order of entries in TreeMap from the existing hashMap"); System.out.println(sortedMap);
Noted that TreeMap is an implementation of SortedMap and keeps keys in their natural order or a custom order specified by Comparator provided while creating TreeMap.
Output in console:
Order of Entries in TreeMap - Sorted in natural order Key:0 Value:Barron Key:2 Value:Jack Key:3 Value:Haney Order of entries in TreeMap from the existing hashMap {1=Marry, 2=Peter, 3=Gayle}
LinkedHashMap
/* LinkedHashMap: Put, Get, Remove is O(1); Not synchronized; Allow null key and value; Sorted basing on the insertion order. */ Map<Integer, String> linkedHashMap = new LinkedHashMap<>(); linkedHashMap.put(2, "Jack"); linkedHashMap.put(3, "Haney"); linkedHashMap.put(0, "Barron"); linkedHashMap.put(null, null); System.out.println("Order of Entries in LinkedHashMap"); for(Map.Entry<Integer, String> entry : linkedHashMap.entrySet()) { System.out.println("Key:" + entry.getKey() + " Value:" + entry.getValue()); } //Using LinkedHashMap to create copy of a Map in Java Map<Integer, String> copy = new LinkedHashMap<>(sortedMap);
Output in console:
Order of Entries in LinkedHashMap Key:2 Value:Jack Key:3 Value:Haney Key:0 Value:Barron Key:null Value:null Order of Entries in a copy Map created by LinkedHashMap {1=Marry, 2=Peter, 3=Gayle}
To sum up, all concrete classes offer a key -> value and a way to iterate through the key. The most important distinction between theses classes is the time guarantees and the ordering of the keys.
References:
- Cay S. Horstmann, Gray Cornel, “Collection”, in Core Java Volume I- Fundamentals, chapter 13, 8th Edition, Sun Microsystems Press.
- Maurice Naftalin and Philip Wadler, “Maps”, in Java Generics and Collections, chapter 16, 2007 O’Reilly Media.
- Oracle Document, Retrieved at http://docs.oracle.com/javase/tutorial/collections/interfaces/index.html
- http://javarevisited.blogspot.com/2015/08/difference-between-HashMap-vs-TreeMap-vs-LinkedHashMap-Java.html
- Java67.com, Retrieved at How to Sort HashMap in Java based on Keys and Values