This was recently a question I was asked in a screening and it got me thinking. I never totally settled on how the conversation ended, and I did some digging. None of the answers I saw seemed satisfactory to me.
The question is essentially "how would you implement a thread safe hash map?" Obviously protect with a mutex, but then you have to deal with contention of multiple threads waiting on a single mutex which means access isn't truly concurrent, and so on. We eventually got to a simple design of n buckets in the hash table, with one mutex corresponding to one bucket. Easy enough, and this is where I see a lot of answers to this question on other sites stop. It does not handle what happens when the hash table is resized or for whatever reason the table is rehashed.
It was supposed that one thread would manage rehashing, so our simple design becomes n + 1 mutexes, and the managing thread has to lock all n + 1 mutexes to rehash. However, any thread that is waiting on any of the n buckets could gain ownership to a mutex which is now matched matched to a different bucket (after a rehash). Only answer I could come up w/ basically went back to a non-concurrent hash map.
I believe java has some type of concurrent hash map out of the box, but I live in a C++ world. I passed the screen but I'm still very curious about this as I never had that "a-ha" moment and it sounds like a practical application.
I do think read-write locks may be a somewhat suitable answer but again, I think there is still the caveat when rehashing.
Best Answer
I have wrestled with this. I did a few iterations on my design...
First solution: Just have a hash table with a global lock.
Second solution: Wait free fixed size hash table. We need to figure out that it is possible to implement a wait free thread safe hash set with fixed size. To do this, we are going to use an array, where the index is the hash, we will use linear probing, and all operations are going to be interlocked.
So, yes, we will have locking. However a thread will never be spin waiting or waiting on a wait handle. It takes some work to figure out how to guarantee they are all atomic.
Third solution: Lock on growth. The naive approach is to lock the structure, create a new array, copy all the data, then unlock. That works, it is thread safe. We can get away with locking only on growth because as long as the size does not change we can work as in the prior solution.
Except I do not like the down time. There are threads waiting for the copy to complete. We can do better...
Fourth solution: Cooperative growth. First implement a thread safe state machine so that the structure can change from normal use to growth and back. Next, every thread that wants to do an operation, instead of waiting, will cooperate in copying data to the new array. How? We can have an index that we increment, again with an interlocked operation... each thread increments the index, takes the element, computes where to place it in the new array, writes it there and then loops until the operation is completed.
There is a problem: it does not shrink.
Fifth solution: Sparse array. Instead of using an array, we can use a tree of arrays, and use it like a sparse array. Its size will be enough to allocate every value that our hash function can output. Now, threads can nodes as needed. We will keep track of usage of each node, that is how many children are occupied and how many threads are currently using it. When usage reaches zero, we can remove it... wait... locking? turns out we can do an optimistic solution: we keep to references to the node data, every thread will write one after operation. The thread that found 0 will erase, then read (another thread could have written it), and then copy to the second reference. All interlocked operations.
By the way, those atomic operations? Yeah, it turns out they are some common patterns we can abstract out. At the end, I only have
DoMayIncrementfor operation that may or may not add items,DoMayDecrementfor those that may or may not remove, andDofor everything else. They will take callbacks with references to the values, which the callback code does not need to know exactly where they are stored, and we build on top of that more specific operations and add probing to handle collisions along the way.Oh, I forgot, to minimize allocations I pool the arrays that make up the nodes of the tree.
Sixth solution: Phil Bagwell's Ideal Hash Trees. It is similar to my fifth solution. Main difference is that the tree does not behave like a sparse array where all values are inserted at the same depth. Instead, the depth of tree branches is dynamic. When a collision happens, the old node is replaced with a branch where the old node is reinserted in addition to the new node. This should make Bagwell’s solution more memory efficient on the average case. Bagwell also pools arrays. Bagwell does not elaborate on shrinking.
The fifth solution is what I currently use to backport/polyfill
ConcurrentDictionary<TKey, TValue>to .NET 2.0. More precisely, my backport ofConcurrentDictionary<TKey, TValue>wraps around a custom typeThreadSafeDictionary<TKey, TValue>which uses aBucket<KeyValuePair<TKey, TValue>>which implement atomic operations over aBucketCorewhich is my thread-safe sparse array thingy, which has the logic for shrink and grow.