Hopscotch-Map: Faster Hash Table with Lower Memory Than std::unordered_map

Tessil's hopscotch-map library on GitHub (768 stars) promises a hash map that outperforms std::unordered_map in most cases while consuming less memory - and it has the benchmarks to back it up.

Open-Addressing Without Sentinel Trickery

Most open-addressing hash tables (like Google's dense_hash_map) force you to reserve a sentinel value for empty buckets. That's a pain with custom types or when you want to use the full value range. Hopscotch-map avoids that entirely. No sentinel needed. The collision resolution uses hopscotch hashing, a cache-friendly scheme that keeps most lookups inside a single cache line.

The library gives you four main classes: tsl::hopscotch_map, tsl::hopscotch_set, and their prime-growth counterparts tsl::hopscotch_pg_map / tsl::hopscotch_pg_set. The power-of-two variants are faster; the prime variants handle poor hash functions better (e.g., pointers with identity hash). The default pick should be tsl::hopscotch_map unless you have a specific reason to go prime.

Concrete Differences from std::unordered_map

The API is close to std::unordered_map, but the iterator semantics differ. operator*() returns const std::pair<const Key, Value>& - to mutate the value you must call it.value(). All non-erase modifying operations invalidate iterators (no stable buckets). Move-only types need a nothrow move constructor. That's the price of open-addressing, and it's well-documented.

DoS Resistance Built In

The bhopscotch_map and bhopscotch_set variants (plus prime-growth versions) give worst-case O(log n) on lookups and deletions, not O(n). This makes them resistant to hash-collision denial-of-service attacks. The trade-off: keys must be LessThanComparable, and performance drops slightly under normal conditions. If you serve user-controlled keys, this is your escape hatch.

Other features worth grabbing: heterogeneous lookups (find with foo* against a std::unique_ptr<foo> key), storing the hash value for faster rehash, passing a known hash to lookups, and full support for -fno-exceptions via std::terminate.

Benchmarks are linked in the repo, and the author also maintains a comparison page against other hash tables like absl::flat_hash_map, folly::F14, and ska::bytell_hash_map. The numbers speak for themselves: hopscotch-map consistently places near the top in mixed workloads.

If you're tuning hash-intensive C++ code, this library deserves a spot in your toolkit - no sentinel headaches, less memory, and a proven collision-resolution strategy.

Source: A C++ implementation of a fast hash map and hash set using hopscotch hashing
Domain: github.com