Concurrent Hash Table

Let's look at the design and implementation of a concurrent hash table.

Let’s end this chapter with a simple and widely applicable concurrent data structure, the hash table. Let’s focus on a simple hash table that does not resize. A little more work is required to handle resizing, which is left as an exercise for you. Feel free to present your ideas on the Discuss forum thread!

%19 node_2 Key 3 node_1 Key 2 node_1_1 Val 2 node_1->node_1_1 node_1_2 Val 3 node_1_1->node_1_2 node_0 Key 1 node_0_1 Val 1 node_0->node_0_1

This concurrent hash table, shown below, is straightforward, is built using the concurrent lists we developed earlier, and works incredibly well. The reason for its good performance is that instead of having a single lock for the entire structure, it uses a lock per hash bucket (each of which is represented by a list). Doing so enables many concurrent operations to take place.

Press + to interact
#define BUCKETS (101)
typedef struct __hash_t {
    list_t lists[BUCKETS];
} hash_t;
void Hash_Init(hash_t *H) {
    int i;
    for (i = 0; i < BUCKETS; i++)
        List_Init(&H->lists[i]);
}
int Hash_Insert(hash_t *H, int key) {
    return List_Insert(&H->lists[key % BUCKETS], key);
}
int Hash_Lookup(hash_t *H, int key) {
    return List_Lookup(&H->lists[key % BUCKETS], key);
}

The graph below shows the performance of the hash table under concurrent updates (from 10,000 to 50,000 concurrent updates from each of four threads, on the same iMac with four CPUs). Also shown, for the sake of comparison, is the performance of a linked list (with a single lock). As you can see from the graph, this simple concurrent hash table scales magnificently; the linked list, in contrast, does not.

Get hands-on with 1400+ tech skills courses.