Hashtable, HashMap, ConcurrentHashMap: Performance – DZone Java

There are a good number of articles that articulate functional differences between HashMap, Hashtable, and ConcurrentHashMap. This post compares the performance behavior of these data structures through practical examples. If you don’t have the patience to read the entire post, here is the bottom line: when you are confronted with the decision of whether to use HashMap, Hashtable, or ConcurrentHashMap, consider using ConcurrentHashMap since it’s thread-safe implementation without compromise in performance.

Performance Study

 To study the performance characteristics, I have put together this sample program:

1 public class HashMapPerformance { 
2
3   public static int ITERATION_COUNT = 10000000; 
4   
5   private static AtomicInteger exitThreadCount = new AtomicInteger(0);   
6   
7   public static HashMap<Integer, Integer> myHashMap; 
8   
9   public static void initData() { 
10      
11      myHashMap = new HashMap<>(1000); 
12      
13      for (int counter = 0; counter < 1000; ++counter) { 
14         
15         myHashMap.put(counter, counter); 
16      }      
17   } 
18   
19   private static class Writer extends Thread{ 
20 
21      public void run() { 
22         
23         Random random = new Random(); 
24         
25         for (int iteration = 0; iteration < ITERATION_COUNT; ++iteration) { 
26            
27            int counter = random.nextInt(1000 - 1);         
28            myHashMap.put(counter, counter);            
29         } 
30         
31         exitThreadCount.incrementAndGet(); 
32      } 
33   } 
34   
35   private static class Reader extends Thread{ 
36 
37      public void run() { 
38         
39         Random random = new Random(); 
40         
41         for (int iteration = 0; iteration < ITERATION_COUNT; ++iteration) { 
42 
43            int counter = random.nextInt(1000 - 1);         
44            myHashMap.get(counter); 
45         } 
46         
47         exitThreadCount.incrementAndGet(); 
48      } 
49   }      
50 
51   public static void main (String args[]) throws Exception { 
52      
53      initData(); 
54      
55      long start = System.currentTimeMillis(); 
56      
57      // Create 10 Writer Threads 
58      for (int counter = 0; counter < 10; ++counter) { 
59         
60         new Writer().start(); 
61      } 
62      
63      // Create 10 Reader Threads 
64      for (int counter = 0; counter < 10; ++counter) { 
65         
66         new Reader().start(); 
67      } 
68      
69      // Wait for all threads to complete 
70      while (exitThreadCount.get() < 20) { 
71         Thread.sleep(100); 
72      } 
73      
74      System.out.println("Total execution Time(ms): " + (System.currentTimeMillis() - start) );      
75   }   
76 }

This program triggers multiple threads to do a concurrent read and write to the java.util.HashMap.

Let’s walk through this code. The primary object in this program is myHashMap, which is defined in line #7. This object is of type java.util.HashMap and it’s initialized with 1000 records in the method initData(), which is defined in line #9. Both the key and value in the HashMap have the same integer value. Thus this HashMap will look as shown in the below diagram:

Data in the HashMap

The Writer Thread is defined in line #19. This thread generates a random number between 0 to 1000 and inserts the generated number into the HashMap, repeatedly, 10 million times. We are randomly generating numbers so that records can be inserted into different parts of the HashMap data structure. Similarly, there is a Reader thread defined in line #35. This thread generates a random number between 0 to 1000 and reads the generated number from the HashMap. 

Also, notice the main() method defined in line #51. In this method, you will see 10 Writer threads are created and launched. Similarly, 10 Reader threads are created and launched. Then in line 70, there is code logic that will prevent the program from terminating until all the Reader and Writer threads complete their work. 

HashMap Performance

We executed the above program several times. The average execution time of the program was 3.16 seconds.

Hashtable Performance

In order to study the Hashtable performance, we replaced line #7 with java.util.Hashtable and modified the Reader and Writer threads to read and write from the Hashtable. We then executed the program several times. The average execution time of the program was 56.27 seconds.

ConcurrentHashMap Performance

In order to study the Hashtable performance, we basically replaced line #7 with java.util.concurrent.ConcurrentHashMap and modified the Reader and Writer threads to read and write from the ConcurrentHashMap. We then executed the program several times. The average execution time of the program was 4.26 seconds.

HashMap, Hashtable, ConcurrentHashMap performance comparison

The below table summarizes the execution time of each data structure: 

Notice HashMap has the best performance; however, it’s not thread-safe. It has a scary problem that can cause the threads to go on an infinite loop, which would ultimately cause the application’s CPU to spike up. 

If you notice ConcurrentHashMap is slightly slower performing than HashMap; however, it’s a 100% thread-safe implementation. 

On the other hand, Hashtable is also a thread-safe implementation, but it’s 18 times slower than HashMap for this test scenario. 

Why Is Hashtable So Slow?

Hashtable is so slow because both the get() and put() methods on this object are synchronized (if you are interested, you can see the Hashtable source code here). When a method is synchronized, at any given point in time, only one thread will be allowed to invoke it. 

In our sample program, there are 20 threads.  10 threads are invoking the get() method, and another 10 threads are invoking the put() method. In these 20 threads, when one thread is executing, the remaining 19 threads will be in a BLOCKED state. Only after the initial thread exits the get() or put() method, the remaining threads would be able to progress forward. Thus, there is going to be a significant degradation in the performance.

To confirm this behavior, we executed the above program, captured the thread dump, and analyzed it with fastThread (a thread dump analysis tool) that generated this analysis report. Below is the excerpt from the report that shows the transitive dependency graph of BLOCKED threads.

Threads BLOCKED on Hashtable (generated by fastThread)

The report was showing that 19 threads were in a BLOCKED state, while one of the threads (i.e., Thread-15) is executing the get() method in the Hashtable. Thus only after Thread-15 exits the get() method, other threads would be able to progress forward and execute the get() and put() method. This will cause a considerable slowdown in the application performance.

Conclusion

If you have a need to use a map data structure, you may consider using ConcurrentHashMap, which provides similar performance characteristics to HashMap but at the same time, provides thread-safe behavior like Hashtable.

Video