Hopscotch-Map: A Fast C++ Hash Map Using Hopscotch Hashing

Hopscotch-Map: A Fast C++ Hash Map Using Hopscotch Hashing

Tessil's hopscotch-map is a header-only C++ library that implements open-addressing hash maps and sets using hopscotch hashing to resolve collisions. It's designed to be cache-friendly and offers better performance than std::unordered_map in most cases, while closely matching google::dense_hash_map but using less memory and providing more functionality.

Key Classes and Variants

The library provides four main classes:

• tsl::hopscotch_map and tsl::hopscotch_set - use a power-of-two growth policy for speed.
• tsl::hopscotch_pg_map and tsl::hopscotch_pg_set - use a prime growth policy for better hash distribution.

Additionally, tsl::bhopscotch_map, tsl::bhopscotch_set, tsl::bhopscotch_pg_map, and tsl::bhopscotch_pg_set require the key to be LessThanComparable but guarantee O(log n) worst-case lookups, making them resistant to hash DoS attacks.

Key Features

• Header-only: Just add the include directory to your include path. CMake integration via tsl::hopscotch_map target.
• Fast: Benchmarks show it outperforms std::unordered_map and is competitive with google::dense_hash_map.
• Move-only and non-default constructible keys/values: Fully supported.
• Heterogeneous lookups: Allows find() with a different type than Key (e.g., foo* when key is std::unique_ptr). Requires KeyEqual::is_transparent.
• No sentinel values: No need to reserve special values for empty/deleted keys.
• StoreHash option: Store the hash value on insert to speed up rehash and lookups when hash or key equality is expensive.
• Precalculated hash: Pass a known hash to find() for faster lookup.
• Exception-free support: Compile with -fno-exceptions or define TSL_NO_EXCEPTIONS; uses std::terminate instead of throw.
• API similar to std::unordered_map: But with some differences.

Differences from std::unordered_map

• Iterator invalidation: Any modifying operation except erase invalidates all iterators.
• References/pointers to keys/values are invalidated similarly on insert.
• operator*() returns const std::pair instead of std::pair. To modify the value, use it.value() = ....
• Move-only types must have a nothrow move constructor.
• No bucket-related methods like bucket_size.

Growth Policies

The GrowthPolicy template parameter controls how the hash table grows. Three policies are provided:

• tsl::hh::power_of_two_growth_policy (default): Uses fast modulo via bitmask, but can cause collisions with poor hash functions.
• tsl::hh::prime_growth_policy (default for _pg variants): Uses prime numbers for better hash distribution, slightly slower.
• tsl::hh::mod_growth_policy: Customizable growth factor, uses modulo directly.

If you see non-zero overflow_size(), you likely have many collisions. Consider a better hash function or a prime growth policy.

Installation

Simply add the include directory to your project. With CMake:

add_subdirectory(third-party/hopscotch-map)
target_link_libraries(your_target PRIVATE tsl::hopscotch_map)

Or install via make install and use find_package(tsl-hopscotch-map REQUIRED).

Code Example

#include 
#include 
#include 

int main() {
    tsl::hopscotch_map map = {{"a", 1}, {"b", 2}};
    map["c"] = 3;
    map.insert({"e", 5});
    map.erase("b");

    for(auto it = map.begin(); it != map.end(); ++it) {
        it.value() += 2;  // Modify value
    }

    for(const auto& key_value : map) {
        std::cout << "{" << key_value.first << ", " << key_value.second << "}\n";
    }

    // Heterogeneous lookup example
    tsl::hopscotch_map map2;
    map2["a"] = 1;
    const std::size_t hash = std::hash{}();
    if(map2.find("a", hash) != map2.end()) {
        std::cout << "Found with precomputed hash\n";
    }

    // StoreHash example
    tsl::hopscotch_map,
                       std::equal_to,
                       std::allocator>,
                       30, true> map3;
    map3["a"] = 1;

    // bhopscotch_map for DoS resistance
    tsl::bhopscotch_map safe_map;
    safe_map[1] = 10;

    return 0;
}

Heterogeneous Lookups

Activate by defining KeyEqual::is_transparent. Example using std::equal_to<>:

struct employee {
    int id;
    std::string name;
    friend bool operator==(const employee& e, int id) { return e.id == id; }
};

struct hash_employee {
    std::size_t operator()(const employee& e) const { return std::hash()(e.id); }
    std::size_t operator()(int id) const { return std::hash()(id); }
};

struct equal_employee {
    using is_transparent = void;
    bool operator()(const employee& e, int id) const { return e.id == id; }
    bool operator()(int id, const employee& e) const { return id == e.id; }
    bool operator()(const employee& a, const employee& b) const { return a.id == b.id; }
};

int main() {
    tsl::hopscotch_map map;
    map[employee{1, "Alice"}] = 100;
    auto it = map.find(1);  // Find by int
    std::cout << it->second; // 100
}

Performance Considerations

• Use tsl::hopscotch_map as default.
• If hash quality is a concern, use tsl::hopscotch_pg_map or tsl::bhopscotch_map.
• For DoS resistance, use tsl::bhopscotch_map which guarantees O(log n) worst-case lookups.
• Enable StoreHash if hash computation is expensive.

Conclusion

Hopscotch-map is a solid choice for C++ projects needing a fast, memory-efficient hash map. Its header-only nature and close API to std::unordered_map make it easy to adopt. For security-critical contexts, the bhopscotch variants provide a strong guarantee against collision attacks. Check the benchmark page for numbers comparing against std::unordered_map, google::dense_hash_map, and others.