Difference between HashMap, LinkedHashMap and TreeMap

Question

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.

Also, what are Hashtables?

Map<String, String> 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<String, String> 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<String, String> 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());

Incongruity

Answer 1

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:

• HashMap makes absolutely no 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

"Hashtable" is the generic name for hash-based maps. In the context of the Java API, Hashtable 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.

Gavrah

What is then Map actually and whats the difference between Map,HashMap and Hashtables. – Incongruity

@theband: Map is an interface. HashMap and Hashtable both implement it; as I wrote, Hashtable is a legacy class. – Gavrah

@theband: Read the API doc, that's what it's for: java.sun.com/javase/6/docs/api/java/util/package-summary.html – Gavrah

A notable difference between Hashtable and HashMap is that in a Hashtable, "neither the key nor the value can be null". This constraint does not exist on the latter. – Rachael

it is possible to use Comparable or Comparator for implementing sorting mechanism in SortedMap (#4109104) – Katheleenkatherin

@AshkanN: Yes - in fact those are the standard ways to implement sorting. TreeMap has a constructor that takes a Comparator to use, and if none is provided, it expects all objects added to implement Comparable. – Gavrah

You can choose whether you want the LinkedHashMap iteration in insertion-order or access-order. – Fatwitted

Answer 2

I prefer visual presentation:

Property	HashMap	TreeMap	LinkedHashMap
Iteration Order	no guaranteed order, will remain constant over time	sorted according to the natural ordering	insertion-order
Get / put / remove / containsKey	O(1)	O(log(n))	O(1)
Interfaces	Map	NavigableMap, Map, SortedMap	Map
Null values/keys	allowed	only values	allowed
Fail-fast behavior	Fail-fast behavior of an iterator cannot be guaranteed, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification	Fail-fast behavior of an iterator cannot be guaranteed, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification	Fail-fast behavior of an iterator cannot be guaranteed, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification
Implementation	buckets	Red-Black Tree	double-linked buckets
Is synchronized	implementation is not synchronized	implementation is not synchronized	implementation is not synchronized

Everrs

In addition to insertion-order, LinkedHashMap also supports access-order (when using the constructor with the boolean access-order param). – Accord

Double Linked Buckets? I think that adds unnecessary overhead of searching for the bucket for insertion/removal operations (because it has to search for the right bucket to put the object in). I always thought that LinkedHashMap implementations would be similar to that of a Map but with a little extra overhead of "entries list" (may be as a linked list) that's used for iteration purposes. Are you sure, shevchyk? If yes, can you explain or give me some online links that back your statement? – Caldarium

@SaiDubbaka LinkedHashMap has the double linked buckets BUT ALSO the bucket table HashMap has. It's not replacing it. This means that accessing buckets is done in the same way as in HashMap, as the linked list is there for iteration in insertion order (or access order) only. – Indeclinable

It may be worth mentioning, that O(1) is the best case scenario (which we wouldn't usually call O, see this question) – Souvaine

It's also worth noting that O(1) isn't always better than O(log n); if you have a very long key, something based on BSTs might be much faster than something that has to perform an O(n) hash on the whole key before being able to do anything. – Nobile

love this visual presentation. See my analogous answer on Sets here https://mcmap.net/q/54200/-hashset-vs-treeset based on your work – Failsafe

It is not strictly true that a TreeMap disallows null keys. If the TreeMap is using a Comparator that allows nulls, then the TreeMap can contain null keys. For example, the following is a TreeMap with "A" mapped to null: new TreeMap<>(Comparator.nullsLast(Comparator.naturalOrder())).put(null, "A"); – Starspangled

Answer 3

All three represent mapping from unique keys to values, and therefore implement the Map interface.

1. 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.

2. 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).

3. 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.

Accord

So if I understand correctly, the only difference between LinkedHashMap and TreeMap is performance, given that the order of insertion is the same as the natural order? – Nevile

@MosheShaham As he said in # 2: LinkedHashMap will iterate in the insertion order, not the natural order. So if you add (2,5,3) to a LinkedHashMap and do a for each over it, it will return 2,5,3. If it were 2,5,3 to a TreeMap it will return 2,3,5. – Observe

Tree map also has a lot of other nice tricks. Like head and tail maps. – Dynatron

private TreeMap<String ,Integer> mySection2 = new TreeMap<>(); mySection2.put("abc1", 2); mySection2.put("abc2",5); mySection2.put("abc3",3); for(Integer x : mySection2.values()) { Log.e("LOG","TreeMap===="+x); } This is giving me the same order as items were inserted ?please suggest how is it different from LinkedHashMaps ? – Stouffer

@B.shruti: This is because your insertion order matches the lexicographic order of your keys ("abc1", "abc2", "abc3"). If you insert in a different order, your code will still iterate according to the lexicographic ordering. – Accord

Thanks for your answer, basically what i get as a difference between tree and linked hash map is linked hasmap would iterate the values in order they were inseted , but tree Map would iterate the values according to natural ordering /lexicograhic/sorted odering of "keys" not values. – Stouffer

Answer 4

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.

Laddy

this is amazing answer with this diagram – Teraterai

Answer 5

HashMap

• It has pair values(keys,values)
• NO duplication key values
• unordered unsorted
• it allows one null key and more than one null values

HashTable

• same as hash map
• it does not allows null keys and null values

LinkedHashMap

• It is ordered version of map implementation
• Based on linked list and hashing data structures

TreeMap

• Ordered and sortered version
• based on hashing data structures

Sternson

Also HashTable is synchronized. Anyways,, I like your answer, clean and clear. – Files

Answer 6

Just some more input from my own experience with maps, on when I would use each one:

• HashMap - Most useful when looking for a best-performance (fast) implementation.
• TreeMap (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.
• LinkedHashMap - 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.

Hawkbill

To be precise, TreeMap doesn't keep the elements in order. It keeps the keys in order. – Cosgrove

Answer 7

All three classes HashMap, TreeMap and LinkedHashMap implements java.util.Map interface, and represents mapping from unique key to values.

HashMap

1. A HashMap contains values based on the key.

2. It contains only unique elements.

3. It may have one null key and multiple null values.

4. It maintains no order.

   public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

LinkedHashMap

1. A LinkedHashMap contains values based on the key.
2. It contains only unique elements.
3. It may have one null key and multiple null values.

4. 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

1. A TreeMap contains values based on the key. It implements the NavigableMap interface and extends AbstractMap class.
2. It contains only unique elements.
3. It cannot have null key but can have multiple null values.

4. 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

Hashtable

1. A 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.
2. It contains only unique elements.
3. It may have not have any null key or value.
4. It is synchronized.

5. It is a legacy class.

   public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, Serializable

Ref: http://javarevisited.blogspot.in/2015/08/difference-between-HashMap-vs-TreeMap-vs-LinkedHashMap-Java.html

Junk

Big-O notation of HashMap should not be O(1). That's the best case, and hashtables have O(n) as their worst case scenario. This is supported by your link. – Hymn

see here - https://mcmap.net/q/36991/-is-a-java-hashmap-search-really-o-1/… – Junk

@HaakonLøtveit I will also suggest to go for actual code here - grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/… – Junk

That STILL says that it's O(n) in the worst case. It's a mathematical concept, and you don't get to say that it's O(1), unless it's actually O(1). You're also assuming some really good hashing functions here. I mean, we could use something like class TerribleHashKey { @Override hashCode() { return 4; /* Determined by fair dice throw */ }} and use that as a key for other fun stuff. Having a high probability of O(1) and having O(1) is not the same. People come here for help with their homework. Let's not ruin their grades.. ;) – Hymn

And it would be worth noticing that in Java 8 you have worst case of O(log(n)) if you have more than 8 buckets, see grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/… for details about this. – Hymn

@HaakonLøtveit above complexity is for well optimized hash function in Java library. And of course we can assume that a novice programmer can always write something like public int hashCode() { return 4; } for O(N) – Junk

also read @Daniel James ans, He explained well - https://mcmap.net/q/36991/-is-a-java-hashmap-search-really-o-1/… – Junk

Daniel James is talking about little-o notation, not big-O notation. It's hence not very relevant. Furthermore, when you admit that a programmer can casually break the speed of the hashing function, degrading it to O(n) or O(log (n)) depending on the version of Java, you cannot then turn around and claim O(1). If you were to say "average case" I would however, have no argument with what you're saying. :-) – Hymn

Answer 8

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

Selig

Thank you, LinkedHashMap's "O(1) expense for maintaining the order" makes sense but do you have a reference to a more detailed explaination? – Lasala

Answer 9

@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 ).

Nasal

Answer 10

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

Reconnoiter

Answer 11

• HashMap:

  • Order not maintains
  • Faster than LinkedHashMap
  • Used for store heap of objects

• LinkedHashMap:

  • LinkedHashMap insertion order will be maintained
  • Slower than HashMap and faster than TreeMap
  • If you want to maintain an insertion order use this.

• TreeMap:

  • TreeMap is a tree-based mapping
  • TreeMap will follow the natural ordering of key
  • Slower than HashMap and LinkedHashMap
  • Use TreeMap when you need to maintain natural(default) ordering

Calyptrogen

Answer 12

Following are major difference between HashMap and TreeMap

1. 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

2. Internal HashMap implementation use Hashing and TreeMap internally uses Red-Black tree implementation.

3. HashMap can store one null key and many null values.TreeMap can not contain null keys but may contain many null values.

4. 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.

5. HashMap is much faster than TreeMap, as performance time of HashMap is constant against the log time TreeMap for most operations.

6. HashMap uses equals() method in comparison while TreeMap uses compareTo() method for maintaining ordering.

7. HashMap implements Map interface while TreeMap implements NavigableMap interface.

Manikin

Answer 13

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());
        }
    }

Maleficent

I like your examples – Swanee

Answer 14

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.
• NULLs: TreeMap does not allow a NULL as the key, while HashMap & LinkedHashMap do.
  • All three allow NULL as the value.
• 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.

Matronize

Answer 15

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.

Repugnant

What are Hashtables actually and what makes it differ from a Map. – Incongruity

Answer 16

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.

1. HashMap offers 0(1) lookup and insertion. If you iterate through the keys, though, the ordering of the keys is essentially arbitrary. It is implemented by an array of linked lists.
2. TreeMap offers O(log N) lookup and insertion. Keys are ordered, so if you need to iterate through the keys in sorted order, you can. This means that keys must implement the Comparable interface.TreeMap is implemented by a Red-Black Tree.
3. LinkedHashMap offers 0(1) lookup and insertion. Keys are ordered by their insertion order. It is implemented by doubly-linked buckets.

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}

Photocopier

Answer 17

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());
    }

Coattail