What is the problem with the resizing strategy? It hurts concurrency. We have actually reduced the affair to a strictly sequential execution, which is a bottleneck. As a goal, we should strive for allowing more concurrency threads to work on the hash set, which still ensures thread safety!
The following diagram shows two concurrent adds. As both the threads work on separate shared mutable states, we could allow both of them the access:
Two (or more) threads could be adding elements to different buckets, while at the same time other threads could be searching the hash set.
The lock striping pattern allows us to do just that. The following diagram shows how the pattern works:
Instead of a single lock, we maintain an array of locks. The following code shows the algorithm:
x <- compute the hash for the element lock(x % length of locks array) // 5 for the above diagram insert the element for the list at (x % length of table) // 10 for the above
The following is...