Difference between HashMap and TreeMap in Java

In this article I will explain the difference between java HashMap and java TreeMap

Although both implement the Map interface and offer mostly the same functionality, HashMap and TreeMap have different implementations. The most important difference is the order in which iteration through the entries will happen.

Look at the table below for a visual representation of the differences between HashMap and TreeMap

Major Difference between HashMap and TreeMap

TreeMap is an example of a SortedMap and is implemented by is implemented by Red-Black tree, which means that the order of the keys is sorted. When iterating over the keys, you can rely on the fact they will be in order. The order of the keys is determined by either element’s compareTo() method or an externally supplied Comparator.

HashMap on the other hand, makes no such guarantee. It is implemented by Hash Table. Therefore, when iterating over the keys of a HashMap, you can’t be sure what order they will be in.

Take a look at the following example:

package javatutorial.net;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class HashMapVsTreeMapExample {

	public static void main(String[] args) {
		Map<Integer, String> hMap = new HashMap<Integer, String>();
		hMap.put(5, "A");
		hMap.put(11, "C");
		hMap.put(4, "Z");
		hMap.put(77, "Y");
		hMap.put(9, "P");
		hMap.put(66, "Q");
		hMap.put(0, "R");

		Map<Integer, String> tMap = new TreeMap<Integer, String>();
		tMap.put(5, "A");
		tMap.put(11, "C");
		tMap.put(4, "Z");
		tMap.put(77, "Y");
		tMap.put(9, "P");
		tMap.put(66, "Q");
		tMap.put(0, "R");

		System.out.println("HashMap iteration order =======");
		for (Map.Entry<Integer, String> entry : hMap.entrySet()) {
			System.out.println(entry.getKey() + " = " + entry.getValue());
		}

		System.out.println("\nTreeMap iteration order =======");
		for (Map.Entry<Integer, String> entry : tMap.entrySet()) {
			System.out.println(entry.getKey() + " = " + entry.getValue());
		}
	}
}

Now look at the output of this program:

HashMap iteration order =======
0 = R
66 = Q
4 = Z
5 = A
9 = P
11 = C
77 = Y

TreeMap iteration order =======
0 = R
4 = Z
5 = A
9 = P
11 = C
66 = Q
77 = Y

As you can see, while iterating over the HashMap we get the entries in some “random” order. The TreeMap iteration on the other hand returns the entries in their natural order.

Implementation Complexity Differences

As the complexity of HashMap implementation is O(1), HashMap can be considered more efficient in general, so use it whenever you don’t care about the order of the keys. The complexity of get, put and remove operations in TreeMap at the other hand is O(log(n))

Allowed Keys and Values Differences

Another important difference is, that HashMap null values are allowed for keys and values, where TreeMap allows null only to be used for it’s values.

Synchronization (no Differences)

Note, that both implementations are not synchronized, meaning operating over those maps is not thread-safe. If you need a thread-safe Map you may want to choose the ConcurrentHashMap class from the java.util.concurrent package. This is a thread-safe implementation of Map that offers far better concurrency than Collections.synchronizedMap(Map<K,V> m)