robin-map Documentation

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

Differences compare to std::unordered_map

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

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.

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

struct custom_policy {
// Called on hash table construction and rehash, min_bucket_count_in_out is the minimum buckets
// that the hash table needs. The policy can change it to a higher number of buckets if needed
// and the hash table will use this value as bucket count. If 0 bucket is asked, then the value
// must stay at 0.
explicit custom_policy(std::size_t& min_bucket_count_in_out);
// Return the bucket [0, bucket_count()) to which the hash belongs.
// If bucket_count() is 0, it must always return 0.
std::size_t bucket_for_hash(std::size_t hash) const noexcept;
// Return the number of buckets that should be used on next growth
std::size_t next_bucket_count() const;
// Maximum number of buckets supported by the policy
std::size_t max_bucket_count() const;
// Reset the growth policy as if the policy was created with a bucket count of 0.
// After a clear, the policy must always return 0 when bucket_for_hash() is called.
void clear() noexcept;


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
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++11 standard-compliant compiler and has been tested with GCC 4.8.4, Clang 3.5.0 and Visual Studio 2015.

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

git clone
cd robin-map/tests
mkdir build
cd build
cmake ..
cmake --build .


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.


#include <cstdint>
#include <iostream>
#include <string>
#include <tsl/robin_map.h>
#include <tsl/robin_set.h>
int main() {
tsl::robin_map<std::string, int> map = {{"a", 1}, {"b", 2}};
map["c"] = 3;
map["d"] = 4;
map.insert({"e", 5});
for(auto it = map.begin(); it != map.end(); ++it) {
//it->second += 2; // Not valid.
it.value() += 2;
// {d, 6} {a, 3} {e, 7} {c, 5}
for(const auto& key_value : map) {
std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
if(map.find("a") != map.end()) {
std::cout << "Found \"a\"." << std::endl;
const std::size_t precalculated_hash = std::hash<std::string>()("a");
// If we already know the hash beforehand, we can pass it in parameter to speed-up lookups.
if(map.find("a", precalculated_hash) != map.end()) {
std::cout << "Found \"a\" with hash " << precalculated_hash << "." << std::endl;
* Calculating the hash and comparing two std::string may be slow.
* We can store the hash of each std::string in the hash map to make
* the inserts and lookups faster by setting StoreHash to true.
tsl::robin_map<std::string, int, std::hash<std::string>,
std::allocator<std::pair<std::string, int>>,
true> map2;
map2["a"] = 1;
map2["b"] = 2;
// {a, 1} {b, 2}
for(const auto& key_value : map2) {
std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
tsl::robin_set<int> set;
set.insert({1, 9, 0});
set.insert({2, -1, 9});
// {0} {1} {2} {9} {-1}
for(const auto& key : set) {
std::cout << "{" << key << "}" << std::endl;

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.

#include <functional>
#include <iostream>
#include <string>
#include <tsl/robin_map.h>
struct employee {
employee(int id, std::string name) : m_id(id), m_name(std::move(name)) {
// Either we include the comparators in the class and we use `std::equal_to<>`...
friend bool operator==(const employee& empl, int empl_id) {
return empl.m_id == empl_id;
friend bool operator==(int empl_id, const employee& empl) {
return empl_id == empl.m_id;
friend bool operator==(const employee& empl1, const employee& empl2) {
return empl1.m_id == empl2.m_id;
int m_id;
std::string m_name;
// ... or we implement a separate class to compare employees.
struct equal_employee {
using is_transparent = void;
bool operator()(const employee& empl, int empl_id) const {
return empl.m_id == empl_id;
bool operator()(int empl_id, const employee& empl) const {
return empl_id == empl.m_id;
bool operator()(const employee& empl1, const employee& empl2) const {
return empl1.m_id == empl2.m_id;
struct hash_employee {
std::size_t operator()(const employee& empl) const {
return std::hash<int>()(empl.m_id);
std::size_t operator()(int id) const {
return std::hash<int>()(id);
int main() {
// Use std::equal_to<> which will automatically deduce and forward the parameters
tsl::robin_map<employee, int, hash_employee, std::equal_to<>> map;
map.insert({employee(1, "John Doe"), 2001});
map.insert({employee(2, "Jane Doe"), 2002});
map.insert({employee(3, "John Smith"), 2003});
// John Smith 2003
auto it = map.find(3);
if(it != map.end()) {
std::cout << it->first.m_name << " " << it->second << std::endl;
// Use a custom KeyEqual which has an is_transparent member type
tsl::robin_map<employee, int, hash_employee, equal_employee> map2;
map2.insert({employee(4, "Johnny Doe"), 2004});
// 2004
std::cout << << std::endl;


The code is licensed under the MIT license, see the [LICENSE file](LICENSE) for details.