Explain the timing causing HashMap.put() to execute an infinite loop

by

To the contrary of what many people think, the main issue with multi-threading and HashMaps is not just a duplicate entry or a vanishing one… As you said, an infinite loop might occur when two or multiple Threads concurrently decide to resize the HashMap.

If the size of the HashMap passes a given threshold, several threads might end up trying to resize it at the same time, and if we are lucky enough (you deployed the code in production already) they will keep going forever…

The issue is caused by the way the void resize(int newCapacity); and void transfer(Entry[] newTable); are implemented, you can take a look at the openjdk source code yourself. A mix of bad luck, good timing, entries that get reversed (ordering is not required in this data structure) and that end up to mistakenly referring to each other while a thread keep going while(e != null)…

While I could try to give you an explanation myself, I want to give credit to Paul Tyma‘s post (I cannot do better than him anyway) where I learned how this worked the first time I decided to figure out why I wasn’t hired for a job several months ago…

http://mailinator.blogspot.com/2009/06/beautiful-race-condition.html

As Paul says, the best word to describe this race is condition is: beautiful

More Related Contents:

  1. Is iterating ConcurrentHashMap values thread safe?
  2. Is a HashMap thread-safe for different keys?
  3. Why there is no ConcurrentHashSet against ConcurrentHashMap
  4. Is it safe to get values from a java.util.HashMap from multiple threads (no modification)?
  5. Are non-synchronised static methods thread safe if they don’t modify static class variables?
  6. Thread Confinement
  7. How does ConcurrentHashMap work internally?
  8. Are arrays thread-safe in Java?
  9. Not thread-safe Object publishing
  10. what is the method to delete hashmap entry
  11. How to check if an integer is in a set of given ranges? [closed]
  12. Java 8 Streams hashmap
  13. What’s the difference between Thread start() and Runnable run()
  14. Java Compare Two Lists
  15. Synchronizing on String objects in Java
  16. java.lang.OutOfMemoryError: GC overhead limit exceeded [duplicate]
  17. Volatile boolean vs AtomicBoolean
  18. What’s a monitor in Java?
  19. Java HashMap performance optimization / alternative
  20. How to use ConcurrentLinkedQueue?
  21. Java threads and number of cores
  22. Java volatile reference vs. AtomicReference
  23. Simplest and understandable example of volatile keyword in Java
  24. Allowing the this reference to escape
  25. How to prove that HashMap in java is not thread-safe
  26. What exactly is bucket in hashmap?
  27. Why does java.util.concurrent.ArrayBlockingQueue use ‘while’ loops instead of ‘if’ around calls to await()?
  28. Changing HashMap keys during iteration
  29. Is Random class thread safe?
  30. What is the most frequent concurrency issue you’ve encountered in Java? [closed]

Leave a Comment