Concurrent, atomic MSI hash tables

Readers will be familiar with Mask-Step-Index (MSI) hash tables, a technique for building fast, open-addressed hash tables in a dozen lines of code. If multiple threads or processes access an MSI table with at least one still inserting elements, care must be taken to avoid data races. This article will show how to add atomic operations to MSI tables in order to support different concurrency constraints. Let’s begin with the simplest case: An integer hash set, no deletions, only one insert thread (single producer), and consumers do not care about insert order. That is, the producer inserts A then B, but consumers may observe B in the table before A. Suppose this is the hash table in the single-threaded case: int32_t *lookup(int32_t key, int32_t *table, int exp) { uint64_t hash = ((uint64_t)key * 1111111111111111111u) >> 32; uint32_t mask = ((uint32_t)1 << exp) - 1; uint32_t step = (hash >> (32 - exp)) | 1; for (uint32_t index = hash;;) { index = (index + step) & mask; if (!table[index]…