High-performance Concurrent Cuckoo Hashing Library
This library provides a compact hash table that allows multiple concurrent reader and writer threads.
Authors: Bin Fan, David G. Andersen, Manu Goyal, and Michael Kaminsky
For details about this algorithm and citations, please refer to our paper in NSDI 2013.
This library has been tested on Mac OSX >= 10.8 and Ubuntu >= 12.04.
It compiles with clang++ >= 3.1 and g++ >= 4.6, however we highly recommend the latest versions of both compilers, as they have greatly improved support for atomic operations. Building the library requires the autotools.
$ autoreconf -fis
$ ./configure
$ make
To build a program with the hash table, include cuckoohash_map.hh
and optionally cuckoohash_config.h into your source file. Then
compile with the flags -I[libcuckoo_dir]/lib -pthread and link
with the flags -lpthread -L[libcuckoo_dir]/lib -lcityhash. You
must also enable C++11 features on your compiler. If compiling a file
test.cpp with g++, it might look like this:
$ g++ -Ilibcuckoo/lib -pthread -std=c++11 -Llibcuckoo/lib -lcityhash test.cpp
With clang++ it might look like this:
$ clang++ -Ilibcuckoo/lib -pthread -std=c++11 -stdlib=libc++ -Llibcuckoo/lib -lcityhash test.cpp
The testing directory contains a number of tests and benchmarks of the
hash table, which also serve as useful examples of how to use the
table's various features. The entire test suite can be run with the
runtest.py script, and individual tests, which have the suffix
".out" can be run individually as well.
The Doxygen-generated documentation is available at the project page.
To let us know your questions or issues, we recommend you report an issue on github. You can also email us at [email protected].