Difference between HashMap, LinkedHashMap and TreeMap

All three represent mapping from unique keys to values, and therefore implement the Map interface.\n\n\nHashMap is a map based on hashing of the keys. It supports O(1) get/put operations. Keys must have consistent implementations of hashCode() and equals() for this to work. \nLinkedHashMap is very similar to HashMap, but it adds awareness to the order at which items are added (or accessed), so the iteration order is the same as insertion order (or access order, depending on construction parameters).\nTreeMap is a tree based mapping. Its put/get operations take O(log n) time. It requires items to have some comparison mechanism, either with Comparable or Comparator. The iteration order is determined by this mechanism.\n",

These are different implementations of the same interface. Each implementation has some advantages and some disadvantages (fast insert, slow search) or vice versa.\n\nFor details look at the javadoc of TreeMap, HashMap, LinkedHashMap.",

See where each class is in the class hierarchy in the following diagram (bigger one). TreeMap implements SortedMap and NavigableMap while HashMap doesn't.\n\nHashTable is obsolete and the corresponding ConcurrentHashMap class should be used.\n",

While there are plenty of excellent Answers here, I'd like to present my own table describing the various Map implementations bundled with Java 11.\n\nWe can see these differences listed on the table graphic:\n\n\nHashMap is the general-purpose Map commonly used when you have no special needs.\nLinkedHashMap extends HashMap, adding this behavior: Maintains an order, the order in which the entries were originally added. Altering the value for key-value entry does not alter its place in the order.\nTreeMap too maintains an order, but uses either (a) the “natural” order, meaning the value of the compareTo method on the key objects defined on the Comparable interface, or (b) invokes a Comparator implementation you provide. \n\n\nTreeMap implements both the SortedMap interface, and its successor, the NavigableMap interface.\n\nNULLs: TreeMap does not allow a NULL as the key, while HashMap & LinkedHashMap do. \n\n\nAll three allow NULL as the value.\n\nHashTable is legacy, from Java 1. Supplanted by the ConcurrentHashMap class. Quoting the Javadoc: ConcurrentHashMap obeys the same functional specification as Hashtable, and includes versions of methods corresponding to each method of Hashtable.\n\n\n",

HashMap\n\n\nIt has pair values(keys,values)\nNO duplication key values\nunordered unsorted\nit allows one null key and more than one null values\n\n\nHashTable\n\n\nsame as hash map\nit does not allows null keys and null values\n\n\nLinkedHashMap\n\n\nIt is ordered version of map implementation\nBased on linked list and hashing data structures\n\n\nTreeMap\n\n\nOrdered and sortered version\nbased on hashing data structures\n",

The most important among all the three is how they save the order of the entries.\n\nHashMap - Does not save the order of the entries.\neg. \n\npublic static void main(String[] args){\n HashMap<String,Integer> hashMap = new HashMap<>();\n hashMap.put(\"First\",1);// First ---> 1 is put first in the map\n hashMap.put(\"Second\",2);//Second ---> 2 is put second in the map\n hashMap.put(\"Third\",3); // Third--->3 is put third in the map\n for(Map.Entry<String,Integer> entry : hashMap.entrySet())\n {\n System.out.println(entry.getKey()+\"--->\"+entry.getValue());\n }\n }\n\n\n\n\nLinkedHashMap : It save the order in which entries were made. eg:\n\npublic static void main(String[] args){\n LinkedHashMap<String,Integer> linkedHashMap = new LinkedHashMap<>();\n linkedHashMap.put(\"First\",1);// First ---> 1 is put first in the map\n linkedHashMap.put(\"Second\",2);//Second ---> 2 is put second in the map\n linkedHashMap.put(\"Third\",3); // Third--->3 is put third in the map\n for(Map.Entry<String,Integer> entry : linkedHashMap.entrySet())\n {\n System.out.println(entry.getKey()+\"--->\"+entry.getValue());\n }\n }\n\n\n\n\nTreeMap : It saves the entries in ascending order of the keys. eg:\n\npublic static void main(String[] args) throws IOException {\n TreeMap<String,Integer> treeMap = new TreeMap<>();\n treeMap.put(\"A\",1);// A---> 1 is put first in the map\n treeMap.put(\"C\",2);//C---> 2 is put second in the map\n treeMap.put(\"B\",3); //B--->3 is put third in the map\n for(Map.Entry<String,Integer> entry : treeMap.entrySet())\n {\n System.out.println(entry.getKey()+\"--->\"+entry.getValue());\n }\n }\n\n\n",

Just some more input from my own experience with maps, on when I would use each one:\n\n\nHashMap - Most useful when looking for a best-performance (fast) implementation.\nTreeMap (SortedMap interface) - Most useful when I'm concerned with being able to sort or iterate over the keys in a particular order that I define.\nLinkedHashMap - Combines advantages of guaranteed ordering from TreeMap without the increased cost of maintaining the TreeMap. (It is almost as fast as the HashMap). In particular, the LinkedHashMap also provides a great starting point for creating a Cache object by overriding the removeEldestEntry() method. This lets you create a Cache object that can expire data using some criteria that you define.\n",

All offer a key->value map and a way to iterate through the keys. The most important distinction between\nthese classes are the time guarantees and the ordering of the keys.\n\n\nHashMap offers 0(1) lookup and insertion. If you iterate through the keys, though, the ordering of the\nkeys is essentially arbitrary. It is implemented by an array of linked lists.\nTreeMap offers O(log N) lookup and insertion. Keys are ordered, so if you need to iterate through\nthe keys in sorted order, you can. This means that keys must implement the Comparable interface.TreeMap is implemented by a Red-Black Tree.\nLinkedHashMap offers 0(1) lookup and insertion. Keys are ordered by their insertion order. It is\nimplemented by doubly-linked buckets.\n\n\nImagine you passed an empty TreeMap, HashMap, and LinkedHashMap into the following function:\n\nvoid insertAndPrint(AbstractMap<Integer, String> map) {\n int[] array= {1, -1, 0};\n for (int x : array) {\n map.put(x, Integer.toString(x));\n }\n for (int k: map.keySet()) {\n System.out.print(k + \", \");\n }\n}\n\n\nThe output for each will look like the results below.\n\nFor HashMap, the output was, in my own tests, { 0, 1, -1}, but it could be any ordering. There is no guarantee on the\nordering.\nTreemap,the output was,{ -1, 0, 1}\nLinkedList,the output was,{ 1, -1, 0}",

All three classes HashMap, TreeMap and LinkedHashMap implements java.util.Map interface, and represents mapping from unique key to values. \n\nHashMap\n\n\nA HashMap contains values based on the key.\nIt contains only unique elements. \nIt may have one null key and multiple null values.\nIt maintains no order.\n\npublic class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable\n\n\nLinkedHashMap\n\n\nA LinkedHashMap contains values based on the key.\nIt contains only unique elements.\nIt may have one null key and multiple null values.\nIt is same as HashMap instead maintains insertion order. //See class deceleration below\n\npublic class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>\n\n\nTreeMap\n\n\nA TreeMap contains values based on the key. It implements the NavigableMap interface and extends AbstractMap class.\nIt contains only unique elements.\nIt cannot have null key but can have multiple null values.\nIt is same as HashMap instead maintains ascending order(Sorted using the natural order of its key.).\n\npublic class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable \n\n\nHashtable\n\n\nA Hashtable is an array of list. Each list is known as a bucket. The position of bucket is identified by calling the hashcode() method. A Hashtable contains values based on the key.\nIt contains only unique elements.\nIt may have not have any null key or value.\nIt is synchronized.\nIt is a legacy class.\n\npublic class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, Serializable\n\n\n\n\nRef: http://javarevisited.blogspot.in/2015/08/difference-between-HashMap-vs-TreeMap-vs-LinkedHashMap-Java.html",

\n HashMap makes absolutely not guarantees about the iteration order. It\n can (and will) even change completely when new elements are added.\n TreeMap will iterate according to the \"natural ordering\" of the keys\n according to their compareTo() method (or an externally supplied\n Comparator). Additionally, it implements the SortedMap interface,\n which contains methods that depend on this sort order. LinkedHashMap\n will iterate in the order in which the entries were put into the map\n\n\nLook at how performance varying..\n\n\nTree map which is an implementation of Sorted map. The complexity of the put, get and containsKey operation is O(log n) due to the Natural ordering",

@Amit: SortedMap is an interface whereas TreeMap is a class which implements the SortedMap interface. That means if follows the protocol which SortedMap asks its implementers to do.\nA tree unless implemented as search tree, can't give you ordered data because tree can be any kind of tree. So to make TreeMap work like Sorted order, it implements SortedMap ( e.g, Binary Search Tree - BST, balanced BST like AVL and R-B Tree , even Ternary Search Tree - mostly used for iterative searches in ordered way ).\n\npublic class TreeMap<K,V>\nextends AbstractMap<K,V>\nimplements SortedMap<K,V>, Cloneable, Serializable\n\n\nIn NUT-SHELL\nHashMap : gives data in O(1) , no ordering\n\nTreeMap : gives data in O(log N), base 2. with ordered keys\n\nLinkedHashMap : is Hash table with linked list (think of indexed-SkipList) capability to store data in the way it gets inserted in the tree. Best suited to implement LRU ( least recently used ).",

Hash map doesn't preserves the insertion order.\nExample. Hashmap\nIf you are inserting keys as \n\n1 3\n5 9\n4 6\n7 15\n3 10\n\n\nIt can store it as \n\n4 6\n5 9\n3 10\n1 3\n7 15\n\n\nLinked Hashmap preserves the insertion order. \n\nExample.\nIf you are inserting keys \n\n1 3\n5 9\n4 6\n7 15\n3 10\n\n\nIt will store it as\n\n1 3\n5 9\n4 6\n7 15\n3 10\n\n\nsame as we insert. \n\nTree map stores the vales in Increasing Order Of Keys. \nExample.\nIf you are inserting keys \n\n1 3\n5 9\n4 6\n7 15\n3 10\n\n\nIt will store it as\n\n1 3\n3 10\n4 6\n5 9\n7 15\n",

I prefer visual presentation:\n\n\n\n\nProperty\nHashMap\nTreeMap\nLinkedHashMap\n\n\n\n\nIteration Order\nno guaranteed order, will remain constant over time\nsorted according to the natural ordering\ninsertion-order\n\n\nGet / put / remove / containsKey\nO(1)\nO(log(n))\nO(1)\n\n\nInterfaces\nMap\nNavigableMap, Map, SortedMap\nMap\n\n\nNull values/keys\nallowed\nonly values\nallowed\n\n\nFail-fast behavior\nFail-fast behavior of an iterator cannot be guaranteed, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification\nFail-fast behavior of an iterator cannot be guaranteed, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification\nFail-fast behavior of an iterator cannot be guaranteed, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification\n\n\nImplementation\nbuckets\nRed-Black Tree\ndouble-linked buckets\n\n\nIs synchronized\nimplementation is not synchronized\nimplementation is not synchronized\nimplementation is not synchronized\n\n\n",

\nHashMap:\n\n\nOrder not maintains\nFaster than LinkedHashMap\nUsed for store heap of objects \n\nLinkedHashMap:\n\n\nLinkedHashMap insertion order will be maintained\nSlower than HashMap and faster than TreeMap\nIf you want to maintain an insertion order use this.\n\nTreeMap:\n\n\nTreeMap is a tree-based mapping\nTreeMap will follow the natural ordering of key\nSlower than HashMap and LinkedHashMap\nUse TreeMap when you need to maintain natural(default) ordering\n\n",

All three classes implement the Map interface and offer mostly the same functionality. The most important difference is the order in which iteration through the entries will happen:\n\n\nHashMap makes absolutely no guarantees about the iteration order. It can (and will) even change completely when new elements are added.\nTreeMap will iterate according to the \"natural ordering\" of the keys according to their compareTo() method (or an externally supplied Comparator). Additionally, it implements the SortedMap interface, which contains methods that depend on this sort order.\nLinkedHashMap will iterate in the order in which the entries were put into the map\n\n\n\"Hashtable\" is the generic name for hash-based maps. In the context of the Java API,\nHashtable is an obsolete class from the days of Java 1.1 before the collections framework existed. It should not be used anymore, because its API is cluttered with obsolete methods that duplicate functionality, and its methods are synchronized (which can decrease performance and is generally useless). Use ConcurrentHashMap instead of Hashtable. ",

Following are major difference between HashMap and TreeMap\n\n\nHashMap does not maintain any order. In other words , HashMap does not provide any guarantee that the element inserted first will be printed first, where as Just like TreeSet , TreeMap elements are also sorted according to the natural ordering of its elements\nInternal HashMap implementation use Hashing and TreeMap internally uses Red-Black tree implementation.\nHashMap can store one null key and many null values.TreeMap can not contain null keys but may contain many null values.\nHashMap take constant time performance for the basic operations like get and put i.e O(1).According to Oracle docs , TreeMap provides guaranteed log(n) time cost for the get and put method.\nHashMap is much faster than TreeMap, as performance time of HashMap is constant against the log time TreeMap for most operations.\nHashMap uses equals() method in comparison while TreeMap uses compareTo() method for maintaining ordering.\nHashMap implements Map interface while TreeMap implements NavigableMap interface.\n",