In previous posts, we introduced the Map collection and some implementations like HashMap and TreeMap.

In this post, we are going to compare HashMap and TreeMap performance using the get and contains operations.

TRY IT YOURSELF: You can find the source code of this post here.

Java Collections Map Series

• Part 1: Java Collections: Map
• Part 2: HashMap vs TreeMap: Get and Contains key (You are here)
• Part 3: HashMap vs TreeMap: Put

If you like this post and are interested in hearing more about my journey as a Software Engineer, you can follow me on Twitter and travel together.

Environment

• JDK 11.0.3, OpenJDK 64-Bit Server VM, 11.0.3+7-Ubuntu-1ubuntu218.04.1
• Ubuntu 18.04
• Memory 15,6 GiB
• Processor Intel® Core™ i7-7500U CPU @ 2.70GHz × 4
• Graphics Intel® HD Graphics 620 (Kaby Lake GT2)
• OS 64-bit
• Disk 387,9 GB
• Intellj IDE Community 2018.3

Approach

• We are going to use JMH for the micro benchmark.
• We are going to use a list of 10.000.000 of elements, generated randomly, and we are going to calculate the average response time in 10 iterations.
• As JMH doesn’t allow sharing data between benchmarks, we are going to create a file with the list of elements, and read from it by each benchmark. In that way, we guarantee we are measuring the same scenario.

Getting a Value – get(key) – containsKey(key)

Now, let’s see the code for measuring how HashMap and TreeMap behave when we need to get a value from a key:

NOTE: containsKey(key) uses get(key) behind scenes, so, we are going to talk about get(key).

    @Test
  public void get()
          throws RunnerException, IOException {
    Utils.populateToFile();

    Options opt = new OptionsBuilder()
            .include(
                    HashMapVsTreeMapGetTest.class
                            .getSimpleName())
            .detectJvmArgs()
            .build();

    Collection runResults = new Runner(opt)
            .run();

    Result hashMapResult = Utils
            .find("hashMap",
                    runResults);
    Result treeMapResult = Utils
            .find("treeMap",
                    runResults);

    assertThat(hashMapResult.getScore())
            .isLessThan(treeMapResult.getScore());
  }

  @Benchmark
  @Measurement(iterations = Utils.amountIterations, batchSize = 1, time = 1)
  @BenchmarkMode(Mode.SingleShotTime)
  @Fork(1)
  @Warmup(iterations = 10)
  @OutputTimeUnit(TimeUnit.MILLISECONDS)
  public HashMap hashMap(
          HashMapExecutionPlan executionPlan) {
    HashMap hashMap = executionPlan.hashMap;

    hashMap.get(ExecutionPlan.element);

    return hashMap;
  }

  @Benchmark
  @Measurement(iterations = Utils.amountIterations, batchSize = 1, time = 1)
  @BenchmarkMode(Mode.SingleShotTime)
  @Fork(1)
  @Warmup(iterations = 10)
  @OutputTimeUnit(TimeUnit.MILLISECONDS)
  public TreeMap treeMap(
          TreeMapExecutionPlan executionPlan) {
    TreeMap treeMap = executionPlan.treeMap;

    treeMap.get(ExecutionPlan.element);

    return treeMap;
  }

Now, let’s see the results:

That is pretty interesting, TreeMap is slower than HashMap, but, both, are pretty fast. Let’s see why they behave like that.

HashMap

Well, let’s use this example for HashMap:

NOTE: The HashMap state could not be exactly the same for the given entries, this is just an example.

There, we see the current state of the HashMap, where the number is the hash code of the key. Now, we want to get the “C” key. The following is the general algorithm HashMap does to find the key:

1. Get the hash code of the key you are searching for. In this case, as the key is a String, the algorithm uses the String.hashCode() method. The value will be 98.

int code = "C".hashCode()

2. Now, we need to find the right index for the 96 hash code, over the HashMap array. The HashMap array has 7 positions, so, an xor operation is performed (the details of how are not necessary). Let’s suppose we get 0, so, we choose the 0 index to search the “C” key:

NOTE: Of course, when you insert the C key (put(key, value)), the algorithm uses the same approach.

3. Next, we need to check if the linked list on the 0 index, contains the key “C” we are searching for. The worst case scenario is that the key is in the last position. We use the String.equals() method to check if the key exists or not:

NOTE: As you can see, equals and hashCode are pretty important for the HashMap to work well, so, if you use a complex key, a class that you own, you should implement equals and hashCode.

NOTE2: This is not the exact process, but it helps to understand the HashMap internals.

We can conclude:

• hashCode and equals are pretty important on the key object.
• Accessing the current index on the array, requires O(1).
• Searching the key over the linked list, requires O(M), where M is the size of the linked list. This size should be lower than N, which is the total elements on the Map, as we will discuss in following posts.
• If the HashMap doesn’t balance well because the hashCode is not well generated, the worst case scenario could be that all the elements will be in the same index, which will require O(N) to find an element.
• Also, the memory space of a HashMap depends on the array size (S) plus the amount of entries (N). The array could have empty positions, which is a waste of space.

TreeMap

Well, let’s use this example for the TreeMap:

There, we see the current state of the TreeMap. This is a red-black tree, a binary tree who balances itself when it needs to. As this is a binary tree, we must have a way to compare one key to other, so, we can sort the keys. The key objects require to implement Comparable, also, you can pass a Comparator object to the TreeMap constructor. The following is the general algorithm TreeMap does to find the key:

1. We start on the root. We compare “C” with “B” keys using the Comparable interface "C".compareTo("B"). This will return if C is lower, greater or equal to B, and based on that, we choose a side of the binary tree. In this case, we choose right, as C is greater than B:

2. We repeat the process from D node. We compare “C” with “D” keys using the Comparable interface "C".compareTo("D") and we choose left, as C is lower than D:

3. Finally, we repeat the process from C node. We compare “C” with “C” keys using the Comparable interface "C".compareTo("C") and they are equal, so, we found the node we are searching for.

NOTE: As you can see, the implementation of Comparable or Comparator are pretty important to get a TreeMap working well.

We can conclude:

• Comparable or Comparator are pretty important on the key object.
• An error will be thrown if you try to create a TreeMap where the key is not Comparable, or you didn’t set a Comparetor object.
• TreeMap is a binary tree, so, it requires O(logn) to find a key.
• Also, the memory space is N.

Summary

Now, this is a summary of the amount of operations in get operation between HashMap and TreeMap:

		HashMap		TreeMap
Operation	Method	Best	Worst	Best	Worst
Get	get(key)	1	1 + n	1	log n

Then, this is a summary of the Big O complexity in get operation between HashMap and TreeMap:

		HashMap		TreeMap
Operation	Method	Best	Worst	Best	Worst
Get	get(key)	O(1)	O(n)	O(1)	O(log n)

NOTE: Remember, the worst case scenario of the HashMap is based on the assumption that all the elements were inserted in the same index, which is unlikely if you set up well the HashMap. Usually, the default values works fine.

Final Thought

As we saw, HashMap is better than TreeMap when we talk about get operation, but, both are pretty fast. Also, take into account that if you need to traversal the map in order, TreeMap should be the first option.

In the following post, we are going to talk about put operation.

If you liked this post and are interested in hearing more about my journey as a Software Engineer, you can follow me on Twitter and travel together.