What is the difference between a HashMap and a TreeMap? [duplicate]

Question

TreeMap is an example of a SortedMap, which means that the order of the keys can be sorted, and when iterating over the keys, you can expect that they will be in order.

HashMap on the other hand, makes no such guarantee. Therefore, when iterating over the keys of a HashMap, you can't be sure what order they will be in.

HashMap will be more efficient in general, so use it whenever you don't care about the order of the keys.

HashMap is implemented by Hash Table while TreeMap is implemented by Red-Black tree. The main difference between HashMap and TreeMap actually reflect the main difference between a Hash and a Binary Tree , that is, when iterating, TreeMap guarantee can the key order which is determined by either element's compareTo() method or a comparator set in the TreeMap's constructor.

Take a look at following diagram.

To sum up:

• HashMap: Lookup-array structure, based on hashCode(), equals() implementations, O(1) runtime complexity for inserting and searching, unsorted
• TreeMap: Tree structure, based on compareTo() implementation, O(log(N)) runtime complexity for inserting and searching, sorted

Taken from: HashMap vs. TreeMap

Use HashMap most of the times but use TreeMap when you need the key to be sorted (when you need to iterate the keys).

I'll talk about the HashMap and TreeMap implementation in Java:

• HashMap -- implement basic map interface

  1. implemented by an array of buckets, each bucket is a LinkedList of entries
  2. running time of basic operations: put(), average O(1), worst case O(n), happens when the table is resized; get(), remove(), average O(1)
  3. not synchronized, to synchronize it: Map m = Collections.synchronizedMap(new HashMap(...));
  4. Iteration order of the map is unpredictable.

• TreeMap -- implement navigable map interface

  1. implemented by a red-black tree
  2. running time of basic operations: put(), get(), remove(), worst case O(lgn)
  3. not synchronized, to synchronize it: SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
  4. provide ordered iteration. higherKey(), lowerKey() can be used to get the successor and predecessor of a given key.

To sum, the biggest difference between HashMap and TreeMap is that TreeMap implements NavigableMap<K,V>, which provide the feature of ordered iteration. Besides, both HashMap and TreeMap are members of Java Collection framework. You can investigate the source code of Java to know more about their implementations.

You almost always use HashMap, you should only use TreeMap if you need your keys to be in a specific order.