Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Java HashMap race condition

I am trying to find out if there is going to be any race condition in this piece of code. If the key weren't 'Thread.currentThread' then I would think yes. But since the thread itself is key, how is it possible to have a race condition? No other thread can possibly update the same key in the HashMap!

public class SessionTracker {

     static private final Map<Thread,Session>  threadSessionMap = new HashMap<Thread,Session>();

     static public Session get() {
         return threadSessionMap.get(Thread.currentThread());
     }

     static public void set(Session s) {
         threadSessionMap.put(Thread.currentThread(),s);
     }

     static public void reset() {
         threadSessionMap.remove(Thread.currentThread());
     }
}
like image 613
JavaLearner Avatar asked Oct 20 '11 03:10

JavaLearner


2 Answers

The answer is yes, there are potential race conditions:

  • when resizing an HashMap by two threads at the same time
  • when collisions happens. Collision can happen when two elements map to the same cell even if they have a different hashcode. During the conflict resolution, there can be a race condition and one added key/value pair could be overwritten by another pair inserted by another thread.

To explain better what I mean on the second point, I was looking at the source code of HashMap in OpenJdk 7

389        int hash = hash(key.hashCode());
390        int i = indexFor(hash, table.length);

First it calculates an Hash of your key (combining two hash functions), then it maps to a cell with indexFor, then it checks if that cell contains the same key or is already occupied by another one. If it's the same key, it just overwrite the value and there is no problem here.

If it's occupied it looks at the next cell and then the next until it finds an empty position and call addEntry(), which could even decide to resize the array if the array is more loaded than a certain loadFactor.

Our table containing the entries is just a vector of Entry which holds key and value.

146    /**
147     * The table, resized as necessary. Length MUST Always be a power of two.
148     */
149    transient Entry[] table;

In a concurrent environment, all sort of evil things can happen, for instance one thread gets a collision for cell number 5 and looks for the next cell (6) and finds it empty.

Meanwhile another thread gets an index of 6 as a result of indexFor and both decide to use that cell at the same time, one of the two overwriting the other.

like image 152
stivlo Avatar answered Nov 03 '22 06:11

stivlo


Without getting into specific details of the Hashmap implementations, I would say that there is still the possibility of an error, given the fact that the Hashmap class is not safe for concurrent access.

While I agree that there should be only 1 modification to a single key at a time, because you are using currentThread(), there is still the possibility that multiple threads will be modifying the Hashmap concurrently. Unless you look at the specific implementation, you should not assume that only concurrent access to the same key would cause a problem on the Hashmap, and that concurrent modification to different keys would not.

Imagine a case where two different keys generate to the same hash value, and its easy to see that there can still be errors with concurrent modification.

like image 21
Steven Mastandrea Avatar answered Nov 03 '22 07:11

Steven Mastandrea