I feel that using a linked list as the underlying structure combined with fine grained locking is the wrong direction to go. What is the scenario in which I would use this collection over an unordered_map and some locking scheme? A linked list is a very (very very) poor performer and I would only use a linked list for implementing a collection which is synchronized based on CAS operations instead of locking. Since yo…
Thanks for your feedback. The linked_lists can definitely be replaced, and I am working on finding a suitable data structure to maintain the individual buckets. However, the "unordered_map" with one global mutex will not achieve what I am trying to do, i.e., allow multiple threads to simultaneously write into the same hash_map, unless two (or more) of them collide on the same bucket at the same time.
Re: Show HN: A concurrent thread-safe hash map implemented in C++
#11It's true that a single global mutex will not provide such locking granularity, but unordered_map does provide bucket api allowing you to find a bucket by key.
This means that for a pair p, you can find the relevant bucket at index i, lock mutex i and insert to the map. The only problem you need to deal with is rehashing which can be solved by wrapping the hash function with a modulo operation and playing around with the max_load_factor.
(I could write a short sample later, it would be a very thin wrapper.)