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

Overview

Build Status Build status

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.

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;
}

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++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 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

#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});
    map.erase("b");
    
    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::equal_to<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;
    }

    map.erase(1);



    // 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 << map2.at(4) << std::endl;
}  

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.

#include <cassert>
#include <cstdint>
#include <fstream>
#include <type_traits>
#include <tsl/robin_map.h>


class serializer {
public:
    serializer(const char* file_name) {
        m_ostream.exceptions(m_ostream.badbit | m_ostream.failbit);
        m_ostream.open(file_name, std::ios::binary);
    }
    
    template<class T,
             typename std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr>
    void operator()(const T& value) {
        m_ostream.write(reinterpret_cast<const char*>(&value), sizeof(T));
    }
    
    void operator()(const std::pair<std::int64_t, std::int64_t>& value) {
        (*this)(value.first);
        (*this)(value.second);
    }

private:
    std::ofstream m_ostream;
};

class deserializer {
public:
    deserializer(const char* file_name) {
        m_istream.exceptions(m_istream.badbit | m_istream.failbit | m_istream.eofbit);
        m_istream.open(file_name, std::ios::binary);
    }
    
    template<class T>
    T operator()() {
        T value;
        deserialize(value);
        
        return value;
    }
    
private:
    template<class T,
             typename std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr>
    void deserialize(T& value) {
        m_istream.read(reinterpret_cast<char*>(&value), sizeof(T));
    }
    
    void deserialize(std::pair<std::int64_t, std::int64_t>& value) {
        deserialize(value.first);
        deserialize(value.second);
    }

private:
    std::ifstream m_istream;
};


int main() {
    const tsl::robin_map<std::int64_t, std::int64_t> map = {{1, -1}, {2, -2}, {3, -3}, {4, -4}};
    
    
    const char* file_name = "robin_map.data";
    {
        serializer serial(file_name);
        map.serialize(serial);
    }
    
    {
        deserializer dserial(file_name);
        auto map_deserialized = tsl::robin_map<std::int64_t, std::int64_t>::deserialize(dserial);
        
        assert(map == map_deserialized);
    }
    
    {
        deserializer dserial(file_name);
        
        /**
         * If the serialized and deserialized map are hash compatibles (see conditions in API), 
         * setting the argument to true speed-up the deserialization process as we don't have 
         * to recalculate the hash of each key. We also know how much space each bucket needs.
         */
        const bool hash_compatible = true;
        auto map_deserialized = 
            tsl::robin_map<std::int64_t, std::int64_t>::deserialize(dserial, hash_compatible);
        
        assert(map == map_deserialized);
    }
} 
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.

#include <boost/archive/binary_iarchive.hpp>
#include <boost/archive/binary_oarchive.hpp>
#include <boost/iostreams/filter/zlib.hpp>
#include <boost/iostreams/filtering_stream.hpp>
#include <boost/serialization/split_free.hpp>
#include <boost/serialization/utility.hpp>
#include <cassert>
#include <cstdint>
#include <fstream>
#include <tsl/robin_map.h>


namespace boost { namespace serialization {
    template<class Archive, class Key, class T>
    void serialize(Archive & ar, tsl::robin_map<Key, T>& map, const unsigned int version) {
        split_free(ar, map, version); 
    }

    template<class Archive, class Key, class T>
    void save(Archive & ar, const tsl::robin_map<Key, T>& map, const unsigned int /*version*/) {
        auto serializer = [&ar](const auto& v) { ar & v; };
        map.serialize(serializer);
    }

    template<class Archive, class Key, class T>
    void load(Archive & ar, tsl::robin_map<Key, T>& map, const unsigned int /*version*/) {
        auto deserializer = [&ar]<typename U>() { U u; ar & u; return u; };
        map = tsl::robin_map<Key, T>::deserialize(deserializer);
    }
}}


int main() {
    tsl::robin_map<std::int64_t, std::int64_t> map = {{1, -1}, {2, -2}, {3, -3}, {4, -4}};
    
    
    const char* file_name = "robin_map.data";
    {
        std::ofstream ofs;
        ofs.exceptions(ofs.badbit | ofs.failbit);
        ofs.open(file_name, std::ios::binary);
        
        boost::iostreams::filtering_ostream fo;
        fo.push(boost::iostreams::zlib_compressor());
        fo.push(ofs);
        
        boost::archive::binary_oarchive oa(fo);
        
        oa << map;
    }
    
    {
        std::ifstream ifs;
        ifs.exceptions(ifs.badbit | ifs.failbit | ifs.eofbit);
        ifs.open(file_name, std::ios::binary);
        
        boost::iostreams::filtering_istream fi;
        fi.push(boost::iostreams::zlib_decompressor());
        fi.push(ifs);
        
        boost::archive::binary_iarchive ia(fi);
     
        tsl::robin_map<std::int64_t, std::int64_t> map_deserialized;   
        ia >> map_deserialized;
        
        assert(map == map_deserialized);
    }
}

License

The code is licensed under the MIT license, see the LICENSE file for details.

Comments
  • Add support for efficient serialization

    Add support for efficient serialization

    This PR adds two new methods template<class Serializer> void serialize(Serializer& serializer) const; and template<class Deserializer> static sparse_map deserialize(Deserializer& deserializer, bool hash_compatible = false); to tsl::robin_(pg)_map/set.

    They take advantage of the internals of the data structure to provide an efficient way to serialize/deserialize the structure.

    Fix feature request #28.

    opened by Tessil 9
  • Replace mod_growth_policy with multiplication-based one

    Replace mod_growth_policy with multiplication-based one

    Well-known technique to mix bits up and then extract some:

    bucket_for_hash(hash) = (hash*CONST) >> SHIFT
    

    CONST should be even odd and preferably prime number, constant through the set/map life. Value of SHIFT determined by the current buckets_count. Extra bonus is that on the hash table growth/reduce table entries arу projected into almost the same place, allowing f.e. incremental, multi-threaded implementation of the resizing operation. Taking into account that shift require 1 cpu cycle, multiplication is 3 cycles, but division is 20+ cycles, MUL-based hashing may be much faster than DIV-based one.

    opened by Bulat-Ziganshin 9
  • 1.0.0 fails to build with GCC 12 on Fedora

    1.0.0 fails to build with GCC 12 on Fedora

    Kind of a strange error to me but here it is:

    [100%] Linking CXX executable tsl_robin_map_tests
    /usr/bin/cmake -E cmake_link_script CMakeFiles/tsl_robin_map_tests.dir/link.txt --verbose=1
    /usr/bin/g++ -O2 -flto=auto -ffat-lto-objects -fexceptions -g -grecord-gcc-switches -pipe -Wall -Werror=format-security -Wp,-D_FORTIFY_SOURCE=2 -Wp,-D_GLIBCXX_ASSERTIONS -specs=/usr/lib/rpm/redhat/redhat-hardened-cc1 -fstack-protector-strong -specs=/usr/lib/rpm/redhat/redhat-annobin-cc1  -m64  -mtune=generic -fasynchronous-unwind-tables -fstack-clash-protection -fcf-protection -Wl,-z,relro -Wl,--as-needed  -Wl,-z,now -specs=/usr/lib/rpm/redhat/redhat-hardened-ld -specs=/usr/lib/rpm/redhat/redhat-annobin-cc1  -Wl,--build-id=sha1 -Wl,-dT,/builddir/build/BUILD/robin-map-1.0.0/.package_note-robin-map-1.0.0-1.fc37.x86_64.ld CMakeFiles/tsl_robin_map_tests.dir/main.cpp.o CMakeFiles/tsl_robin_map_tests.dir/custom_allocator_tests.cpp.o CMakeFiles/tsl_robin_map_tests.dir/policy_tests.cpp.o CMakeFiles/tsl_robin_map_tests.dir/robin_map_tests.cpp.o CMakeFiles/tsl_robin_map_tests.dir/robin_set_tests.cpp.o -o tsl_robin_map_tests  /usr/lib64/libboost_unit_test_framework.so
    /usr/bin/ld: /usr/lib/gcc/x86_64-redhat-linux/12/../../../../lib64/Scrt1.o: in function `_start':
    (.text+0x1b): undefined reference to `main'
    
    opened by hobbes1069 8
  • CMake exports using incorrect name

    CMake exports using incorrect name

    Trying to add robin-map into a cmake script of another package using find_package, with the outputs generated by the cmake script of this project, throws this error:

    ...
    find_package(tsl-robin-map PATHS "<my path>")
    if (tsl-robin-map_FOUND)
        target_link_libraries(my_project PRIVATE tsl::robin-map)
    endif()
    
    CMake Error at <my path>/robinmap/build/tsl-robin-mapConfig.cmake:31 (include):
      include could not find load file:
    
        <my path>/robinmap/build/tsl-robin-mapTargets.cmake
    Call Stack (most recent call first):
      CMakeLists.txt:71 (find_package)
    
    
    CMake Error at <my path>/robinmap/build/tsl-robin-mapConfig.cmake:32 (get_target_property):
      get_target_property() called with non-existent target "tsl::robin_map".
    
    opened by david-cortes 6
  • Conan Package Support

    Conan Package Support

    Hello,

    Do you know about Conan?

    Conan is modern dependency and package manager for C/C++ and would be great if your library would be available via package manager for other developers.

    All Conan packages are available on Conan Center, where is possible search, install and upload any official Conan package.

    As your project is header-only, people will not need to download manually each new release. Other header-only projects, as Catch2, are available on Conan Center.

    We could support you writing a recipe and publishing your packages on Bintray.

    If you have any questions, just ask :-)

    Regards!

    opened by uilianries 6
  • Infinite recursive loop in robin_set::insert

    Infinite recursive loop in robin_set::insert

    When compiling with Visual C++ 2017 15.7.3 I get this warning. Note that the "C++ Language Setting" of "Conformance Mode" must be "No". If Conformance mode is /permissive- then the code compiles and runs without error. Clearly this is an issue with standards conformance and the Visual C++ compiler switches. But is an easy trap to fall into unless you are using the latest Visual C++ compilers with correct settings.

    Warning C4717 'tsl::detail_robin_hash::robin_hash<CBroadcaster *,tsl::robin_set<CBroadcaster *,std::hash<CBroadcaster *>,std::equal_to<CBroadcaster *>,std::allocator<CBroadcaster *>,0,tsl::rh::power_of_two_growth_policy<2> >::KeySelect,void,std::hash<CBroadcaster *>,std::equal_to<CBroadcaster *>,std::allocator<CBroadcaster *>,0,tsl::rh::power_of_two_growth_policy<2> >::insert_value<CBroadcaster * &>': recursive on all control paths, function will cause runtime stack overflow foundation tsl\robin_hash.h 1152

    And so it happens. I get a stack overflow run-time error due to a recursive loop when inserting values.

    struct CBroadcaster { int dummy; };

    int main() { tsl::robin_set<CBroadcaster *> aSet; for (int i = 0; i < 100; i++) { CBroadcaster *tmp = new CBroadcaster(); aSet.insert(tmp); } }

    opened by loopless 5
  • clear() does not trigger rehash

    clear() does not trigger rehash

    I re-use an existing robin_set after calling clear(). When I profiled this code, I noticed that a lot of time was spent in the iterator. Consider the following example:

    tsl::robin_set<size_t> my_set;
    my_set.min_load_factor(0.1f);
    
    for (size_t i = 0; i < 50000000; ++i) {
    	my_set.insert(i);
    }
    
    std::cout << "Inserted items" << std::endl;
    
    my_set.clear();
    
    for (size_t i = 0; i < 10; ++i) {
    	my_set.insert(9999999);
    	for (size_t j : my_set) {
    		std::cout << "Iterating over " << j << std::endl;
    	}
    	my_set.clear();
    }
    

    I would have expected that the second loop is very fast. However, it needs time proportional to the number of items I have inserted previously. What seems to happen is that only an erase() triggers rehashing on the next insertion, while calling clear() does not trigger any rehashing. Is there any reason for this?

    opened by michitux 4
  • Ceral with robin-map

    Ceral with robin-map

    Hi,

    I'd like to use tsl::robin_map everywhere instead of the std maps, however I can't figure out how to serialize them with Cereal. I saw your post about sparse_map but don't see the same serialize functions in robin - am I missing something?

    Thanks for your help!

    opened by PcChip 4
  • Error with gcc 9.0.1: implicitly-declared...

    Error with gcc 9.0.1: implicitly-declared...

    There's lots of these so I'm only pasting on here

     /builddir/build/BUILD/robin-map-0.6.0/tests/robin_map_tests.cpp:269:53: error: implicitly-declared 'tsl::detail_robin_hash::robin_hash<std::pair<std::__cxx11::basic_string<char>, move_only_test>, tsl::robin_map<std::__cxx11::basic_string<char>, move_only_test>::KeySelect, tsl::robin_map<std::__cxx11::basic_string<char>, move_only_test>::ValueSelect, std::hash<std::__cxx11::basic_string<char> >, std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<std::__cxx11::basic_string<char>, move_only_test> >, false, tsl::rh::power_of_two_growth_policy<2> >::robin_iterator<false>& tsl::detail_robin_hash::robin_hash<std::pair<std::__cxx11::basic_string<char>, move_only_test>, tsl::robin_map<std::__cxx11::basic_string<char>, move_only_test>::KeySelect, tsl::robin_map<std::__cxx11::basic_string<char>, move_only_test>::ValueSelect, std::hash<std::__cxx11::basic_string<char> >, std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<std::__cxx11::basic_string<char>, move_only_test> >, false, tsl::rh::power_of_two_growth_policy<2> >::robin_iterator<false>::operator=(const tsl::detail_robin_hash::robin_hash<std::pair<std::__cxx11::basic_string<char>, move_only_test>, tsl::robin_map<std::__cxx11::basic_string<char>, move_only_test>::KeySelect, tsl::robin_map<std::__cxx11::basic_string<char>, move_only_test>::ValueSelect, std::hash<std::__cxx11::basic_string<char> >, std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<std::__cxx11::basic_string<char>, move_only_test> >, false, tsl::rh::power_of_two_growth_policy<2> >::robin_iterator<false>&)' is deprecated [-Werror=deprecated-copy]
    

    The is on Fedora Rawhide x86_64 with gcc 9.0.1.

    opened by hobbes1069 4
  • Compiling with

    Compiling with "-Wshadow" flag causes error

    Hi,

    Compiling this with -Wshadow flag causes it to error out. If I set the -Wno-shadow flag, compilation passes successfully.

    Currently I'm trying it to include it in a project of mine, but I'm not allowed to change any compilation flags. Would be really helpful if this problem could be solved.

    Thanks Stainlee

    opened by stainleebakhla 3
  • Why did the download of release 0.6.3 change?

    Why did the download of release 0.6.3 change?

    Conan is a C/C++ package manager

    In the Conan Center Index we have a recipe for robin-map: https://conan.io/center/tsl-robin-map/0.6.3/

    The downloads of the source code are secured by sha256 checksums and are verified after every download

    On June 20 version 0.6.3 was added with the sha256sum 7db3530dd6482c4a0d8f8bb52601dbdfdf3da10ac7ea9e100d4b8041a02f034e

    https://github.com/conan-io/conan-center-index/commit/ea4942a6899a544c7cd120653eb4c03a605bae12 https://github.com/conan-io/conan-center-index/pull/1950#issuecomment-647021442

    Somewhen after June 20, the checksum changed to e6654c8c2598f63eb0b1d52ff8bdf39cfcc91d81dd5d05274a6dca91241cd72f

    https://github.com/conan-io/conan-center-index/pull/2568

    Why is this?

    opened by Croydon 3
  • aligned_storage is deprecated by C++23

    aligned_storage is deprecated by C++23

    template <typename ValueType, bool StoreHash> class bucket_entry : public bucket_entry_hash { using bucket_hash = bucket_entry_hash;

    public: using value_type = ValueType; using distance_type = std::int16_t;

    ..................................................................................

    private: using storage = typename std::aligned_storage<sizeof(value_type), alignof(value_type)>::type;

    distance_type m_dist_from_ideal_bucket; bool m_last_bucket; storage m_value; };

    visual studio 2022 v17.3.0 preview reported this as error.

    Severity Code Description Project File Line Suppression State Error C4996 'std::aligned_storage<8,4>': warning STL4034: std::aligned_storage and std::aligned_storage_t are deprecated in C++23. Prefer alignas(T) std::byte t_buff[sizeof(T)]. You can define _SILENCE_CXX23_ALIGNED_STORAGE_DEPRECATION_WARNING or _SILENCE_ALL_CXX23_DEPRECATION_WARNINGS to acknowledge that you have received this warning. MDTest D:\STHFT\3rd\include\tsl\robin_hash.h 334

    opened by qdztxc 2
  • Hash Map Insert Stuck in an infinite loop

    Hash Map Insert Stuck in an infinite loop

    Hi, there,

    We used the robin-map/v0.6.1, and we observed the robin map stuck in an infinite loop here in insert_value_impl method.

    We created tsl::robin_map<uint64_t, DataBlock*>, and we inserted monotonically increasing keys like: 0xc000000000001, 0xc000000000002, etc. We do not have concurrent modifications on the robin map.

    We observed this issue both on Intel and ARM machines, but ARM machines showed up more often. However, we do not have a good reproducer, and we only observed this issue in our production fleet.

    Could any one help us debug a bit to see if anything pops out? Any suggestions would be appreciated!

    Thanks very much!


    Here are some debug information we gathered.

    The robin map has 8 buckets, but the number of elements are only 5 (although all 8 keys look valid to us). However, we observed a really large m_load_threshold = 18446744069414584320, and all 8 buckets show with m_dist_from_ideal_bucket = 32767.

    We suspected somehow m_load_threshold overflowed, causing the robin map would not expand the size, and hence there are no empty buckets in the map anymore.

    (gdb) p *this 
    $35 = {<std::hash<unsigned long>> = {<std::__hash_base<unsigned long, unsigned long>> = {<No data fields>}, <No data fields>}, <std::equal_to<unsigned long>> = {<std::binary_function<unsigned long, unsigned long, bool>> = {<No data fields>}, <No data fields>}, <tsl::rh::power_of_two_growth_policy<2>> = {m_mask = 7}, 
      static STORE_HASH = false, static USE_STORED_HASH_ON_LOOKUP = false, static DEFAULT_INIT_BUCKETS_SIZE = 0, static DEFAULT_MAX_LOAD_FACTOR = 0.5, 
      static MINIMUM_MAX_LOAD_FACTOR = 0.200000003, static MAXIMUM_MAX_LOAD_FACTOR = 0.949999988, static DEFAULT_MIN_LOAD_FACTOR = 0, static MINIMUM_MIN_LOAD_FACTOR = 0, 
      static MAXIMUM_MIN_LOAD_FACTOR = 0.150000006, static REHASH_ON_HIGH_NB_PROBES__NPROBES = 128, static REHASH_ON_HIGH_NB_PROBES__MIN_LOAD_FACTOR = 0.150000006, 
      m_buckets_data = {<std::_Vector_base<tsl::detail_robin_hash::bucket_entry<std::pair<unsigned long, MapGraph::Blocks::DataBlock*>, false>, std::allocator<tsl::detail_robin_hash::bucket_entry<std::pair<unsigned long, MapGraph::Blocks::DataBlock*>, false> > >> = {
          _M_impl = {<std::allocator<tsl::detail_robin_hash::bucket_entry<std::pair<unsigned long, MapGraph::Blocks::DataBlock*>, false> >> = {<__gnu_cxx::new_allocator<tsl::detail_robin_hash::bucket_entry<std::pair<unsigned long, MapGraph::Blocks::DataBlock*>, false> >> = {<No data fields>}, <No data fields>}, _M_start = 0x40006630f040, 
            _M_finish = 0x40006630f100, _M_end_of_storage = 0x40006630f100}}, <No data fields>}, m_buckets = 0x40006630f040, m_bucket_count = 8, m_nb_elements = 5, 
      m_load_threshold = 18446744069414584320, m_max_load_factor = 0.5, m_grow_on_next_insert = true, m_min_load_factor = 0, m_try_skrink_on_next_insert = false}
    
    (gdb) p m_buckets[0]
    $36 = {<tsl::detail_robin_hash::bucket_entry_hash<false>> = {<No data fields>}, static EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET = -1, m_dist_from_ideal_bucket = 32767, 
      m_last_bucket = false, m_value = {__data = "\t\000\000\000\000\000\f\000\000\000\000\000\000\000\000", __align = {<No data fields>}}}
    (gdb) p m_buckets[1]
    $37 = {<tsl::detail_robin_hash::bucket_entry_hash<false>> = {<No data fields>}, static EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET = -1, m_dist_from_ideal_bucket = 32767, 
      m_last_bucket = false, m_value = {__data = "\002\000\000\000\000\000\f\000\340R\304#\[email protected]\000", __align = {<No data fields>}}}
    (gdb) p m_buckets[2]
    $38 = {<tsl::detail_robin_hash::bucket_entry_hash<false>> = {<No data fields>}, static EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET = -1, m_dist_from_ideal_bucket = 32767, 
      m_last_bucket = false, m_value = {__data = "\003\000\000\000\000\000\f\000\320P\304#\[email protected]\000", __align = {<No data fields>}}}
    (gdb) p m_buckets[3]
    $39 = {<tsl::detail_robin_hash::bucket_entry_hash<false>> = {<No data fields>}, static EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET = -1, m_dist_from_ideal_bucket = 32767, 
      m_last_bucket = false, m_value = {__data = "\004\000\000\000\000\000\f\000А?\034\[email protected]\000", __align = {<No data fields>}}}
    (gdb) p m_buckets[4]
    $40 = {<tsl::detail_robin_hash::bucket_entry_hash<false>> = {<No data fields>}, static EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET = -1, m_dist_from_ideal_bucket = 32767, 
      m_last_bucket = false, m_value = {__data = "\005\000\000\000\000\000\f\000\000\221?\034\[email protected]\000", __align = {<No data fields>}}}
    (gdb) p m_buckets[5]
    $41 = {<tsl::detail_robin_hash::bucket_entry_hash<false>> = {<No data fields>}, static EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET = -1, m_dist_from_ideal_bucket = 32767, 
      m_last_bucket = false, m_value = {__data = "\006\000\000\000\000\000\f\000\300$Fe\[email protected]\000", __align = {<No data fields>}}}
    (gdb) p m_buckets[6]
    $42 = {<tsl::detail_robin_hash::bucket_entry_hash<false>> = {<No data fields>}, static EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET = -1, m_dist_from_ideal_bucket = 32767, 
      m_last_bucket = false, m_value = {__data = "\a\000\000\000\000\000\f\000\240&Fe\[email protected]\000", __align = {<No data fields>}}}
    (gdb) p m_buckets[7]
    $43 = {<tsl::detail_robin_hash::bucket_entry_hash<false>> = {<No data fields>}, static EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET = -1, m_dist_from_ideal_bucket = 32767, 
      m_last_bucket = true, m_value = {__data = "\b\000\000\000\000\000\f\000\340\033Re\[email protected]\000", __align = {<No data fields>}}}
    

    Here are the list of keys in the map:

    (gdb) p/x *reinterpret_cast<uint64_t*>(m_buckets[0].m_value.__data)
    $14 = 0xc000000000009
    (gdb) p/x *reinterpret_cast<uint64_t*>(m_buckets[1].m_value.__data)
    $15 = 0xc000000000002
    (gdb) p/x *reinterpret_cast<uint64_t*>(m_buckets[2].m_value.__data)
    $16 = 0xc000000000003
    (gdb) p/x *reinterpret_cast<uint64_t*>(m_buckets[3].m_value.__data)
    $17 = 0xc000000000004
    (gdb) p/x *reinterpret_cast<uint64_t*>(m_buckets[4].m_value.__data)
    $18 = 0xc000000000005
    (gdb) p/x *reinterpret_cast<uint64_t*>(m_buckets[5].m_value.__data)
    $19 = 0xc000000000006
    (gdb) p/x *reinterpret_cast<uint64_t*>(m_buckets[6].m_value.__data)
    $20 = 0xc000000000007
    (gdb) p/x *reinterpret_cast<uint64_t*>(m_buckets[7].m_value.__data)
    $21 = 0xc000000000008
    
    cannot reproduce 
    opened by szhang0119 30
  • add support for heterogeneous insert

    add support for heterogeneous insert

    This pull request adds support for heterogeneous. This is useful for the same reasons as heterogeneous lookup. You can for example insert words from a string into a set of strings, without unnecessary memory allocations (see example).

    In addition to the requirements for heterogeneous lookup the "key" type has to be constructible from the "key_equal" type. I strongly recommend using an explicit constructor otherwise you always live in danger of silent copys.

    The changes required for this to work are very minor, because most of the code is already generic.

    Right now it's only implemented for robin_set and not tested throughoutly, because i want to know what you think about it before i waste my time.

    example.cpp.txt

    opened by the5avage 2
  • Updated Benchmark?

    Updated Benchmark?

    Hi, Your benchmark is great and very extensive. Could you run it again now so to see how all libs have improved over the past 4 or so years? Also some have stopped development and maybe some hot new ones appeared? Would be so awesome!

    opened by patlecat 2
  • Maybe it would make sense for the self-insertion/emplacement to work (suggestion)

    Maybe it would make sense for the self-insertion/emplacement to work (suggestion)

    Currently the following code leads to crash/undefined behavior with tsl::robin_map:

    int main ()
    {
      tsl::robin_map<int, std::string> v;
      v[0] = "23";
      for (int i = 2; i < 3300; ++i)
        v[i] = v[0];
    }
    

    It happens because we pass the reference to our own element which gets destroyed during reallocation and since construction happens late it leads to the unfortunate results. I understand that this might be a design decision to treat it as UB however I have the following reason for suggesting to fix this:

    1. It works fine with node-based (std::) maps.

    2. It works with std::vector. I can't quote standard paragraph exactly but here's link to the statement from Microsoft of fixing this problem in their implementation https://devblogs.microsoft.com/cppblog/stl-fixes-in-vs-2017-rtm/ (Fixed aliasing bugs)

    3. It actually seems to be much more frequent operation for unordered map rather than for vector, simply copying a past value to the newly created field feels like natural operation in many cases.

    4. A fix seems to be the same as for vector since it is the structure robin map built upon so should not be that hard to implement.

    opened by Predelnik 5
Releases(v1.0.1)
  • v1.0.1(Apr 5, 2022)

    Minor release to fix tests compilation on some platforms, no change in the library code itself.

    • For the tests, force the usage of the Boost static libraries by setting Boost_USE_STATIC_LIBS to ON in CMake. Fix #50
    Source code(tar.gz)
    Source code(zip)
  • v1.0.0(Mar 25, 2022)

    • Add support for efficient serialization (https://github.com/Tessil/robin-map/pull/36)
    • Remove compilation warnings when -Wshadow flag is set (https://github.com/Tessil/robin-map/pull/41)
    • Fix USE_STORED_HASH_ON_REHASH to return true when bucket_count is 0, STORE_HASH is true and is_power_of_two_policy::value is true. This commit doesn't change the actual behaviour of the map as even when USE_STORED_HASH_ON_REHASH was returning false on empty map rehashes, no stored hashes were used as the map was empty.
    • Fix CMake warning by specifying a project language before including GNUInstallDirs
    • Create a local tsl-robin-mapTargets.cmake (https://github.com/Tessil/robin-map/issues/45)
    Source code(tar.gz)
    Source code(zip)
  • v0.6.3(Jun 22, 2020)

    • Fix issue #26, raise the maximum possible size of the hash table when using the prime_growth_policy on a 64-bit platform.
    • Fix issue #31, when min_load_factor() > 0, the clear() method will also reset the bucket_count of the hash table to 0.
    • Fix shrink when min_load_factor is set and a range erase with end() as last is called. The m_try_skrink_on_next_insert was not correctly set.
    • Fix issue #33, the value function of a const iterator can now be called and returns a mutable reference to the underlying value_type.
    Source code(tar.gz)
    Source code(zip)
  • v0.6.2(Sep 25, 2019)

    • Fix compilation error for move-only types with a throwing move constructor/operator (#14).
    • Add support for min_load_factor (#17).
    • Fix compilation error when exceptions are disabled and C++ 14 or higher is used (#18).
    • Fix issue #23. The distance_type used to store the distance of a value in a bucket from its ideal bucket could overflow when a lot of collisions happened and the load_factor() stayed below REHASH_ON_HIGH_NB_PROBES__MIN_LOAD_FACTOR. We now rehash no matter the load factor if the distance becomes too high.
    • Add bool contains(...) methods.
    Source code(tar.gz)
    Source code(zip)
  • v0.6.1(Feb 17, 2019)

    • Fix compilation error with GCC 9, the implicit copy/move constructor/operator of the iterator were not generated (#12).
    • Rename the internal insert with hint method to insert_hint to avoid a potential ambiguous overload with the insert with a pair of iterators.
    Source code(tar.gz)
    Source code(zip)
  • v0.6.0(Jan 27, 2019)

    • Rename CMake project name from tsl_robin_map to tsl-robin-map for coherence with the convention used by most package managers. The find_package(tsl-robin-map) command must now be used instead of the find_package(tsl_robin_map).
    • Set bucket count for default constructed map/set to 0 to avoid any allocation.
    • On Windows, add tsl-robin-map.natvis to the installed files.
    • Fix CMake >= 3.13 warning on Policy CMP0076 and add quotes to paths.
    • Remove cxx_std_11 from target_compile_features to avoid a warning with older versions of CMake that don't support it. The warning was given even if the target_compile_features was surrounded in a if(${CMAKE_VERSION} VERSION_GREATER "3.7").
    • Change error message when max_bucket_count is reached. It's the maximum bucket count that has been reached and not the size.
    Source code(tar.gz)
    Source code(zip)
  • v0.5.0(Nov 3, 2018)

  • v0.4.0(Sep 17, 2018)

    This release introduce a minor backward incompatibility by moving the headers files.

    • Move the header files from tsl to include/tsl for more coherence with other C++ libraries.
    • For CMake users, add an exported target tsl::robin_map to be used with target_link_libraries.
    • Fix issue #6 by circumverting a bug in MSVC on insert when using a pointer as type in a set. The bug resulted in an infinite recursion inside the insert function. (#7)
    Source code(tar.gz)
    Source code(zip)
  • v0.3.0(Jun 21, 2018)

    • Bug correction (#3), a moved tsl::robin_map or tsl::robin_set can now still be used after a move. Previously the map ended up in a invalid state after a move but the standard mandates that a moved object should be in a valid (but unspecified) state so that it can still be used after a move.
    • When a hash map or set with a bucket count of 0 is instantiated, no heap memory will be allocated.
    • Add the possibility to use the library without exceptions (#2).
    • Improve lookups performances with a branch prediction hint (#2).
    Source code(tar.gz)
    Source code(zip)
  • v0.2.0(Dec 11, 2017)

    • Fix range erase method, take care of the invalidation of the iterators on erase.
    • In max_load_factor(float ml) check that the ml parameter is in [0.1, 0.95].
    Source code(tar.gz)
    Source code(zip)
  • v0.1(Aug 21, 2017)

Owner
Thibaut Goetghebuer-Planchon
Thibaut Goetghebuer-Planchon
Fast & memory efficient hashtable based on robin hood hashing for C++11/14/17/20

➵ robin_hood unordered map & set robin_hood::unordered_map and robin_hood::unordered_set is a platform independent replacement for std::unordered_map

Martin Leitner-Ankerl 1.2k Sep 30, 2022
C++ hash map and hash set which preserve the order of insertion

C++ hash map and hash set which preserves the order of insertion The ordered-map library provides a hash map and a hash set which preserve the order o

Thibaut Goetghebuer-Planchon 368 Sep 23, 2022
A fast hash map/hash table (whatever you want to call it) for the C programming language.

C HashMap A fast hash map/hash table (whatever you want to call it) for the C programming language. It can associate a key with a pointer or integer v

Mashpoe 68 Sep 15, 2022
Bit-Map is a simple bit map.

Bit-Map Bit-Map is a simple bit map. Usage Create a map uint8** bitmap; uint64 map_size = 32; // bit number pfs_create_bitmap(bitmap,

Pink 2 Feb 18, 2022
A benchmark for hash tables and hash functions in C++, evaluate on different data as comprehensively as possible

Hash Table Benchmark This is yet another benchmark for hash tables(hash maps) with different hash functions in C++, attempting to evaluate the perform

Ren Zibei 2 Mar 14, 2022
A repository I'm using to learn hashing with GLib.

GLib Tests Description A repository I'm using to store my progress while learning GNOME's GLib library. Specifically hashing via ghash. Test Files GLi

Christian Deacon 7 Oct 1, 2022
Explore building a hash table with two different hash functions that balances chain length

hash-duo Explore building a hash table with two different hash functions that balances chain length. There is a really cool article called Don't Throw

Terence Parr 3 May 7, 2022
Very Fast Non-Cryptographic Hash Function

KOMIHASH - Very Fast Hash Function Introduction The komihash() function available in the komihash.h file implements a very fast 64-bit hash function,

Aleksey Vaneev 75 Sep 28, 2022
A simple single header 64 and 32 bit hash function using only add, sub, ror, and xor.

K-HASH A simple single header 64 bit hash function using only add, sub, ror, and xor. This a just general-purpose hash function for like making hash m

null 69 Jul 31, 2022
Typesafe, Generic & Fastest Set Data structure implementation in C

Typesafe & Fast as fuck Set in C Key Features Extremely fast non-cryptographic hash algorithm XXHash Complete Typesafe APIs Double Hashing to avoid bo

Robus Gauli 4 Sep 6, 2021
Unofficial .hmap map viewer for HumandKind

bhkmap Main Features Read/Write .hmap files Display elevation level, territories, biomes, tile types, strategic resources, luxury resources, natural w

null 5 Apr 9, 2022
Header-only compile time key-value map written in C++20.

C++ Static Map Header-only compile time key-value map written in C++20. Getting Started Simply add the files in your source and #include "@dir/Static_

null 1 Oct 19, 2021
Diablo II Resurrected map revealing tool.

D2RMH Diablo II Resurrected map revealing tool. What's New v0.2 add display for Unique Chest, Well, neighbour map path fix display of correct taltomb

Soar Qin 150 Sep 21, 2022
Simple hash table implemented in C

Simple hash table written in C. To go with my article How to implement a hash table (in C). This is a learning exercise, not a battle-tested data stru

Ben Hoyt 80 Sep 18, 2022
simple hash table linear probing method can expand/reduce

hash table a simple c hash table implementation based on https://benhoyt.com/writings/hash-table-in-c/ project can store different data types (data al

Fabio Murer 1 Oct 3, 2021
HashTableBenchmark - A simple cross-platform speed & memory-efficiency benchmark for the most common hash-table implementations in the C++ world

Hash-Tables Benchmarks This repository contains a bunch of extendable benchmarks mostly for following containers: std:unordered_map from STL. google::

Unum 8 Jul 11, 2022
A collection of hash tables for parallel programming, including lock-free, wait-free tables.

Hatrack Hash tables for parallel programming This project consisists of fast hash tables suitable for parallel programming, including multiple lock-fr

null 58 Sep 23, 2022
This is a beginner-friendly project aiming to build a problem-set on different data structures and algorithms in different programming languages.

DSAready Overview This is a beginner-friendly project that aims to create a problem-set for various Data Structures and Algorithms. Being a programmer

Riddhi Jain 13 Aug 17, 2022
A fast Python Common substrings of multiple strings library with C++ implementation

A fast Python Common substrings of multiple strings library with C++ implementation Having a bunch of strings, can I print some substrings which appea

Đào Nguyên Dương 7 Aug 21, 2022