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

Overview

Build Status Build status

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

The hopscotch-map library is a C++ implementation of a fast hash map and hash set using open-addressing and hopscotch hashing to resolve collisions. It is a cache-friendly data structure offering better performances than std::unordered_map in most cases and is closely similar to google::dense_hash_map while using less memory and providing more functionalities.

The library provides the following main classes: tsl::hopscotch_map, tsl::hopscotch_set, tsl::hopscotch_pg_map and tsl::hopscotch_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.

In addition to these classes the library also provides tsl::bhopscotch_map, tsl::bhopscotch_set, tsl::bhopscotch_pg_map and tsl::bhopscotch_pg_set. These classes have an additional requirement for the key, it must be LessThanComparable, but they provide a better asymptotic upper bound, see details in example. Nonetheless if you don't have specific requirements (risk of hash DoS attacks), tsl::hopscotch_map and tsl::hopscotch_set should be sufficient in most cases and should be your default pick as they perform better in general.

An overview of hopscotch hashing and some implementation details can be found here.

A benchmark of tsl::hopscotch_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::hopscotch_map exported target from the CMakeLists.txt.
  • Fast hash table, see 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 on insert for faster rehash and lookup if the hash or the key equal functions are expensive to compute (see the StoreHash template parameter).
  • 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).
  • The tsl::bhopscotch_map and tsl::bhopscotch_set provide a worst-case of O(log n) on lookups and deletions making these classes resistant to hash table Deny of Service (DoS) attacks (see details in example).
  • 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::hopscotch_map tries to have an interface similar to std::unordered_map, but some differences exist.

  • Iterator invalidation on insert doesn't behave in the same way. In general any operation modifying the hash table, except erase, invalidate all the iterators (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 on insert.
  • For iterators, 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::hopscotch_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
}
  • Move-only types must have a nothrow move constructor (with open addressing, it is not possible to keep the strong exception guarantee on rehash if the move constructor may throw).
  • No support for some buckets related methods (like bucket_size, bucket, ...).

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

Thread-safety and exceptions 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::hh::power_of_two_growth_policy. Default policy used by tsl::(b)hopscotch_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::hh::prime_growth_policy. Default policy used by tsl::(b)hopscotch_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 hashes 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::hh::power_of_two_growth_policy but more secure.
  • tsl::hh::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.

If you encounter poor performances check the overflow_size(), if it is not zero you may have a lot of hash collisions. Either change the hash function for something more uniform or try another growth policy (mainly tsl::hh::prime_growth_policy). Unfortunately it is sometimes difficult to guard yourself against collisions (e.g. DoS attack on the hash map). If needed, check also tsl::bhopscotch_map/set which offer a worst-case scenario of O(log n) on lookups instead of O(n), see details in example.

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 hopscotch-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::hopscotch_map exported target from the CMakeLists.txt with target_link_libraries.

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

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

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/hopscotch-map.git
cd hopscotch-map/tests
mkdir build
cd build
cmake ..
cmake --build .
./tsl_hopscotch_map_tests 

Usage

The API can be found here.

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

Example

#include <cstdint>
#include <iostream>
#include <string>
#include <tsl/hopscotch_map.h>
#include <tsl/hopscotch_set.h>

int main() {
    tsl::hopscotch_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::hopscotch_map<std::string, int, std::hash<std::string>, 
                       std::equal_to<std::string>,
                       std::allocator<std::pair<std::string, int>>,
                       30, 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::hopscotch_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::hopscotch_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/hopscotch_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::hopscotch_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::hopscotch_map<employee, int, hash_employee, equal_employee> map2;
    map2.insert({employee(4, "Johnny Doe"), 2004});

    // 2004
    std::cout << map2.at(4) << std::endl;
} 

Deny of Service (DoS) attack

In addition to tsl::hopscotch_map and tsl::hopscotch_set, the library provides two more "secure" options: tsl::bhopscotch_map and tsl::bhopscotch_set (all with their pg counterparts).

These two additions have a worst-case asymptotic complexity of O(log n) for lookups and deletions and an amortized worst case of O(log n) for insertions (amortized due to the possibility of rehash which would be in O(n)). Even if the hash function maps all the elements to the same bucket, the O(log n) would still hold.

This provides a security against hash table Deny of Service (DoS) attacks.

To achieve this, the secure versions use a binary search tree for the overflown elements (see implementation details) and thus need the elements to be LessThanComparable. An additional Compare template parameter is needed.

#include <chrono>
#include <cstdint>
#include <iostream>
#include <tsl/hopscotch_map.h>
#include <tsl/bhopscotch_map.h>

/*
 * Poor hash function which always returns 1 to simulate
 * a Deny of Service attack.
 */
struct dos_attack_simulation_hash {
    std::size_t operator()(int id) const {
        return 1;
    }
};

int main() {
    /*
     * Slow due to the hash function, insertions are done in O(n).
     */
    tsl::hopscotch_map<int, int, dos_attack_simulation_hash> map;
    
    auto start = std::chrono::high_resolution_clock::now();
    for(int i=0; i < 10000; i++) {
        map.insert({i, 0});
    }
    auto end = std::chrono::high_resolution_clock::now();
    
    // 110 ms
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end-start);
    std::cout << duration.count() << " ms" << std::endl;
    
    
    
    
    /*
     * Faster. Even with the poor hash function, insertions end-up to
     * be O(log n) in average (and O(n) when a rehash occurs).
     */
    tsl::bhopscotch_map<int, int, dos_attack_simulation_hash> map_secure;
    
    start = std::chrono::high_resolution_clock::now();
    for(int i=0; i < 10000; i++) {
        map_secure.insert({i, 0});
    }
    end = std::chrono::high_resolution_clock::now();
    
    // 2 ms
    duration = std::chrono::duration_cast<std::chrono::milliseconds>(end-start);
    std::cout << duration.count() << " ms" << std::endl;
} 

License

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

Issues
  • Add Conan support

    Add Conan support

    Hi!

    I was reviewing your inclusion request for Conan Center and having a conanfile in the source repository is much better.

    I have created an updated conanfile with the following enhancements:

    • Sources are exported instead of cloning the repo (no need to clone sources as you already have them).
    • Include library license in the binary packages.
    • Extract library version from CMakelists.txt

    I have also included a conan folder with some additional things.

    • test_pacakge folder: Includes the example of you readme with conanfile.py consumer of your Conan package library. This is useful to make sure the package is correctly created.

    • Conan Package Tools build script build.py: This scripts generates your Conan package and gets it uploaded to your Bintray.com account (IMPORTANT: You would need to create a new hidden environment variable in Travis CI called "CONAN_PASSWORD" with you Bintray API token).

      I have included a check so only new tags on Travis are actually uploaded (new package on every new release). I have also added a new entry in the Travis matrix for this (independent from any other CI config you already had).

    Hope it makes sense and do not hesitate to make any question. Thanks!

    opened by danimtb 14
  • range-based for loops

    range-based for loops

    This is a minor thing, but it's been bugging me for a little while. One of the differences with std::unordered_map is that value_type is const std::pair<Key,T> instead of std::pair<const Key,T>. Iterators allow us to work around this with the value() method, which gives us a mutable reference to the mapped type.

    This works fine with traditional for loops and iterators.

    for (auto it = map.begin(); it != map.end(); ++it) {
        auto &second = it.value();
        ...
    }
    

    However, range-based for loops don't work as nicely, and AFAIK the only way to get a mutable reference to the mapped type in that case is to const_cast it:

    for (auto &value : map) {
        auto &second = const_cast<T&>(value.second);
        ...
    }
    

    I'm sure there's a reason why value_type has to be const (sorry if I missed it), but it's a bit unfortunate that we can't use range-based for loops as straightfordwardly as with std::unordered_map. Apart from that, great library! :+1:

    opened by jeychenne 6
  • Precalculated hashes

    Precalculated hashes

    Hi tessil,

    we are working on a research database which uses radix clustering. Here, we first hash a value, determine a partition accordingly, and then create a hash table for each partition.

    Since we already calculated a hash for the partitioning, I was wondering why there is no insert method that supports precalculated hashes. Am I overseeing something or has there just not been a reason to implement yet?

    Besides that, I really dig your work here on GitHub. Keep it up!

    opened by Bouncner 6
  • Infinite loop with insert / emplace on MSVC

    Infinite loop with insert / emplace on MSVC

    Certainly the fault of a dumb compiler, but still : given hopscotch_map<void*>, I get an infinite recursion between these two functions:

    template<class P, typename std::enable_if<std::is_constructible<value_type, P&&>::value>::type* = nullptr>
    std::pair<iterator, bool> insert(P&& value) { 
        return emplace(std::forward<P>(value)); 
    }
    
    template<class... Args>
    std::pair<iterator, bool> emplace(Args&&... args) {
        return insert(value_type(std::forward<Args>(args)...));
    }
    
    opened by jcelerier 6
  • Bad insertion time of uint64_t on the latest version (February 7th)

    Bad insertion time of uint64_t on the latest version (February 7th)

    Hi,

    I tried your project yesterday and compared its performance on Windows (VS2015) and Linux (gcc 5.3) vs std::unordered_map. I have 2 use cases for some 'struct A': a) tsl::hopscotch_map<std::string, A&> or tsl::hopscotch_map<gsl::cstring_span<>, A&> b) tsl::hopscotch_map<uint64_t, A&> I must say that for first use case hopscotch_map performed much better than std::unordered_map on both Windows and Linux. However the second use case on Linux has really bad performance. I measured the time of 70.000 insertions of unique uint64_t key/values pairs (and verified they have unique hash values too) and then the cleanup of such a container. The result was more than 100x times worse performance of tsl::hopscotch_map. It looks strange to me as use case a) works at the same speed. I tried to analyze the issue with linux perf tools but didn't have much time for that. Do you have any ideas what is wrong?

    opened by mpusz 6
  • hopscotch_set::emplace doesn't work with MSVC compiler

    hopscotch_set::emplace doesn't work with MSVC compiler

    #include <iostream>
    #include "hopscotch/hopscotch_set.h"
    
    void test() {
    	tsl::hopscotch_set<int> xx;
    	xx.emplace(1);
    	std::cout << "size after emplace:" << xx.size() << std::endl;
    }
    
    void test1() {
    	tsl::hopscotch_set<int> xx;
    	xx.insert(1);
    	std::cout << "size after insert:" << xx.size() << std::endl;
    }
    
    int main(int argc, char* argv[]) {
    	test();
    	test1();
    

    output:

    size after emplace:0                                                                                                                                          
    size after insert:1      
    

    MSVC 2019 compiler

    opened by olegator77 4
  • Warning: comparison 'unsigned int' <= 4294967295 is always true

    Warning: comparison 'unsigned int' <= 4294967295 is always true

    While compiling my code, I'm getting this warning.

    hopscotch_hash.h:1743:39: warning: comparison 'unsigned int' <= 4294967295 is always true [-Wtautological-constant-compare]"

    opened by dan-ryan 4
  • Non-indexed map view for MSVC debugger

    Non-indexed map view for MSVC debugger

    This update to the map visualizer shows the key in the name column and the value in the value column, just like std::map and proposed tsl::sparse_map (https://github.com/Tessil/sparse-map/pull/5) visualizers do.

    Also I moved the bucket visualizer to the end of the .natvis file in order to keep more important (containers > iterators > internal structures and helpers) parts of the file closer to the top for easier navigation and maintenance.

    opened by cmakshin 4
  • compile failed if use with sparse-map

    compile failed if use with sparse-map

    reproduce code:

    #include <string>
    
    #include "sparse-map/tsl/sparse_map.h"
    #include "hopscotch-map/include/tsl/hopscotch_map.h"
    
    
    class Value;
    
    typedef tsl::sparse_map<std::string, Value> SMap;
    typedef tsl::hopscotch_map<std::string, Value> Map;
    
    // general value class
    class Value {
    
    public:
    
        Value& operator=(const SMap& v) noexcept {
            smap = new SMap(v);
            return *this;
        }
    
        Value& operator=(const Map& v) noexcept {
            map = new Map(v);
            return *this;
        }
    
    private:
            Map* map;
            SMap* smap;
    };
    
    
    int main() {
            Value xx;
            return 0;
    }
    

    error message:

    In file included from test.cc:4:
    In file included from ./hopscotch-map/include/tsl/hopscotch_map.h:36:
    ./hopscotch-map/include/tsl/hopscotch_hash.h:405:51: error: invalid application of 'sizeof' to an incomplete type 'tsl::detail_hopscotch_hash::hopscotch_bucket<std::pair<std::__cxx11::basic_string<char>, Value>, 62, false>::value_type' (aka 'std::pair<std::__cxx11::basic_string<char>, Value>')
        using storage = typename std::aligned_storage<sizeof(value_type), alignof(value_type)>::type;
                                                      ^~~~~~~~~~~~~~~~~~
    ./hopscotch-map/include/tsl/hopscotch_hash.h:463:42: note: in instantiation of template class 'tsl::detail_hopscotch_hash::hopscotch_bucket<std::pair<std::__cxx11::basic_string<char>, Value>, 62, false>' requested here
        using neighborhood_bitmap = typename hopscotch_bucket::neighborhood_bitmap;
                                             ^
    ./hopscotch-map/include/tsl/hopscotch_map.h:119:31: note: in instantiation of template class 'tsl::detail_hopscotch_hash::hopscotch_hash<std::pair<std::__cxx11::basic_string<char>, Value>, tsl::hopscotch_map<std::__cxx11::basic_string<char>, Value, std::hash<std::__cxx11::string>, std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<std::__cxx11::basic_string<char>, Value> >, 62, false, tsl::hh::power_of_two_growth_policy<2> >::KeySelect, tsl::hopscotch_map<std::__cxx11::basic_string<char>, Value, std::hash<std::__cxx11::string>, std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<std::__cxx11::basic_string<char>, Value> >, 62, false, tsl::hh::power_of_two_growth_policy<2> >::ValueSelect, std::hash<std::__cxx11::string>, std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<std::__cxx11::basic_string<char>, Value> >, 62, false, tsl::hh::power_of_two_growth_policy<2>, std::__cxx11::list<std::pair<std::__cxx11::basic_string<char>, Value>, std::allocator<std::pair<std::__cxx11::basic_string<char>, Value> > > >' requested here
        using key_type = typename ht::key_type;
                                  ^
    /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/8.1.1/../../../../include/c++/8.1.1/type_traits:1061:56: note: in instantiation of template class 'tsl::hopscotch_map<std::__cxx11::basic_string<char>, Value, std::hash<std::__cxx11::string>, std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<std::__cxx11::basic_string<char>, Value> >, 62, false, tsl::hh::power_of_two_growth_policy<2> >' requested here
          : public __bool_constant<__is_assignable(_Tp, _Up)>
                                                           ^
    /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/8.1.1/../../../../include/c++/8.1.1/type_traits:1073:14: note: in instantiation of template class 'std::is_assignable<Value &, const Value &>' requested here
        : public is_assignable<_Tp&, const _Tp&>
                 ^
    /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/8.1.1/../../../../include/c++/8.1.1/type_traits:1079:14: note: in instantiation of template class 'std::__is_copy_assignable_impl<Value, true>' requested here
        : public __is_copy_assignable_impl<_Tp>
                 ^
    /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/8.1.1/../../../../include/c++/8.1.1/type_traits:144:14: note: (skipping 5 contexts in backtrace; use -ftemplate-backtrace-limit=0 to see all)
        : public conditional<_B1::value, _B2, _B1>::type
                 ^
    /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/8.1.1/../../../../include/c++/8.1.1/type_traits:1049:14: note: in instantiation of template class 'std::is_nothrow_constructible<std::pair<std::__cxx11::basic_string<char>, Value>, std::pair<std::__cxx11::basic_string<char>, Value> &&>' requested here
        : public is_nothrow_constructible<_Tp, _Tp&&>
                 ^
    /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/8.1.1/../../../../include/c++/8.1.1/type_traits:1055:14: note: in instantiation of template class 'std::__is_nothrow_move_constructible_impl<std::pair<std::__cxx11::basic_string<char>, Value>, true>' requested here
        : public __is_nothrow_move_constructible_impl<_Tp>
                 ^
    ./sparse-map/tsl/sparse_hash.h:833:24: note: in instantiation of template class 'std::is_nothrow_move_constructible<std::pair<std::__cxx11::basic_string<char>, Value> >' requested here
        static_assert(std::is_nothrow_move_constructible<ValueType>::value ||
                           ^
    ./sparse-map/tsl/sparse_map.h:119:31: note: in instantiation of template class 'tsl::detail_sparse_hash::sparse_hash<std::pair<std::__cxx11::basic_string<char>, Value>, tsl::sparse_map<std::__cxx11::basic_string<char>, Value, std::hash<std::__cxx11::string>, std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<std::__cxx11::basic_string<char>, Value> >, tsl::sh::power_of_two_growth_policy<2>, tsl::sh::exception_safety::basic, tsl::sh::sparsity::medium>::KeySelect, tsl::sparse_map<std::__cxx11::basic_string<char>, Value, std::hash<std::__cxx11::string>, std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<std::__cxx11::basic_string<char>, Value> >, tsl::sh::power_of_two_growth_policy<2>, tsl::sh::exception_safety::basic, tsl::sh::sparsity::medium>::ValueSelect, std::hash<std::__cxx11::string>, std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<std::__cxx11::basic_string<char>, Value> >, tsl::sh::power_of_two_growth_policy<2>, tsl::sh::exception_safety::basic, tsl::sh::sparsity::medium, tsl::sh::probing::quadratic>' requested here
        using key_type = typename ht::key_type;
                                  ^
    test.cc:18:20: note: in instantiation of template class 'tsl::sparse_map<std::__cxx11::basic_string<char>, Value, std::hash<std::__cxx11::string>, std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<std::__cxx11::basic_string<char>, Value> >, tsl::sh::power_of_two_growth_policy<2>, tsl::sh::exception_safety::basic, tsl::sh::sparsity::medium>' requested here
            smap = new SMap(v);
                       ^
    /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/8.1.1/../../../../include/c++/8.1.1/bits/stl_pair.h:198:12: note: definition of 'std::pair<std::__cxx11::basic_string<char>, Value>' is not complete until the closing '}'
        struct pair
               ^
    In file included from test.cc:4:
    In file included from ./hopscotch-map/include/tsl/hopscotch_map.h:36:
    ./hopscotch-map/include/tsl/hopscotch_hash.h:1233:67: error: no member named 'value' in 'std::is_nothrow_move_constructible<std::pair<std::__cxx11::basic_string<char>, Value> >'
        static_assert(std::is_nothrow_move_constructible<value_type>::value || 
                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
    ./hopscotch-map/include/tsl/hopscotch_map.h:119:31: note: in instantiation of template class 'tsl::detail_hopscotch_hash::hopscotch_hash<std::pair<std::__cxx11::basic_string<char>, Value>, tsl::hopscotch_map<std::__cxx11::basic_string<char>, Value, std::hash<std::__cxx11::string>, std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<std::__cxx11::basic_string<char>, Value> >, 62, false, tsl::hh::power_of_two_growth_policy<2> >::KeySelect, tsl::hopscotch_map<std::__cxx11::basic_string<char>, Value, std::hash<std::__cxx11::string>, std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<std::__cxx11::basic_string<char>, Value> >, 62, false, tsl::hh::power_of_two_growth_policy<2> >::ValueSelect, std::hash<std::__cxx11::string>, std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<std::__cxx11::basic_string<char>, Value> >, 62, false, tsl::hh::power_of_two_growth_policy<2>, std::__cxx11::list<std::pair<std::__cxx11::basic_string<char>, Value>, std::allocator<std::pair<std::__cxx11::basic_string<char>, Value> > > >' requested here
        using key_type = typename ht::key_type;
                                  ^
    /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/8.1.1/../../../../include/c++/8.1.1/type_traits:1061:56: note: in instantiation of template class 'tsl::hopscotch_map<std::__cxx11::basic_string<char>, Value, std::hash<std::__cxx11::string>, std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<std::__cxx11::basic_string<char>, Value> >, 62, false, tsl::hh::power_of_two_growth_policy<2> >' requested here
          : public __bool_constant<__is_assignable(_Tp, _Up)>
                                                           ^
    /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/8.1.1/../../../../include/c++/8.1.1/type_traits:1073:14: note: in instantiation of template class 'std::is_assignable<Value &, const Value &>' requested here
        : public is_assignable<_Tp&, const _Tp&>
                 ^
    /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/8.1.1/../../../../include/c++/8.1.1/type_traits:1079:14: note: in instantiation of template class 'std::__is_copy_assignable_impl<Value, true>' requested here
        : public __is_copy_assignable_impl<_Tp>
                 ^
    /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/8.1.1/../../../../include/c++/8.1.1/type_traits:144:14: note: in instantiation of template class 'std::is_copy_assignable<Value>' requested here
        : public conditional<_B1::value, _B2, _B1>::type
                 ^
    /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/8.1.1/../../../../include/c++/8.1.1/bits/stl_pair.h:368:3: note: (skipping 4 contexts in backtrace; use -ftemplate-backtrace-limit=0 to see all)
                    __and_<is_copy_assignable<_T1>,
                    ^
    /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/8.1.1/../../../../include/c++/8.1.1/type_traits:1049:14: note: in instantiation of template class 'std::is_nothrow_constructible<std::pair<std::__cxx11::basic_string<char>, Value>, std::pair<std::__cxx11::basic_string<char>, Value> &&>' requested here
        : public is_nothrow_constructible<_Tp, _Tp&&>
                 ^
    /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/8.1.1/../../../../include/c++/8.1.1/type_traits:1055:14: note: in instantiation of template class 'std::__is_nothrow_move_constructible_impl<std::pair<std::__cxx11::basic_string<char>, Value>, true>' requested here
        : public __is_nothrow_move_constructible_impl<_Tp>
                 ^
    ./sparse-map/tsl/sparse_hash.h:833:24: note: in instantiation of template class 'std::is_nothrow_move_constructible<std::pair<std::__cxx11::basic_string<char>, Value> >' requested here
        static_assert(std::is_nothrow_move_constructible<ValueType>::value ||
                           ^
    ./sparse-map/tsl/sparse_map.h:119:31: note: in instantiation of template class 'tsl::detail_sparse_hash::sparse_hash<std::pair<std::__cxx11::basic_string<char>, Value>, tsl::sparse_map<std::__cxx11::basic_string<char>, Value, std::hash<std::__cxx11::string>, std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<std::__cxx11::basic_string<char>, Value> >, tsl::sh::power_of_two_growth_policy<2>, tsl::sh::exception_safety::basic, tsl::sh::sparsity::medium>::KeySelect, tsl::sparse_map<std::__cxx11::basic_string<char>, Value, std::hash<std::__cxx11::string>, std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<std::__cxx11::basic_string<char>, Value> >, tsl::sh::power_of_two_growth_policy<2>, tsl::sh::exception_safety::basic, tsl::sh::sparsity::medium>::ValueSelect, std::hash<std::__cxx11::string>, std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<std::__cxx11::basic_string<char>, Value> >, tsl::sh::power_of_two_growth_policy<2>, tsl::sh::exception_safety::basic, tsl::sh::sparsity::medium, tsl::sh::probing::quadratic>' requested here
        using key_type = typename ht::key_type;
                                  ^
    test.cc:18:20: note: in instantiation of template class 'tsl::sparse_map<std::__cxx11::basic_string<char>, Value, std::hash<std::__cxx11::string>, std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<std::__cxx11::basic_string<char>, Value> >, tsl::sh::power_of_two_growth_policy<2>, tsl::sh::exception_safety::basic, tsl::sh::sparsity::medium>' requested here
            smap = new SMap(v);
                       ^
    2 errors generated.
    

    compiler:

    1. clang6.0 / gcc8.1 can not compile this code
    2. vs 2017 can compile this code

    But following code is OK

    #include <string>
    
    #include "sparse-map/tsl/sparse_map.h"
    #include "hopscotch-map/include/tsl/hopscotch_map.h"
    
    
    class Value;
    
    typedef tsl::sparse_map<std::string, Value> SMap;
    typedef tsl::hopscotch_map<std::string, Value> Map;
    
    // general value class
    class Value {
    
    public:
    
        Value& operator=(const SMap& v) noexcept {
            smap = new SMap(v);
            return *this;
        }
    
    /*
        Value& operator=(const Map& v) noexcept {
            map = new Map(v);
            return *this;
        }
    */
    
    private:
            Map* map;
            SMap* smap;
    };
    
    
    int main() {
            Value xx;
            return 0;
    }
    
    opened by justmao945 4
  • set::erase crash

    set::erase crash

    Hello,

    We are hitting a crash when calling erase on the set implementation.

    Exception thrown: read access violation.
    this was nullptr.
    

    Here is the stack trace

    >	Server_r.exe!tsl::detail_hopscotch_hash::hopscotch_bucket<unsigned int,62,0>::neighborhood_infos() Line 487	C++	Symbols loaded.
     	Server_r.exe!tsl::detail_hopscotch_hash::hopscotch_hash<unsigned int,tsl::hopscotch_set<unsigned int,std::hash<unsigned int>,std::equal_to<unsigned int>,std::allocator<unsigned int>,62,0,tsl::power_of_two_growth_policy>::KeySelect,void,std::hash<unsigned int>,std::equal_to<unsigned int>,std::allocator<unsigned int>,62,0,tsl::power_of_two_growth_policy,std::list<unsigned int,std::allocator<unsigned int> > >::find_in_buckets<unsigned int>(const unsigned int & key, unsigned __int64 hash, std::_Vector_const_iterator<std::_Vector_val<std::_Simple_types<tsl::detail_hopscotch_hash::hopscotch_bucket<unsigned int,62,0> > > > it_bucket) Line 1772	C++	Symbols loaded.
     	Server_r.exe!tsl::detail_hopscotch_hash::hopscotch_hash<unsigned int,tsl::hopscotch_set<unsigned int,std::hash<unsigned int>,std::equal_to<unsigned int>,std::allocator<unsigned int>,62,0,tsl::power_of_two_growth_policy>::KeySelect,void,std::hash<unsigned int>,std::equal_to<unsigned int>,std::allocator<unsigned int>,62,0,tsl::power_of_two_growth_policy,std::list<unsigned int,std::allocator<unsigned int> > >::find_in_buckets<unsigned int>(const unsigned int & key, unsigned __int64 hash, std::_Vector_iterator<std::_Vector_val<std::_Simple_types<tsl::detail_hopscotch_hash::hopscotch_bucket<unsigned int,62,0> > > > it_bucket) Line 1760	C++	Symbols loaded.
     	Server_r.exe!tsl::detail_hopscotch_hash::hopscotch_hash<unsigned int,tsl::hopscotch_set<unsigned int,std::hash<unsigned int>,std::equal_to<unsigned int>,std::allocator<unsigned int>,62,0,tsl::power_of_two_growth_policy>::KeySelect,void,std::hash<unsigned int>,std::equal_to<unsigned int>,std::allocator<unsigned int>,62,0,tsl::power_of_two_growth_policy,std::list<unsigned int,std::allocator<unsigned int> > >::erase<unsigned int>(const unsigned int & key, unsigned __int64 hash) Line 1124	C++	Symbols loaded.
     	Server_r.exe!tsl::detail_hopscotch_hash::hopscotch_hash<unsigned int,tsl::hopscotch_set<unsigned int,std::hash<unsigned int>,std::equal_to<unsigned int>,std::allocator<unsigned int>,62,0,tsl::power_of_two_growth_policy>::KeySelect,void,std::hash<unsigned int>,std::equal_to<unsigned int>,std::allocator<unsigned int>,62,0,tsl::power_of_two_growth_policy,std::list<unsigned int,std::allocator<unsigned int> > >::erase<unsigned int>(const unsigned int & key) Line 1117	C++	Symbols loaded.
     	Server_r.exe!tsl::hopscotch_set<unsigned int,std::hash<unsigned int>,std::equal_to<unsigned int>,std::allocator<unsigned int>,62,0,tsl::power_of_two_growth_policy>::erase(const unsigned int & key) Line 279	C++	Symbols loaded.
    

    Thanks !

    opened by yamashi 4
  • Warnings with -Wshadow flag

    Warnings with -Wshadow flag

    Gcc produces warnings if compile with flag -Wshadow.

    /home/ksergey/dev/bitfinex_gateway_ng/deps/zerofw/deps/hopscotch-map/src/hopscotch_set.h:460:34: warning: declaration of ‘count’ shadows a member of ‘tsl::hopscotch_set<Key, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy>’ [-Wshadow]
    
    /home/ksergey/dev/bitfinex_gateway_ng/deps/zerofw/deps/hopscotch-map/src/hopscotch_set.h:461:35: warning: declaration of ‘count’ shadows a member of ‘tsl::hopscotch_set<Key, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy>’ [-Wshadow]
         void reserve(size_type count) { m_ht.reserve(count); }
    
    
    opened by ksergey 4
  • Occasional map misbehavior, inserted element not found later on

    Occasional map misbehavior, inserted element not found later on

    Hello,

    We are experiencing a weird misbehavior with tsl/hopscotch_map, bisected to commit 5c5770adf28d76f2f00a15166c71e42b63141f8a being the culprit.


    According to its changelog entry, this looks like an innocent commit purely renaming variables, namely m_buckets to m_buckets_data and m_first_or_empty_bucket to m_buckets. However, danger lurks around in one of the old names being the same as the other new name.

    At several places (e.g. hopscotch_hash.h line 1246 being the first one) m_buckets remains m_buckets. Based on the changelog's wording, these look like accidental mistakes rather than intentional "changes".


    Into our tsl::hopscotch_map<int, void *> we insert about 1000 entries (using map[key] = val) and erase about 800 (using it = map.find(key); blahblah; map.erase(it) and then no longer using it afterwards). These operations interleave each other in kinda random order, and we sometimes re-add a key that we erased earlier.

    Then, after one insertion, the following situation arises:

    If I iterate through all the items using for (auto it : map) {...} then I get all the about 200 items, as expected.

    However, for one of these entries map.count(key) gives 0 instead of the expected 1. Trying to access this item using .at(key) raises an exception, as usual for missing entries. Or, trying to access this key using [key] inserts this item again, with the default value of nullptr. After this operation, if I loop through the items again using for (auto it : map) {...} then this key gets listed twice, once with the expected value and once with nullptr. And at this point it becomes another key that is "missing" in this weird sense that looping over all the entries finds it, but looking it up directly does not.


    Unfortunately I couldn't come up with a self-contained test demonstrating the failure, and I cannot give you access to our in-house software that every now and then triggers this bug. Our software has a very non-deterministic behavior by its nature, but as of your aforementioned commit we see the misbehavior about 1 out of 20-50-ish cases. We haven't seen misbehavior with your hopscotch_map prior to the mentioned commit during thousands of runs, nor with the standard unordered_map.

    Let me know if you need any help in debugging this issue (without me digging deeply into your code :)). For example, if you create a version that dumps into a global fd the memory region of the map after every insertion/deletion, I'd be happy to test that. But maybe you just want to revert the functionality and redo the variable naming properly :)

    Thanks in advance!

    opened by egmontkob 23
Releases(v2.3.0)
  • v2.3.0(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)
  • v2.2.1(Feb 17, 2019)

  • v2.2.0(Jan 26, 2019)

    • Rename CMake project name from tsl_hopscotch_map to tsl-hopscotch-map for coherence with the convention used by most package managers. The find_package(tsl-hopscotch-map) command must now be used instead of the find_package(tsl_hopscotch_map).
    • Set bucket count for default constructed map/set to 0 to avoid any allocation.
    • On Windows, add tsl-hopscotch-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").
    Source code(tar.gz)
    Source code(zip)
  • v2.1.0(Nov 3, 2018)

    • Add installation rules in the CMake of the project.
    • Add MSVC debugger visualization .natvis file.
    • Fix issue #41 in max_size() function resulting in compilation error. The variable bucket_hash::hash_type doesn't exist anymore due to previous refactoring. Remove the hopscotch_bucket::max_size as this is now obsolete.
    Source code(tar.gz)
    Source code(zip)
  • v2.0.1(Jul 30, 2018)

    • In CMakeList.txt, only use cxx_std_11 in target_compile_features when the CMake version is >= 3.8 (#37).
    • Move the static_assert checking that value_type is nothrow move constructible or copy constructible inside the constructor to avoid issues when Key and/or T are not commplete types (#36).
    Source code(tar.gz)
    Source code(zip)
  • v2.0.0(Jul 1, 2018)

    General overhaul of the library introducing minor backward incompatibilities.

    • Move the header files from src to include/tsl for more coherence with other C++ libraries.
    • For CMake users, add an exported target tsl::hopscotch_map to be used with target_link_libraries.
    • Move growth policies from the tsl namespace to the tsl::hh namespace.
    • Add GrowthFactor template parameter to tsl::hh::power_of_two_growth_policy.
    • Rename hopscotch_sc_map to bhopscotch_map and hopscotch_sc_set to bhopscotch_set.
    • Check that the max_load_factor passed in parameter is between 0.1 and 0.95.
    Source code(tar.gz)
    Source code(zip)
  • v1.5.0(May 27, 2018)

    • Correct issue #31, a moved tsl::hopscotch_map or tsl::hopscotch_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 memory will be allocated.
    • Add iterator mutable_iterator(const_iterator pos) method to convert a const iterator to a mutable iterator.
    • Add a void clear() noexcept method to growth policies classes. If you use a custom GrowthPolicy check the interface update.
    Source code(tar.gz)
    Source code(zip)
  • v1.4.0(Jul 29, 2017)

    • Add iterator mutable_iterator(const_iterator pos) method.
    • Add erase method taking a precalculated hash in parameter similar to lookup functions.
    • Reduce default max load factor to 0.9.
    • Add mandatory max_bucket_count() method to GrowthPolicy to take into account the possible limitations of the growth policy.
    • Fix the number of reserved buckets on range insert (i.e. void insert(InputIt first, InputIt last)). The amount was too low.
    Source code(tar.gz)
    Source code(zip)
  • v1.3.3(Jul 16, 2017)

    • Critical bug correction (#27), on rehash some elements were lost in the overflow list in some corner cases.
    • Use std::uint_least* instead of std::uint* for better portability.
    Source code(tar.gz)
    Source code(zip)
  • v1.3.2(Jul 11, 2017)

    • Use 'Empty Base Optimization' for Hash, KeyEqual and GrowthPolicy to reduce a bit the sizeof(hopsoctch_map).
    • Bug correction (#26), make count() works for tsl::set.
    Source code(tar.gz)
    Source code(zip)
  • v1.3.1(Apr 24, 2017)

  • v1.3.0(Mar 14, 2017)

    • Add tsl::prime_growth_policy which keeps the size of the map/set to a prime number.
    • Bug fix #18: resolve compilation issue tsl::mod_growth_policy
    Source code(tar.gz)
    Source code(zip)
  • v1.2.1(Mar 11, 2017)

    • Bug fix #17: restore the copy constructor of hopscotch_map/set and hopscotch_sc_map/set.
    • Bug fix: only allow StoreHash if a power of two size is used.
    Source code(tar.gz)
    Source code(zip)
  • v1.2.0(Mar 7, 2017)

    • Allow the hash to be stored alongside the neighborhood bitmap.
    • Add a more flexible growth policy.
    • DoS resistant version of hopscotch_map/set: hopscotch_sc_map/set.
    • Split hopscotch_map.h into hopscotch_hash.h, hopscotch_map.h and hopscotch_set.h.
    • Minor bugfixes.
    Source code(tar.gz)
    Source code(zip)
  • v1.1.0(Feb 18, 2017)

    • Add support for heterogeneous lookup.
    • Add insert_or_assign method.
    • Add template<class P> std::pair<iterator,bool> insert(P&& value) method.
    • Add T& operator[](Key&& key) method.
    • Add methods taking a hint in parameter.
    Source code(tar.gz)
    Source code(zip)
  • v1.0.1(Feb 3, 2017)

  • v1.0.0(Nov 1, 2016)

  • v0.4.1(Oct 19, 2016)

  • v0.4.0(Oct 13, 2016)

  • v0.3.1(Oct 9, 2016)

    • When searching for an empty bucket trough linear probing, limit the search to 4096 buckets before rehash.
    • Add some space for the neighbours of the last few buckets.
    Source code(tar.gz)
    Source code(zip)
  • v0.3.0(Sep 29, 2016)

    • Store std::pair<Key, T> instead of std::pair<const Key, T> allowing us to move keys on rehash or when displacements occur on insert.
    • Backward incompatibility: iterators now return const std::pair<Key, T> reference instead of std::pair<const Key, T>. To modify the value of a key-value pair in a map you have to call the value() method of the iterator to get a mutable reference to T.
    Source code(tar.gz)
    Source code(zip)
  • v0.2.2(Sep 20, 2016)

  • v0.2.1(Sep 5, 2016)

    • Bug fix: the strong exception guarantee was not valid on insert and rehash, it's now fixes.
    • Optimization: on rehash, unnecessary calls to find were done
    Source code(tar.gz)
    Source code(zip)
  • v0.1.0(Aug 21, 2016)

Owner
Thibaut Goetghebuer-Planchon
Thibaut Goetghebuer-Planchon
A fast, memory efficient hash map for C++

I now recommend using the parallel hashmap instead of sparsepp, unless if you are stuck with a non C++11 compatible compiler, or if using a little bit

Gregory Popovitch 1.1k Jun 23, 2022
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 Ankerl 1.2k Jun 21, 2022
A c++ toolbox of locality-sensitive hashing (LSH), provides several popular LSH algorithms, also support python and matlab.

LSHBOX-0.9 A C++ Toolbox of Locality-Sensitive Hashing for Large Scale Image Retrieval, Also Support Python and MATLAB. Change Log 2015.07.04 A new LS

null 265 Jun 16, 2022
🏅State-of-the-art learned data structure that enables fast lookup, predecessor, range searches and updates in arrays of billions of items using orders of magnitude less space than traditional indexes

The Piecewise Geometric Model index (PGM-index) is a data structure that enables fast lookup, predecessor, range searches and updates in arrays of bil

Giorgio Vinciguerra 604 Jun 24, 2022
A drop-in replacement for std::list with 293% faster insertion, 57% faster erasure, 17% faster iteration and 77% faster sorting on average. 20-24% speed increase in use-case testing.

plf_list A drop-in replacement for std::list with (on average): 293% faster insertion 57% faster erasure 17% faster iteration 77% faster sorting 70% f

Matt Bentley 115 Apr 11, 2022
ring-span lite - A C++yy-like ring_span type for C++98, C++11 and later in a single-file header-only library

ring-span lite: A circular buffer view for C++98 and later Contents Example usage In a nutshell Dependencies Installation Synopsis Reported to work wi

Martin Moene 122 May 23, 2022
C++ implementation of a fast hash map and hash set using hopscotch hashing

A C++ implementation of a fast hash map and hash set using hopscotch hashing The hopscotch-map library is a C++ implementation of a fast hash map and

Thibaut Goetghebuer-Planchon 551 Jun 17, 2022
C++ implementation of a fast hash map and hash set using robin hood hashing

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 has

Thibaut Goetghebuer-Planchon 771 Jun 24, 2022
C++ implementation of a fast hash map and hash set using robin hood hashing

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 has

Thibaut Goetghebuer-Planchon 768 Jun 19, 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 350 Jun 26, 2022
Generate Height map with Generator (OpenGL and imgui) and Construct Splat Map with generated height map using Algorithm

Generate Height map with Generator (OpenGL and imgui) and Construct Splat Map with generated height map using Algorithm(DPS, BFS, Gradient Descent ... etc) . At Renderer, with height map and blend map which are generated in front of this stage, render high quality terrain with OpenGL

Snowapril 35 Mar 22, 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 63 May 28, 2022
A fast, memory efficient hash map for C++

I now recommend using the parallel hashmap instead of sparsepp, unless if you are stuck with a non C++11 compatible compiler, or if using a little bit

Gregory Popovitch 1.1k Jun 23, 2022
traces tcp requests in kernel. allow to set up IPs to filter dynamically using bpf-map.

ttcp cilium/ebpf/examples/tcprtt에다가 BPF_MAP_TYPE_HASH를 추가해서 srcAddr을 필터링하도록 수정함. 어플리케이션에는 Http API를 추가해서 필터링할 IP를 추가, 삭제, 조회할 수 있도록 함. Getting Startd

null 8 May 20, 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 fantasy map generator based on Martin O'Leary's "Generating fantasy map" notes

Fantasy Map Generator This program is an implementation of a fantasy map generator written in C++ based on the methods described in Martin O'Leary's "

Ryan Guy 610 Jun 19, 2022
A lightweight C++14 parsing library for tmx map files created with the Tiled map editor

tmxlite Description A lightweight C++14 parsing library for tmx map files created with the Tiled map editor. Requires no external linking, all depende

Matt Styles 307 Jun 18, 2022
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 Ankerl 1.2k Jun 21, 2022
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 Jun 28, 2022
oZKS (Ordered Zero-Knowledge Set) is a library that provides an implementation of an Ordered (and Append Only) Zero-Knowledge Set.

Ordered Zero-Knowledge Set - oZKS Introduction oZKS is a library that provides an implementation of an Ordered (and Append Only) Zero Knowledge Set. A

Microsoft 6 Mar 25, 2022
Implementation of Univaraint Linear Regresion (Supervised Machine Learning) in c++. With a data set (training set) you can predict outcomes.

Linear-Regression Implementation of Univaraint Linear Regresion (Supervised Machine Learning) in c++. With a data set (training set) you can predict o

vincent laizer 1 Nov 3, 2021
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
Consistent Hashing Using Fibonacci Encoding

fibonacci_table This does not work as I thought it would. I did not manage to compute an inverse fibonacci mapping. It works, but just like linear has

Wolfgang Brehm 10 Jan 30, 2021
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 5 May 31, 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
C++11 header-only library that offers small vector, small flat map/set/multimap/multiset.

sfl library This is header-only C++11 library that offers several new containers: small_vector small_flat_set small_flat_map small_flat_multiset small

null 9 Jun 18, 2022
HashLibPlus is a recommended C++11 hashing library that provides a fluent interface for computing hashes and checksums of strings, files, streams, bytearrays and untyped data to mention but a few.

HashLibPlus HashLibPlus is a recommended C++11 hashing library that provides a fluent interface for computing hashes and checksums of strings, files,

Telepati 7 Apr 11, 2022