libcuckoo: a header-only concurrent hash table with multiple writers

A hash table that several writers may use at once

The library is described in one sentence: libcuckoo provides a high-performance, compact hash table that allows multiple concurrent reader and writer threads.

That last clause is the design goal, and it is where cuckoo hashing earns its place. A conventional hash table with a lock serialises access, and a conventional one without a lock is either unsafe or needs a far more complicated protocol. Cuckoo hashing sidesteps the problem structurally. Each key has a small set of candidate positions, and an insert that finds its first choice occupied can move the resident key to one of its own alternatives, cascading until everything fits. A move is a single element relocation, which is what makes it possible to do this without a global lock, and it is why the table is described as compact.

The authors are Manu Goyal, Bin Fan, Xiaozhou Li, David G. Andersen and Michael Kaminsky, and the Doxygen generated documentation is published at the project page. The code lives in a libcuckoo/ subdirectory, with a C wrapper in libcuckoo-c/, examples under examples/, and the test suites under tests/.

The repository is not archived, the last push was on 2026-10-18, and there are no GitHub releases, so the library is consumed as source rather than as a tagged artefact, which suits a header-only library in any case.

The intended user is a C++ developer with a concurrent workload and a specific problem: a map that is read on every request and written often enough that a global mutex shows up in a profile.

The papers, and why the source is the reference

The README points at two papers for the algorithm and citations, one from NSDI 2013 and one from EuroSys 2014. The first is MemC3, a compact and concurrent memcache, and the second is on algorithmic improvements for fast concurrent cuckoo hashing.

Then comes the sentence that matters to anyone reading the code today. Some of the details of the hashing algorithm have been improved since that work, and the example given is that the previous algorithm in the first paper serializes all writer threads, while the current implementation supports multiple concurrent writers. The README adds that the source code is now the definitive reference.

That is a useful warning for readers coming from the literature. If you implement from the 2013 paper, you will implement a different concurrency model from the one in the repository, because the write path has been reworked since. The papers explain why the design works and give the citations you need, but the code is the authority on behaviour.

For a reader who has never used a cuckoo table, the practical consequence is that the two papers also tell you what to look for in the implementation. The hash function has to be fast, since it sits on the hot path of every lookup, and the table has to be resizable, since cuckoo hashing can fail to place a key when the table is too full and the whole set has to be rehashed. The README does not describe those details, and the papers are where they are written down.

Header-only means copying a directory, not linking a library

The build section is short because there is not much to build. libcuckoo is a header-only library, so in order to get going you just add the libcuckoo subdirectory to your include path.

There are still two things the CMake build does for you, and the README describes both. It can install the library to a location on your system, and it can build the examples and the tests included in the repository. The README suggests building out of source, in a separate build directory:

mkdir build
cd build

The library is then included by path:

#include <libcuckoo/cuckoohash_map.hh>

The usage section adds the compiler requirement that catches people out. When compiling your own files with libcuckoo, always remember to enable C++11 features on your compiler. On g++ that is -std=c++11, and on clang++ it is -std=c++11 -stdlib=libc++.

The header-only distribution has a practical upside that is easy to miss. Because there is no library to link, the version of libcuckoo that ends up in your binary is the version whose headers you copied into your tree, and there is no runtime version negotiation to think about. The cost is that upgrades are a copy operation rather than a package manager action, so the header set has to be tracked deliberately in your own repository.

CMake flags decide which parts of the tree get built

The build is driven by flags that select which directories are compiled, and the README lists them one by one.

The two standard ones are -DCMAKE_INSTALL_PREFIX, which sets the location where the libcuckoo header files are installed, and -DCMAKE_BUILD_TYPE, which enables different types of build flags for different purposes. The rest are switches for the parts of the repository.

-DBUILD_EXAMPLES=1 builds the examples directory, -DBUILD_TESTS=1 builds all tests in the tests directory, -DBUILD_STRESS_TESTS=1 builds all tests in the tests/stress-tests directory, -DBUILD_UNIT_TESTS=1 builds all tests in the tests/unit-tests directory, and -DBUILD_UNIVERSAL_BENCHMARK=1 builds the universal benchmark in the tests/universal-benchmark directory.

The universal benchmark gets a sentence of its own because it is not an ordinary test. The README describes it as a benchmark that allows you to test a variety of operations in arbitrary percentages, with specific keys and values, and points to the README in the benchmark directory for details. In other words, it lets you construct a workload mix of your own rather than running one fixed pattern, which is what you want when you are trying to reproduce a production mix.

The full sequence for building everything into a local installation directory, taken from the README, is:

cmake -DCMAKE_INSTALL_PREFIX=../install -DBUILD_EXAMPLES=1 -DBUILD_TESTS=1 ..
make all
make install

The default is therefore a small build. If you are adding libcuckoo to a project and want nothing but the headers, you do not need any of the BUILD_ flags at all.

The stated compiler and platform requirements are old

The requirements section lists what the library has been tested on, and the numbers date the project.

It has been tested on Mac OSX 10.8 and later and Ubuntu 12.04 and later. It compiles with clang++ 3.3 and later and g++ 4.8 and later, but the README strongly suggests using the latest versions of both compilers, and the reason given is specific: they have greatly improved support for atomic operations.

That reason is the whole story of the library's portability constraints. Concurrent cuckoo hashing is built out of atomic operations on shared memory, and the correctness of the whole thing depends on the compiler generating the right instructions for them, with the right memory ordering. A compiler whose atomic support is weak or whose memory model understanding is dated is a genuine risk rather than a missing feature.

Building the library requires CMake 3.1.0 or newer, and the README gives the install command for it on Ubuntu:

sudo apt-get update && sudo apt-get install cmake

The combination of requirements and the current state of the repository is worth noting. The tested platforms are versions from more than a decade ago, which in practice means the library is exercised on modern systems by users rather than by the maintainers' test matrix. The header-only distribution and the use of standard atomics are what make that viable, and the strong recommendation to use current compilers is what makes it safe.

The C wrapper for projects that are not C++

Most of the repository is C++, but there is a way in for a project that is not.

The README describes a C wrapper around the table that can be leveraged to use libcuckoo in a C program. The interface consists of a template header and an implementation file that can be used to generate instances of the hashtable for different key-value types. The source lives in a libcuckoo-c/ directory, and the examples directory includes a c_hash.c file that demonstrates it.

The shape of that interface is the interesting part. It is not a single fixed C API with one hard coded set of types, it is a template plus an implementation file that you instantiate. So the key and value types of your table are chosen when you generate the wrapper, which is what lets a C program use a table of, say, string to int without the C API having to enumerate every combination.

The examples directory also shows the range of things the table can hold, with blob_blob_table, int_str_table, nested_table, count_freq and hellohash, each pair of a header and a source file in the two table examples. A nested table in particular is the case where the structure matters, since a cuckoo table stores plain values and a table of tables is the common way to build a map whose values are themselves keyed collections.

The README points at the examples directory as the demonstration of all these features, and separately notes that the tests directory can serve as useful examples of how to use the table's various features.

Tests, stress tests and the benchmark as a workload mixer

The tests directory is where the library's claims are exercised, and its structure mirrors the CMake flags.

The README says the tests directory contains a number of tests and benchmarks of the hash table, that they can also serve as useful examples of how to use the table's various features, and that you should enable the ones you want to build with the corresponding CMake flags. The suite is run with make test, and the test executables can be run individually as well.

The three test categories map to the three questions you would ask of a concurrent container. The unit tests check the behaviour of the table itself. The stress tests, in tests/stress-tests, exist because the failure mode of concurrent cuckoo hashing is not a wrong answer, it is a hang or a lost update under contention, which a functional test will not catch. And the universal benchmark in tests/universal-benchmark is the measurement tool, letting you mix operations in arbitrary percentages with specific keys and values.

That last one is the piece to look at first if you are evaluating the library for your own workload, because a table's characteristics depend on the mix. Insert heavy, read heavy and update heavy patterns stress different parts of the algorithm, and the benchmark lets you build the mix that resembles your application rather than the one the project chose.

The repository also carries a .clang-format file, so the code is formatted to a defined style, and a libcuckoo-gdb-printers/ directory, which is debugger support for inspecting the table's internals. That second one is a small signal about the audience: people who need to look inside a hash table's buckets are debugging a concurrent structure, and they are doing it in gdb.

Editorial conclusion

Adopt libcuckoo if you have a shared hash table that many threads read and write and the locking on your conventional map is the bottleneck you have already measured. Do not adopt it for a single threaded program, where a standard container is simpler and faster to reason about, and do not adopt it without reading the papers, because the algorithm has real failure modes. Verify first that your toolchain meets the stated compiler and CMake requirements, that you can enable the unit and stress test targets in your build, and that the licence situation is clear, since the repository metadata flags the LICENSE file as unclassifiable while the README states Apache 2.0.

Frequently asked questions

Official sources

1. efficient/libcuckoo on GitHub
2. Issues
3. README