Search This Blog

Wednesday, May 22, 2019

Race conditions in HashMap

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
        int hash = hash(key.hashCode());
        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.
     * The table, resized as necessary. Length MUST Always be a power of two.
    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.

No comments :

Post a Comment