Ditching std::unordered_map for Cache-Friendly Hopscotch Hashing

C++ developers routinely default to std::unordered_map when they need a key-value store. It is standard, safe, and works out of the box. But under the hood, the standard map is a node-based container. It resolves collisions using closed addressing (chaining), which means every single insertion triggers a heap allocation, and elements are scattered across memory in linked lists. For performance-critical code paths, this architecture is a silent killer that leads to pointer chasing, cache misses, and massive memory overhead.

To solve this, developers are increasingly turning to open-addressing alternatives. Tessil's tsl::hopscotch_map, available on GitHub, is a header-only C++ implementation that uses hopscotch hashing to resolve collisions. It offers a cache-friendly, highly performant alternative that drops directly into most codebases while slashing memory usage.

The Mechanics of Hopscotch Hashing

Hopscotch hashing is an open-addressing algorithm designed to keep elements close to their natural bucket. When a collision occurs, the algorithm looks for an empty slot nearby. If the empty slot is outside a predefined neighborhood (typically 32 buckets), the algorithm hops elements around to pull the empty slot closer to the target bucket.

To keep track of where elements actually landed, each bucket maintains a small neighborhood bitmap. If bit i is set in bucket j's bitmap, it means the element belonging to bucket j is currently sitting at index j + i.

This bitmap approach makes lookups incredibly fast. Instead of traversing a linked list across random heap locations, the CPU only needs to check the target bucket and scan its local bitmap. Because the neighborhood is small and contiguous, the entire search space usually fits within a single CPU cache line.

Some developers argue that hopscotch hashing is less elegant than Robin Hood hashing, which uses a "take from the rich" approach to swap elements based on their distance from their home bucket. While Robin Hood hashing avoids the sparse bitmap overhead of hopscotch, hopscotch hashing provides a unique advantage when strict bounds are required. For instance, Tessil's library offers a bounded variant that guarantees a worst-case lookup of O(log n), making it highly resilient to hash collision attacks.

The Performance and Memory Reality

The architectural differences between node-based chaining and contiguous open-addressing show up clearly in benchmarks. In a test sequentially inserting and querying 30 million integers, the standard library map struggles under the weight of its own allocations, while the hopscotch map runs circles around it.

xychart-beta
    title "Memory Usage for 30M Integer Inserts (MB)"
    x-axis [std::unordered_map, tsl::hopscotch_map]
    y-axis "Memory (MB)" 0 --> 1600
    bar [1493, 321]

Inserting 30 million integers into std::unordered_map takes 11.56 seconds and consumes 1493 MB of memory. The hopscotch map completes the same task in 3.44 seconds (just 30% of the time) and uses only 321 MB of memory (22% of the standard map's footprint).

Query times show a similar, though less dramatic, improvement. Querying 30 million existing keys drops from 1.84 seconds to 1.50 seconds, while querying non-existing keys drops from 1.92 seconds to 1.48 seconds. The massive speedup in insertion comes down to memory allocation: the standard map allocates memory on every single insert, whereas the hopscotch map allocates a contiguous block once and grows it as needed.

The Developer Angle: Integration and Gotchas

Integrating tsl::hopscotch_map is straightforward. It is a header-only library, meaning you can copy the include directory into your project or use the exported target in CMake.

The library provides several classes depending on your safety and performance requirements:

• tsl::hopscotch_map / tsl::hopscotch_set: The default choice. It uses a power-of-two growth policy, meaning bucket mapping uses a fast bitwise AND (hash & (size - 1)) instead of a slow modulo operation. This is the fastest option but can suffer from collisions if your hash function is weak.
• tsl::hopscotch_pg_map / tsl::hopscotch_pg_set: These use a prime growth policy. Mapping uses a prime number modulo, which distributes keys better if you have a poor hash function (like storing pointers with an identity hash). It uses a lookup table of constant primes to help the compiler optimize the modulo operation.
• tsl::bhopscotch_map / tsl::bhopscotch_set: These require keys to be LessThanComparable but provide a worst-case O(log n) bound on lookups and deletions, protecting your application against hash Denial of Service (DoS) attacks.

The Trade-offs

You cannot simply run a global search-and-replace from std::unordered_map to tsl::hopscotch_map without keeping a few critical API differences in mind.

First, iterator invalidation is aggressive. In std::unordered_map, pointers and references to elements remain valid unless that specific element is erased. In tsl::hopscotch_map, any insert operation can trigger a rehash or element shift, invalidating all iterators, references, and pointers. If your code relies on stable element addresses, this library is a non-starter.

Second, iterator values are const by default. To prevent accidental key corruption, iterators return a reference to const std::pair<Key, T> instead of std::pair<const Key, T>. You cannot modify a value directly through the iterator's second member. Instead, you must call the .value() method:

tsl::hopscotch_map<int, int> map = {{1, 1}, {2, 1}};
for(auto it = map.begin(); it != map.end(); ++it) {
    // it->second = 2; // This is illegal and will fail to compile
    it.value() = 2;    // This is the correct way
}

Third, move-only types require noexcept. Because open-addressing tables move elements around during rehashing, your move constructors must be marked noexcept. If they can throw, the library cannot guarantee exception safety during a rehash.

Finally, there is no bucket API. Methods like bucket_size or bucket are missing because they do not make sense in an open-addressing context.

On the plus side, the library offers advanced features that the standard library lacks. It supports heterogeneous lookups, allowing you to find elements using a different type than the key (e.g., searching with a raw pointer foo* when the map stores std::unique_ptr<foo>) without triggering temporary allocations. You can also pass precalculated hashes directly to lookups or use the StoreHash template parameter to store hash values alongside keys, speeding up rehashing when hash functions are expensive.

The Verdict

If your application is bound by memory allocations or CPU cache misses, tsl::hopscotch_map is a highly viable drop-in replacement. It is production-ready, works with exceptions disabled, and matches the standard library's thread-safety guarantees (safe for multiple readers, unsafe for concurrent writes).

For general-purpose code where performance is not a bottleneck, stick with std::unordered_map to keep your iterator guarantees simple. But for game engines, high-frequency trading, network packet processing, or any hot path where every microsecond and megabyte counts, the hopscotch map is well worth the minor API adjustments.