robin-map

A C++ implementation of a fast hash map and hash set using robin hood hashing

The robin-map library is a C++ implementation of a fast hash map and hash set using open-addressing and linear robin hood hashing with backward shift deletion to resolve collisions.

Four classes are provided: tsl::robin_map, tsl::robin_set, tsl::robin_pg_map and tsl::robin_pg_set. The first two are faster and use a power of two growth policy, the last two use a prime growth policy instead and are able to cope better with a poor hash function. Use the prime version if there is a chance of repeating patterns in the lower bits of your hash (e.g. you are storing pointers with an identity hash function). See GrowthPolicy for details.

A benchmark of tsl::robin_map against other hash maps may be found here. This page also gives some advices on which hash table structure you should try for your use case (useful if you are a bit lost with the multiple hash tables implementations in the tsl namespace).

Key features

• Header-only library, just add the include directory to your include path and you are ready to go. If you use CMake, you can also use the tsl::robin_map exported target from the CMakeLists.txt.
• Fast hash table, check the benchmark for some numbers.
• Support for move-only and non-default constructible key/value.
• Support for heterogeneous lookups allowing the usage of find with a type different than Key (e.g. if you have a map that uses std::unique_ptr<foo> as key, you can use a foo* or a std::uintptr_t as key parameter to find without constructing a std::unique_ptr<foo>, see example).
• No need to reserve any sentinel value from the keys.
• Possibility to store the hash value alongside the stored key-value for faster rehash and lookup if the hash or the key equal functions are expensive to compute. Note that hash may be stored even if not asked explicitly when the library can detect that it will have no impact on the size of the structure in memory due to alignment. See the StoreHash template parameter for details.
• If the hash is known before a lookup, it is possible to pass it as parameter to speed-up the lookup (see precalculated_hash parameter in API).
• Support for efficient serialization and deserialization (see example and the serialize/deserialize methods in the API for details).
• The library can be used with exceptions disabled (through -fno-exceptions option on Clang and GCC, without an /EH option on MSVC or simply by defining TSL_NO_EXCEPTIONS). std::terminate is used in replacement of the throw instruction when exceptions are disabled.
• API closely similar to std::unordered_map and std::unordered_set.

Differences compared to std::unordered_map

tsl::robin_map tries to have an interface similar to std::unordered_map, but some differences exist.

• The strong exception guarantee only holds if the following statement is true std::is_nothrow_swappable<value_type>::value && std::is_nothrow_move_constructible<value_type>::value (where value_type is Key for tsl::robin_set and std::pair<Key, T> for tsl::robin_map). Otherwise if an exception is thrown during the swap or the move, the structure may end up in a undefined state. Note that per the standard, a value_type with a noexcept copy constructor and no move constructor also satisfies this condition and will thus guarantee the strong exception guarantee for the structure (see API for details).
• The type Key, and also T in case of map, must be swappable. They must also be copy and/or move constructible.
• Iterator invalidation doesn't behave in the same way, any operation modifying the hash table invalidate them (see API for details).
• References and pointers to keys or values in the map are invalidated in the same way as iterators to these keys-values.
• For iterators of tsl::robin_map, operator*() and operator->() return a reference and a pointer to const std::pair<Key, T> instead of std::pair<const Key, T> making the value T not modifiable. To modify the value you have to call the value() method of the iterator to get a mutable reference. Example:

tsl::robin_map<int, int> map = {{1, 1}, {2, 1}, {3, 1}};
for(auto it = map.begin(); it != map.end(); ++it) {
    //it->second = 2; // Illegal
    it.value() = 2; // Ok
}

• No support for some buckets related methods (like bucket_size, bucket, ...).

These differences also apply between std::unordered_set and tsl::robin_set.

Thread-safety guarantees are the same as std::unordered_map/set (i.e. possible to have multiple readers with no writer).

Growth policy

The library supports multiple growth policies through the GrowthPolicy template parameter. Three policies are provided by the library but you can easily implement your own if needed.

• tsl::rh::power_of_two_growth_policy. Default policy used by tsl::robin_map/set. This policy keeps the size of the bucket array of the hash table to a power of two. This constraint allows the policy to avoid the usage of the slow modulo operation to map a hash to a bucket, instead of hash % 2n, it uses hash & (2n - 1) (see fast modulo). Fast but this may cause a lot of collisions with a poor hash function as the modulo with a power of two only masks the most significant bits in the end.
• tsl::rh::prime_growth_policy. Default policy used by tsl::robin_pg_map/set. The policy keeps the size of the bucket array of the hash table to a prime number. When mapping a hash to a bucket, using a prime number as modulo will result in a better distribution of the hash across the buckets even with a poor hash function. To allow the compiler to optimize the modulo operation, the policy use a lookup table with constant primes modulos (see API for details). Slower than tsl::rh::power_of_two_growth_policy but more secure.
• tsl::rh::mod_growth_policy. The policy grows the map by a customizable growth factor passed in parameter. It then just use the modulo operator to map a hash to a bucket. Slower but more flexible.

To implement your own policy, you have to implement the following interface.

…

Installation

To use robin-map, just add the include directory to your include path. It is a header-only library.

If you use CMake, you can also use the tsl::robin_map exported target from the CMakeLists.txt with target_link_libraries.

# Example where the robin-map project is stored in a third-party directory
add_subdirectory(third-party/robin-map)
target_link_libraries(your_target PRIVATE tsl::robin_map)  

If the project has been installed through make install, you can also use find_package(tsl-robin-map REQUIRED) instead of add_subdirectory.

The library is available in vcpkg and conan. It's also present in Debian, Ubuntu and Fedora package repositories.

The code should work with any C++17 standard-compliant compiler.

To run the tests you will need the Boost Test library and CMake.

git clone https://github.com/Tessil/robin-map.git
cd robin-map/tests
mkdir build
cd build
cmake ..
cmake --build .
./tsl_robin_map_tests

Usage

The API can be found here.

All methods are not documented yet, but they replicate the behavior of the ones in std::unordered_map and std::unordered_set, except if specified otherwise.

Example

…

Heterogeneous lookups

Heterogeneous overloads allow the usage of other types than Key for lookup and erase operations as long as the used types are hashable and comparable to Key.

To activate the heterogeneous overloads in tsl::robin_map/set, the qualified-id KeyEqual::is_transparent must be valid. It works the same way as for std::map::find. You can either use std::equal_to<> or define your own function object.

Both KeyEqual and Hash will need to be able to deal with the different types.

…

Serialization

The library provides an efficient way to serialize and deserialize a map or a set so that it can be saved to a file or send through the network. To do so, it requires the user to provide a function object for both serialization and deserialization.

struct serializer {
    // Must support the following types for U: std::int16_t, std::uint32_t, 
    // std::uint64_t, float and std::pair<Key, T> if a map is used or Key for 
    // a set.
    template<typename U>
    void operator()(const U& value);
};

struct deserializer {
    // Must support the following types for U: std::int16_t, std::uint32_t, 
    // std::uint64_t, float and std::pair<Key, T> if a map is used or Key for 
    // a set.
    template<typename U>
    U operator()();
};

Note that the implementation leaves binary compatibility (endianness, float binary representation, size of int, ...) of the types it serializes/deserializes in the hands of the provided function objects if compatibility is required.

More details regarding the serialize and deserialize methods can be found in the API.

…

Serialization with Boost Serialization and compression with zlib

It is possible to use a serialization library to avoid the boilerplate.

The following example uses Boost Serialization with the Boost zlib compression stream to reduce the size of the resulting serialized file. The example requires C++20 due to the usage of the template parameter list syntax in lambdas, but it can be adapted to less recent versions.

…

Performance pitfalls

Two potential performance pitfalls involving tsl::robin_map and tsl::robin_set are noteworthy:

1. Bad hashes. Hash functions that produce many collisions can lead to the following surprising behavior: when the number of collisions exceeds a certain threshold, the hash table will automatically expand to fix the problem. However, in degenerate cases, this expansion might have no effect on the collision count, causing a failure mode where a linear sequence of insertion leads to exponential storage growth.

   This case has mainly been observed when using the default power-of-two growth strategy with the default STL std::hash<T> for arithmetic types T, which is often an identity! See issue #39 for an example. The solution is simple: use a better hash function and/or tsl::robin_pg_set /