Java

When to use which Map in Java

Posted on Nov 7, 2016 by Alexej Bondarenko

There are many use cases for Maps out there. A huge one is a simple Key/Value store. So why don't just use HashMap all the time? It is all about storing values and reading them later, right? Let's have a look at three Map implementations in Java.

HashMap

HashMap is the classic key/value store. You can add values by just providing a key and the value. The insertion and lookup time is O(1) since we know how to find the value for a key. This means the size of our map doesn't matter. What if we want to iterate through all values inside the map? In which order would the values be?

package ersocon.net;

import java.util.HashMap;

public class Tutorial {

   public static void main(String args[]) {

      HashMap<Integer, String> hashMap = new HashMap<Integer, String>();

      // Add elements to HashMap
      hashMap.put(0, "A");
      hashMap.put(-1, "B");
      hashMap.put(1, "C");
      
      // Iterate the hash map, results?
      for (Integer key : hashMap.keySet()) {
         System.out.println(hashMap.get(key));
      }
   }
}

Here we can see an important detail of HashMap. The ordering of the elements is arbitrary. Relying on it would introduce a major bug to our software. How can we fix this?

LinkedHashMap

Like HashMap LinkedHashMap gives us the power to insert and lookup values by key in O(1). But, instead of ordering the elements randomly a LinkedHashMap will order the items by their insertion order. Let's rewrite our example and look at the results:

package ersocon.net;

import java.util.LinkedHashMap;

public class Tutorial {

   public static void main(String args[]) {

      LinkedHashMap<Integer, String> linkedHashMap = new LinkedHashMap<Integer, String>();

      // Add elements to LinkedHashMap
      linkedHashMap.put(0, "A");
      linkedHashMap.put(-1, "B");
      linkedHashMap.put(1, "C");
      
      // Iterate the map, results?
      for (Integer key : linkedHashMap.keySet()) {
         System.out.println(linkedHashMap.get(key));
      }

      // Output: A, B, C
   }
}

This looks much better now. We can predict the behavior of the iteration. But what if the requirements change and we need to have the elements ordered by it's key?

TreeMap

Now is the time for TreeMap to shine. A TreeMap can as well store values by key. Plus it will order the map for iteration by its keys, not the insertion order. But this feature has a costly price tag on it. Our insertion and lookup times will grow to O(log N). This is what you have to be aware of if you use a TreeMap.

TreeMaps use a Red-Black-Tree as implementation. For the correct sorting, our keys need to implement the Comparable interface. So, if you plan to use your own classes as keys you will add some extra work here.

package ersocon.net;

import java.util.TreeMap;

public class Tutorial {

   public static void main(String args[]) {

      TreeMap<Integer, String> treeMap = new TreeMap<Integer, String>();

      // Add elements to TreeMap
      treeMap.put(0, "A");
      treeMap.put(-1, "B");
      treeMap.put(1, "C");
      
      // Iterate the map, results?
      for (Integer key : treeMap.keySet()) {
         System.out.println(treeMap.get(key));
      }

      // Output: B, A, C
   }
}

I hope you understand the differences and use cases for the presented map solutions in Java. If you have any comments, thoughts or questions, please use the section below.