HashTable concurrency

Question

I have a HashTable which is accessed by multiple threads. For example lets look at three threads:

Thread A does Hash.Insert("a",new object());

Thread B does Hash.Insert("b",new object());

Thread C does Hash.Insert("a",new object());

For some reasons, I cannot use a Lock on the entire Hash

I dont care about the order or which object will be at the hash at the end of the process. The only thing I care about is not getting data corruption by updating the same cell from different threads.

What are my options? or is it not a problem and the HashTable handles that by itself and keeps the data in tact.

"For some reasons, I cannot use a Lock on the entire Hash" Can you explain that requirement? Is it only performance? — CodesInChaos, Jan 30 '12 at 08:14
@CodeInChaos there can be thousands of requests concurrently so i am more worried about starvation because its possible for a thread that aquired a lock to never get processor time... — Amit Raz, Jan 30 '12 at 08:26
It's highly unlikely that you'll experience starvation due to non-FIFO processing of the locks. See http://stackoverflow.com/questions/961869/is-there-a-synchronization-class-that-guarantee-fifo-order-in-c. for a synchronization object that guarantees FIFO ordering, which will prevent starvation. — Jim Mischel, Jan 30 '12 at 23:04

score 5 · Accepted Answer · answered Jan 30 '12 at 08:05

5

You could consider using something like:

ConcurrentDictionary<string, object> Hash = new ConcurrentDictionary<string, object>();

from the System.Collections.Concurrent namespace.

answered Jan 30 '12 at 08:05

sblom

26,911
4
71
95

I thought about it but that depends on how ConcurrentDictionary is implemented. Does it lock the entire Hash? or is it more sophisticated? – Amit Raz Jan 30 '12 at 08:11
@Amit I'm pretty sure the implementation is lockless, but that's of course only an implementation detail. But there is no way to directly observe the difference between lockless and locking implementations, except lockless is often faster. – CodesInChaos Jan 30 '12 at 08:13
from a quick look in reflector it seems that the concurrent dictionary uses bucket locks and it seems it has several lockes and each number of cells gets one lock. Hope its good enough – Amit Raz Jan 30 '12 at 08:21

score 3 · Answer 2 · answered Jan 30 '12 at 22:50

ConcurrentDictionary should work for you. It is not lock free, but it does not "lock the entire hash" except in certain situations.

It uses two collections, a lock array and a collection of hash buckets.
The number of lock buckets can be controlled by setting the concurrency level, and the initial number of hash buckets can be controlled by setting the initial capacity. (these are both constructor parameters).

Each bucket in the lock array covers several (well at least one really) hash buckets using a simple modulo hash.

The only times that the concurrent dictionary locks all the lock buckets are:

When resizing the the hash buckets.
When reading the public Keys property.
When reading the public Values Property.
When Reading the public Count Property.
When reading the public IsEmpty Property.
When Calling Clear().
When serializing.

With the exception of resizing these are all easily avoidable.

Resizing can be avoided if you can predict the max number of items in the dictionary.

HashTable concurrency

2 Answers2