What is the difference between HashMap
, LinkedHashMap
and TreeMap
in Java?
I don't see any difference in the output as all the three has keySet
and values
. What are Hashtable
s?
Map m1 = new HashMap();
m1.put("map", "HashMap");
m1.put("schildt", "java2");
m1.put("mathew", "Hyden");
m1.put("schildt", "java2s");
print(m1.keySet());
print(m1.values());
SortedMap sm = new TreeMap();
sm.put("map", "TreeMap");
sm.put("schildt", "java2");
sm.put("mathew", "Hyden");
sm.put("schildt", "java2s");
print(sm.keySet());
print(sm.values());
LinkedHashMap lm = new LinkedHashMap();
lm.put("map", "LinkedHashMap");
lm.put("schildt", "java2");
lm.put("mathew", "Hyden");
lm.put("schildt", "java2s");
print(lm.keySet());
print(lm.values());
All three represent mapping from unique keys to values, and therefore implement the Map interface.
HashMap 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.
LinkedHashMap 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).
TreeMap 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.
@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.
A 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 ).
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements SortedMap<K,V>, Cloneable, Serializable
In NUT-SHELL
HashMap
: gives data in O(1) , no ordering
TreeMap
: gives data in O(log N), base 2. with ordered keys
LinkedHashMap
: 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 ).
All three classes HashMap
, TreeMap
and LinkedHashMap
implements java.util.Map
interface, and represents mapping from unique key to values.
A HashMap
contains values based on the key.
It contains only unique elements.
It may have one null key and multiple null values.
It maintains no order.
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
LinkedHashMap
contains values based on the key.It is same as HashMap instead maintains insertion order. //See class deceleration below
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
TreeMap
contains values based on the key. It implements the NavigableMap interface and extends AbstractMap class.It is same as HashMap
instead maintains ascending order(Sorted using the natural order of its key.).
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable
It is a legacy class.
public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, Serializable
HashMap:
LinkedHashMap:
TreeMap:
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.
We can see these differences listed on the table graphic:
HashMap
is the general-purpose Map
commonly used when you have no special needs.LinkedHashMap
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.TreeMap
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.
TreeMap
implements both the SortedMap
interface, and its successor, the NavigableMap
interface.TreeMap
does not allow a NULL as the key, while HashMap
& LinkedHashMap
do.
HashTable
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
.All offer a key->value map and a way to iterate through the keys. The most important distinction between these classes are the time guarantees and the ordering of the keys.
Imagine you passed an empty TreeMap, HashMap, and LinkedHashMap into the following function:
void insertAndPrint(AbstractMap<Integer, String> map) {
int[] array= {1, -1, 0};
for (int x : array) {
map.put(x, Integer.toString(x));
}
for (int k: map.keySet()) {
System.out.print(k + ", ");
}
}
The output for each will look like the results below.
For HashMap, the output was, in my own tests, { 0, 1, -1}, but it could be any ordering. There is no guarantee on the
ordering.
Treemap,the output was,{ -1, 0, 1}
LinkedList,the output was,{ 1, -1, 0}
HashMap
can contain one null key.
HashMap maintains no order.
TreeMap
TreeMap can not contain any null key.
TreeMap maintains ascending order.
LinkedHashMap
LinkedHashMap can be used to maintain insertion order, on which keys are inserted into Map or it can also be used to maintain an access order, on which keys are accessed.
Examples::
1) HashMap map = new HashMap();
map.put(null, "Kamran");
map.put(2, "Ali");
map.put(5, "From");
map.put(4, "Dir");`enter code here`
map.put(3, "Lower");
for (Map.Entry m : map.entrySet()) {
System.out.println(m.getKey() + " " + m.getValue());
}
2) TreeMap map = new TreeMap();
map.put(1, "Kamran");
map.put(2, "Ali");
map.put(5, "From");
map.put(4, "Dir");
map.put(3, "Lower");
for (Map.Entry m : map.entrySet()) {
System.out.println(m.getKey() + " " + m.getValue());
}
3) LinkedHashMap map = new LinkedHashMap();
map.put(1, "Kamran");
map.put(2, "Ali");
map.put(5, "From");
map.put(4, "Dir");
map.put(3, "Lower");
for (Map.Entry m : map.entrySet()) {
System.out.println(m.getKey() + " " + m.getValue());
}
Following are major difference between HashMap and TreeMap
HashMap 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
Internal HashMap implementation use Hashing and TreeMap internally uses Red-Black tree implementation.
HashMap can store one null key and many null values.TreeMap can not contain null keys but may contain many null values.
HashMap 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.
HashMap is much faster than TreeMap, as performance time of HashMap is constant against the log time TreeMap for most operations.
HashMap uses equals() method in comparison while TreeMap uses compareTo() method for maintaining ordering.
HashMap implements Map interface while TreeMap implements NavigableMap interface.
Hash map doesn't preserves the insertion order.
Example. Hashmap
If you are inserting keys as
1 3
5 9
4 6
7 15
3 10
It can store it as
4 6
5 9
3 10
1 3
7 15
Linked Hashmap preserves the insertion order.
Example.
If you are inserting keys
1 3
5 9
4 6
7 15
3 10
It will store it as
1 3
5 9
4 6
7 15
3 10
same as we insert.
Tree map stores the vales in Increasing Order Of Keys.
Example.
If you are inserting keys
1 3
5 9
4 6
7 15
3 10
It will store it as
1 3
3 10
4 6
5 9
7 15
See where each class is in the class hierarchy in the following diagram (bigger one). TreeMap implements SortedMap
and NavigableMap
while HashMap
doesn't.
HashTable
is obsolete and the corresponding ConcurrentHashMap
class should be used.
Just some more input from my own experience with maps, on when I would use each one:
removeEldestEntry()
method. This lets you create a Cache object that can expire data using some criteria that you define.The most important among all the three is how they save the order of the entries.
HashMap
- Does not save the order of the entries.
eg.
public static void main(String[] args){
HashMap<String,Integer> hashMap = new HashMap<>();
hashMap.put("First",1);// First ---> 1 is put first in the map
hashMap.put("Second",2);//Second ---> 2 is put second in the map
hashMap.put("Third",3); // Third--->3 is put third in the map
for(Map.Entry<String,Integer> entry : hashMap.entrySet())
{
System.out.println(entry.getKey()+"--->"+entry.getValue());
}
}
LinkedHashMap
: It save the order in which entries were made. eg:
public static void main(String[] args){
LinkedHashMap<String,Integer> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("First",1);// First ---> 1 is put first in the map
linkedHashMap.put("Second",2);//Second ---> 2 is put second in the map
linkedHashMap.put("Third",3); // Third--->3 is put third in the map
for(Map.Entry<String,Integer> entry : linkedHashMap.entrySet())
{
System.out.println(entry.getKey()+"--->"+entry.getValue());
}
}
TreeMap
: It saves the entries in ascending order of the keys. eg:
public static void main(String[] args) throws IOException {
TreeMap<String,Integer> treeMap = new TreeMap<>();
treeMap.put("A",1);// A---> 1 is put first in the map
treeMap.put("C",2);//C---> 2 is put second in the map
treeMap.put("B",3); //B--->3 is put third in the map
for(Map.Entry<String,Integer> entry : treeMap.entrySet())
{
System.out.println(entry.getKey()+"--->"+entry.getValue());
}
}
I prefer visual presentation:
+------------------------------------------------------------------------------+
¦ Property ¦ HashMap ¦ TreeMap ¦ LinkedHashMap ¦
¦--------------+---------------------+-------------------+---------------------¦
¦ Iteration ¦ no guarantee order ¦ sorted according ¦ ¦
¦ Order ¦ will remain constant¦ to the natural ¦ insertion-order ¦
¦ ¦ over time ¦ ordering ¦ ¦
¦--------------+---------------------+-------------------+---------------------¦
¦ Get/put ¦ ¦ ¦ ¦
¦ remove ¦ O(1) ¦ O(log(n)) ¦ O(1) ¦
¦ containsKey ¦ ¦ ¦ ¦
¦--------------+---------------------+-------------------+---------------------¦
¦ ¦ ¦ NavigableMap ¦ ¦
¦ Interfaces ¦ Map ¦ Map ¦ Map ¦
¦ ¦ ¦ SortedMap ¦ ¦
¦--------------+---------------------+-------------------+---------------------¦
¦ ¦ ¦ ¦ ¦
¦ Null ¦ allowed ¦ only values ¦ allowed ¦
¦ values/keys ¦ ¦ ¦ ¦
¦--------------+---------------------------------------------------------------¦
¦ ¦ Fail-fast behavior of an iterator cannot be guaranteed ¦
¦ Fail-fast ¦ impossible to make any hard guarantees in the presence of ¦
¦ behavior ¦ unsynchronized concurrent modification ¦
¦--------------+---------------------------------------------------------------¦
¦ ¦ ¦ ¦ ¦
¦Implementation¦ buckets ¦ Red-Black Tree ¦ double-linked ¦
¦ ¦ ¦ ¦ buckets ¦
¦--------------+---------------------------------------------------------------¦
¦ Is ¦ ¦
¦ synchronized ¦ implementation is not synchronized ¦
+------------------------------------------------------------------------------+
HashMap makes absolutely not guarantees about the iteration order. It can (and will) even change completely when new elements are added. TreeMap 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. LinkedHashMap will iterate in the order in which the entries were put into the map
Look at how performance varying..
Tree 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
These are different implementations of the same interface. Each implementation has some advantages and some disadvantages (fast insert, slow search) or vice versa.
For details look at the javadoc of TreeMap, HashMap, LinkedHashMap.
Source: Stackoverflow.com