Tessil/robin-map for C++ hash containers

Why robin-map replaces chained C++ hash tables

Tessil/robin-map addresses the need for a compact hash table when applications do not want the node-oriented storage used by a typical chained implementation. It provides both maps and sets, but stores their elements directly in an open-addressed bucket array. The library offers `tsl::robin_map`, `tsl::robin_set`, `tsl::robin_pg_map`, and `tsl::robin_pg_set`, giving developers separate choices for power-of-two and prime-based capacity growth.

The main audience is C++ code that needs a container API resembling `std::unordered_map` or `std::unordered_set`. Particular attention has been given to move-only and non-default-constructible keys and values. The containers also accept heterogeneous lookup types, meaning `find` does not always need a temporary or owning object of the stored key type. The README describes a map keyed by `std::unique_ptr<foo>` being queried with a `foo*` or `std::uintptr_t` without constructing a `std::unique_ptr<foo>`.

Other supported requirements include optional hash storage, caller-supplied precalculated hashes, serialization and deserialization, and operation without language exceptions. These features make the library relevant to parsers, indexes, caches, and other data structures with demanding element types. The README does not claim concurrent mutation support. Its stated thread-safety guarantee is the same as for `std::unordered_map` and `std::unordered_set`: multiple readers are possible when there is no writer.

Linear probing and backward-shift deletion in robin-map

The library combines open addressing with linear robin hood hashing. When a hash maps to an occupied bucket, the implementation examines later buckets in the array. Robin hood ordering treats entries with longer probe distances as moving ahead of entries with shorter probe distances, while maintaining space for entries displaced during insertion. This approach keeps the data inside the bucket array instead of allocating a separate node for every element.

Deletion is performed with a backward shift rather than leaving a tombstone. When an occupied entry is removed, the implementation can shift later entries toward the empty position while preserving their probe relationships. That distinction matters for a long-lived container because the documented mechanism directly addresses vacant buckets created by deletion. The README does not provide a lower-level trace of every boundary check or resizing condition, so code-level claims beyond the stated collision and deletion methods would require inspection of `include/`.

The library allows a known hash to be passed to lookup methods through the documented `precalculated_hash` parameter. It can also store the hash beside an entry when doing so avoids extra storage because of alignment, or when `StoreHash` is requested. Cached hashes can reduce repeated key or equality work during lookup and rehashing. This is a deliberate space and computation trade-off rather than a promise that every workload will pay for the extra stored field.

Choosing power-of-two or prime growth in robin-map

The default growth policy for `tsl::robin_map` and `tsl::robin_set`, `tsl::rh::power_of_two_growth_policy`, keeps the bucket count at a power of two. The README explains that bucket selection can then use a bit mask rather than modulo. That avoids the slower modulo operation, but the policy depends on the hash distributing bits well. If repeated lower-bit patterns cause collisions, the apparent simplicity of a mask can work against the container.

The prime policy, used by `tsl::robin_pg_map` and `tsl::robin_pg_set`, keeps capacity at a prime number. The README says this distributes hashes more evenly when the input hash has repeating lower-bit patterns. It identifies identity hashing of pointers as a case where the prime variants may cope better. The implementation uses a lookup table of constant prime modulo operations so the compiler can optimize modulo calculations, but the README still characterizes the prime policy as slower than the power-of-two option.

This is the clearest selection decision documented by the project. Use the standard classes when a suitable hash function already provides good distribution and avoiding modulo matters. Consider the `robin_pg` classes when hash quality is uncertain or lower-bit repetition is possible. The repository also exposes `GrowthPolicy` as a template parameter, so an application can define its own policy if neither built-in behavior matches its requirements.

Installing and first populating a robin-map

Installation is header-only. The README instructs users to add the repository's `include/` directory to the include path. A CMake-based project can alternatively use the `tsl::robin_map` target exported by `CMakeLists.txt`. The documentation does not provide a package-manager installation command or a standalone configure-and-build sequence, so none should be assumed.

The following first use initializes a `tsl::robin_map<int, int>` with three entries. This is the example shown in the README. The reader should see a map containing keys `1`, `2`, and `3`, with each value initially equal to `1`.

tsl::robin_map<int, int> map = {{1, 1}, {2, 1}, {3, 1}};

The project uses an API close to the standard unordered containers, but this iterator exposes `const std::pair<Key, T>`. A mapped value therefore cannot be changed through `operator->()`. The documented way to obtain mutable access is `it.value()`. Applying the assignment below changes every mapped value to `2`.

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

The iterator invalidation rule should be checked before code that retains iterators. According to the README, any operation that modifies the hash table invalidates all iterators, which is broader than the behavior developers may carry over from `std::unordered_map`.

Exception and iterator constraints in robin-map

The strongest documented exception guarantee has a precise requirement. For a map, `value_type` is `std::pair<Key, T>`; for a set, it is `Key`. The strong exception guarantee holds only when that type is nothrow swappable and nothrow move constructible. The README also explains that a type with a noexcept copy constructor and no move constructor satisfies the stated condition. If a swap or move throws outside these conditions, the container may end in an undefined state.

This makes exception specifications part of container selection rather than an implementation detail to discover during failure handling. Keys and mapped values must be swappable and copyable or movable as required by their roles. The library can be compiled with exceptions disabled, including through `TSL_NO_EXCEPTIONS`. In that mode, it uses `std::terminate` where an exception would otherwise be thrown. The README documents `-fno-exceptions` for Clang and GCC and omitting `/EH` on MSVC, but choosing that mode also requires the application to accept termination-based failure handling.

Iterator and reference stability are another boundary. Any modifying operation invalidates iterators. Pointers and references to stored keys or values are invalidated in the same circumstances. Applications that maintain long-lived references across updates will need to retrieve them after each modification. The API also omits several bucket-oriented operations, including `bucket_size` and `bucket`, so code tied to `std::unordered_map` bucket interfaces will not transfer directly.

robin-map versus `std::unordered_map`

The closest documented alternative is `std::unordered_map`, or `std::unordered_set` for set use. Its interface is more familiar, and code that depends on bucket inspection or standard iterator stability rules may fit it more directly. Tessil/robin-map instead emphasizes open-addressed array storage, a similar but deliberately different API, move-only element support, heterogeneous lookup, optional cached hashes, and serialization hooks.

The concrete differences matter more than the shared naming. `robin-map` iterators expose `const std::pair<Key, T>`, so mutable mapped access goes through `it.value()`. Every table-modifying operation invalidates iterators. It does not implement the documented bucket-related subset, and its strong exception guarantee depends on the `value_type` traits described earlier. These are compatibility constraints for migrations, not merely performance differences.

A custom `GrowthPolicy` is another differentiator, although it does not remove the API or invalidation constraints. The project links an older benchmark comparing `tsl::robin_map` with other hash maps, but the README does not publish current benchmark data. An engineering decision should therefore be based on compatibility and hash behavior first, then on measurements that reflect the application's own keys, load pattern, compiler, and growth policy.

License, maintenance, and robin-map upgrade work

Tessil/robin-map is distributed under the MIT License. The repository also identifies the library as header-only, which keeps deployment simple: consumers include project headers, and a CMake project can use the exported target. The license permits reuse, modification, distribution, and sublicensing subject to its terms, but an organization should review the actual `LICENSE` file when combining this code with its own licensing policy.

The repository is not archived, and its last push was on 2026-06-13. Recent tagged releases include `v1.4.1` on 2025-11-02, `v1.4.0` on 2025-03-30, and `v1.3.0` on 2024-04-20. Those dates indicate recent repository activity and released versions, but the README does not provide upgrade instructions, a changelog summary, compiler compatibility matrix, or migration guide for those releases.

Consequently, an upgrade should be treated as ordinary integration work rather than a documented drop-in operation. The release notes in the repository, tests, and build configuration are the relevant files to inspect for changes in behavior. Because iterator behavior and exception guarantees already differ from the standard container, maintainers should pay particular attention to API changes that affect retained iterators, element traits, and failure handling.

Editorial conclusion

C++ developers should consider Tessil/robin-map when an application wants an `std::unordered_map`-like API, move-only or non-default-constructible elements, heterogeneous lookup, or explicit open-addressing behavior. It is a poor fit for code that depends on bucket-related methods or expects modifying operations to preserve iterators. Before adoption, verify element exception properties, iterator invalidation requirements, hash quality, the selected growth policy, and whether disabling exceptions is compatible with the application.

Frequently asked questions

Official sources

1. Issues
2. License: MIT
3. README
4. Releases
5. Tessil/robin-map on GitHub