Is a HashMap thread-safe for different keys?

by

In @dotsid’s answer he says this:

If you change a HashMap in any way then your code is simply broken.

He is correct. A HashMap that is updated without synchronization will break even if the threads are using disjoint sets of keys. Here are just some1 of the things that can go wrong.

  • If one thread does a put, then another thread may see a stale value for the hashmap’s size.

  • If one thread does a put with a key that is (currently) in the same hash bucket as the second thread’s key, second thread’s map entry might get lost, temporarily or permanently. It depends on how the hash chains (or whatever) are implemented.

  • When a thread does a put that triggers a rebuild of the table, another thread may see transient or stale versions of the hashtable array reference, its size, its contents or the hash chains. Chaos may ensue.

  • When a thread does a put for a key that collides with some key used by some other thread, and the latter thread does a put for its key, then the latter might see a stale copy of hash chain reference. Chaos may ensue.

  • When one thread probes the table with a key that collides with one of some other thread’s keys, it may encounter that key on the chain. It will call equals on that key, and if the threads are not synchronized, the equals method may encounter stale state in that key.

And if you have two threads simultaneously doing put or remove requests, there are numerous opportunities for race conditions.

I can think of three solutions:

  1. Use a ConcurrentHashMap.
  2. Use a regular HashMap but synchronize on the outside; e.g. using primitive mutexes, Lock objects, etcetera. But beware that this could lead to a concurrency bottleneck due to lock contention.
  3. Use a different HashMap for each thread. If the threads really have a disjoint set of keys, then there should be no need (from an algorithmic perspective) for them to share a single Map. Indeed, if your algorithms involve the threads iterating the keys, values or entries of the map at some point, splitting the single map into multiple maps could give a significant speedup for that part of the processing.

1 – We cannot enumerate all of the possible things that could go wrong. For a start, we can’t predict how all JVMs will handle the unspecified aspects of the JMM … on all platforms. But you should NOT be relying on that kind of information anyway. All you need to know is that it is fundamentally wrong to use a HashMap like this. An application that does this is broken … even if you haven’t observed the symptoms of the brokenness yet.

More Related Contents:

  1. Synchronizing on String objects in Java
  2. Is java.sql.Connection thread safe?
  3. Java synchronized method lock on object, or method?
  4. Is iterating ConcurrentHashMap values thread safe?
  5. Thread safe multitons in Java
  6. Is a volatile int in Java thread-safe?
  7. Is it safe to get values from a java.util.HashMap from multiple threads (no modification)?
  8. Use cases for RxJava schedulers
  9. How to stop a thread created by implementing runnable interface?
  10. Throttling javafx gui updates
  11. Are non-synchronised static methods thread safe if they don’t modify static class variables?
  12. Odd even number printing using thread
  13. How do I prove programmatically that StringBuilder is not threadsafe?
  14. How to prove that HashMap in java is not thread-safe
  15. Is Random class thread safe?
  16. Thread Confinement
  17. Testing initialization safety of final fields
  18. Thread safe Hash Map?
  19. Java Synchronization [closed]
  20. Is Cipher thread-safe?
  21. How to get the Context from anywhere? [duplicate]
  22. Is LinkedList thread-safe when I’m accessing it with offer and poll exclusively?
  23. Explain the timing causing HashMap.put() to execute an infinite loop
  24. Regarding thread safety of servlet [duplicate]
  25. Are Thread.stop and friends ever safe in Java?
  26. Copying a HashMap in Java
  27. Java HashMap nested generics with wildcards
  28. Is there a way to get the value of a HashMap randomly in Java?
  29. How to find a Java thread running on Linux with ps -axl?
  30. Executing Dependent tasks in parallel in Java

Leave a Comment