Introduction:

In this quick post, we’re gonna look at the similarities as well as the differences between Java HashMap and TreeMap.

Similarities:

Before we dive into the differences between Java HashMap and TreeMap, let’s first look at their similarities:

• Both extend java.util.AbstractMap class and are part of Java Collections API
• Both of these Map implementations aren’t synchronized. So to obtain a synchronized map in either case, we’ll use:

  Collections.synchronizedMap(map)

  where the map is the name of our Map.

• Both HashMap and TreeMap doesn’t support duplicate keys – the newer value always overrides the previous one

  Map<Integer, String> hashMap = new HashMap<>();
  hashMap.put(1, "Selena");
  hashMap.put(1, "Harry");
  
  System.out.println(hashMap.size());  //prints 1
  System.out.println(hashMap.get(1)); //prints Harry
  
  Map<Integer, String> treeMap = new TreeMap<>();
  treeMap.put(1, "Selena");
  treeMap.put(1, "Harry");
  
  System.out.println(treeMap.size());  //prints 1
  System.out.println(treeMap.get(1)); //prints Harry

  Rather any Java Map implementation doesn’t allow duplicate keys

• The iterators returned by both HashMap and TreeMap are fail-fast. It means a ConcurrentModificationException is thrown if the map is structurally modified after the iterator has been created, except when using iterator’s remove() method

  Map<Integer, String> hashMap = new HashMap<>();
  hashMap.put(1, "Selena");
  hashMap.put(2, "Harry");
  
  for(Map.Entry<Integer, String> entry : hashMap.entrySet()) {
      hashMap.remove(2);  //throws ConcurrentModificationException
  }

Differences :

Now that we’re aware of how similar they are, let’s look at the differences:

• HashMap works on the principle of hashing and internally uses a hash table to store values. On the other hand, TreeMap is implemented using Red-Black Trees. A Red-Black Tree is a Self Balancing Binary Search Tree
• TreeMap is a SortedMap and the elements are maintained in sorted order. Unless we specify a custom Comparator, TreeMap stores items based on the natural ordering of key values.

  Map<Integer, String> treeMap = new TreeMap<>();
  treeMap.put(5, "Harry");
  treeMap.put(1, "Jack");
  treeMap.put(2, "Selena");
  
  System.out.println(treeMap.keySet());  // prints [1, 2, 5]

  HashMap doesn’t guarantee any specific ordering of elements. We can’t predict the order in which the elements will be stored in it.

• HashMap theoretically has O(1) time complexity for operations like add(), remove(), contains() etc. However, TreeMap takes O(log N) time for such basic operations as it has to maintain the ordering of elements
• HashMap always allows at most one null key and any number of null values. TreeMap only allows null values (not a null key) when using the natural ordering of keys:

  Map<Integer, String> treeMap = new TreeMap<>();
  treeMap.put(null, "Harry"); //throws NullPointerException
  
  Map<Integer, String> hashMap = new HashMap<>();
  hashMap.put(null, null); //works fine

  This is because the default compare() or compareTo() method implementations throw a NullPointerException. However, when using a TreeMap with a custom Comparator, the compare() method implementation determines how the null key and values are handled

Which one to use – a HashMap or a TreeMap?

Whether to opt for a HashMap or a TreeMap will depend upon the application requirements. Let’s look at the general guideline to help us decide which data structure to use:

• If we wish to keep our entries sorted based on some ordering, we should use a TreeMap
• If we have a time-critical system and performance is our major concern, we should opt for a HashMap. However, it’s important to have a good hashCode() implementation to ensure we evenly distribute our items among the several buckets.

Conclusion:

In this quick tutorial, we looked at the similarities and differences between two extremely popular Java Map implementations – HashMap and TreeMap.

There’s an article: Java Code Geeks-TreeMap that I recommend checking out to learn more about Java TreeMap.