# Concurrent, atomic MSI hash tables

DevFeed: [Concurrent, atomic MSI hash tables](<https://devfeed.tech/articles/concurrent-atomic-msi-hash-tables-20515.md>)

Original publisher: [Read original article](<https://nullprogram.com/blog/2026/05/06/>)

Published: 2026-05-06T02:01:17Z

Content type: tutorial

Language: en

Sources: [Chris Wellons](<https://devfeed.tech/sources/chris-wellons.md>)

Topics: [Concurrency](<https://devfeed.tech/topics/concurrency.md>), [Concurrent Programming](<https://devfeed.tech/topics/concurrent-programming.md>), [Code](<https://devfeed.tech/topics/code.md>), [gcc](<https://devfeed.tech/topics/gcc.md>), [Processes](<https://devfeed.tech/topics/processes.md>)

Tags: [article](<https://devfeed.tech/tags/article.md>), [c](<https://devfeed.tech/tags/c.md>), [code](<https://devfeed.tech/tags/code.md>), [concurrency](<https://devfeed.tech/tags/concurrency.md>), [concurrent](<https://devfeed.tech/tags/concurrent.md>), [gcc](<https://devfeed.tech/tags/gcc.md>), [processes](<https://devfeed.tech/tags/processes.md>), [thread](<https://devfeed.tech/tags/thread.md>)

## AI overview

This article explains how to add atomic operations to Mask-Step-Index (MSI) hash tables so they can be accessed concurrently without data races. It covers single-producer and multiple-consumer designs, relaxed atomics, and acquire-release synchronization when published objects must be safely observed.

## Source excerpt

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] || table[index]==key) { return table + index; } } } Keys must be non-zero, and tables are zero-initialized. Usage example: // Initialization enum { exp = 8 }; int32_t table[1<<8] = {}; // Producer for (int i = 0; i < nkeys; i++) { *lookup(keys[i], table, exp) = keys[i]; } // Consumer int32_t key = 1234; bool present = *lookup(key, table, exp); The only problem is the data race on table slots. Since consumers can tolerate out-of-order insertions, ordering does not matter and relaxed atomics eliminate the data race. Insert and query now have different requirements, so it makes sense to distinguish them. Starting with the latter: bool contains(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; int32_t k = __atomic_load_n(table+index, __ATOMIC_RELAXED); if (!k) { return false; } else if (k == ke