Home » Java » Core Java » Java Hashtable, HashMap, ConcurrentHashMap – Performance impact

About Ram Lakshmanan

Ram Lakshmanan
Ram Lakshmanan developed world's finest DevOps tools: GCeasy.io, fastThread.io, HeapHero.io. Every single day, millions & millions of people in North America—bank, travel, and commerce—use the applications that Ram Lakshmanan has architected. Ram is an acclaimed speaker in major conferences on scalability, availability, and performance topics. Recently, he has founded a startup, which specializes in troubleshooting performance problems.

Java Hashtable, HashMap, ConcurrentHashMap – Performance impact

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 patience to read the entire post, here is bottom line: When you confront with the decision of whether to use HashMap or HashTable or ConcurrentHashMap, you can 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

public class HashMapPerformance {

   public static int ITERATION_COUNT = 10000000;
   
   private static AtomicInteger exitThreadCount = new AtomicInteger(0);   
   
   public static HashMap<Integer, Integer> myHashMap;
   
   public static void initData() {
      
      myHashMap = new HashMap<>(1000);
      
      for (int counter = 0; counter < 1000; ++counter) {
         
         myHashMap.put(counter, counter);
      }      
   }
   
   private static class Writer extends Thread{

      public void run() {
         
         Random random = new Random();
         
         for (int iteration = 0; iteration < ITERATION_COUNT; ++iteration) {
            
            int counter = random.nextInt(1000 - 1);         
            myHashMap.put(counter, counter);            
         }
         
         exitThreadCount.incrementAndGet();
      }
   }
   
   private static class Reader extends Thread{

      public void run() {
         
         Random random = new Random();
         
         for (int iteration = 0; iteration < ITERATION_COUNT; ++iteration) {

            int counter = random.nextInt(1000 - 1);         
            myHashMap.get(counter);
         }
         
         exitThreadCount.incrementAndGet();
      }
   }      

   public static void main (String args[]) throws Exception {
      
      initData();
      
      long start = System.currentTimeMillis();
      
      // Create 10 Writer Threads
      for (int counter = 0; counter < 10; ++counter) {
         
         new Writer().start();
      }
      
      // Create 10 Reader Threads
      for (int counter = 0; counter < 10; ++counter) {
         
         new Reader().start();
      }
      
      // Wait for all threads to complete
      while (exitThreadCount.get() < 20) {
         Thread.sleep(100);
      }
      
      System.out.println("Total execution Time(ms): " + (System.currentTimeMillis() - start) );      
   }   
 }

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

 Let’s walk through this code. 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 key and value in the HashMap have the same integer value. Thus this HashMap will look like as shown in the below diagram:

KeyValue
00
11
22
33
::
::
10001000

Fig: Data in the HashMap

 ‘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 for 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. 

 You can also notice ‘main()’ method defined in line #51. In this method you will see 10 ‘Writer’ threads are created & launched. Similarly, 10 ‘Reader’ threads are created & launched. Then in line 70, there is code logic which 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. Average execution time of the program was 3.16 seconds

Hashtable Performance

 In order to study the Hashtable performance, we replaced the 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. Average execution time of the program was 56.27 seconds.

ConcurrentHashMap Performance

 In order to study the HashTable performance, we basically replaced the 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. Average execution time of the program was 4.26 seconds.

HashMap, Hashtable, ConcurrentHashMap performance comparison

 Below table summarizes the execution time of each data structure: 

Data structureExecution Time (secs)
HashMap3.16
ConcurrentHashMap4.26
Hashtable56.27

 If you 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 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 ‘get()’ method, another 10 threads are invoking ‘put()’ method. In these 20 threads when one thread is executing, the remaining 19 threads will be in BLOCKED state. Only after the initial thread exits ‘get()’, ‘put()’ method, 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 and captured the thread dump and analyzed it with fastThread( a thread dump analysis tool). Tool generated this interesting analysis report. Below is the excerpt from the report that shows the transitive dependency graph of BLOCKED threads

Fig: Threads BLOCKED on Hashtable (generated by fastThread)

Report was showing that 19 threads were in 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()’, ‘put()’ method. This will cause considerable slowdown in the application performance.

Conclusion

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

Video

Published on Java Code Geeks with permission by Ram Lakshmanan, partner at our JCG program. See the original article here: Java Hashtable, HashMap, ConcurrentHashMap – Performance impact

Opinions expressed by Java Code Geeks contributors are their own.

(0 rating, 0 votes)
You need to be a registered member to rate this.
Start the discussion Views Tweet it!
Do you want to know how to develop your skillset to become a Java Rockstar?
Subscribe to our newsletter to start Rocking right now!
To get you started we give you our best selling eBooks for FREE!
1. JPA Mini Book
2. JVM Troubleshooting Guide
3. JUnit Tutorial for Unit Testing
4. Java Annotations Tutorial
5. Java Interview Questions
6. Spring Interview Questions
7. Android UI Design
and many more ....
I agree to the Terms and Privacy Policy
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Inline Feedbacks
View all comments