# Sparsepp: an open addressing hash map whose author now recommends something else

> Sparsepp is a header-only C++ hash map derived from Google's sparsehash, built on open addressing with roughly one byte of overhead per entry and a cheap resize, and the project's own banner now tells you to use the author's parallel-hashmap instead unless you are on a pre C++11 compiler or cannot afford the extra memory. It suits a specific memory constrained situation rather than a general one.

**greg7mdp/sparsepp** — A fast, memory efficient hash map for C++

- Repository: https://github.com/greg7mdp/sparsepp
- Stars: 1,317 · Forks: 126
- Language: C++
- License: NOASSERTION
- Published: 2026-10-19 · Updated: 2026-10-19 · Language: en
- Canonical page: https://hysenlabs.com/projects/greg7mdp-sparsepp

## The banner at the top of the README

The first thing in the Sparsepp README is a recommendation to use a different project, and that is the most important thing to know about it.

The author now recommends using the parallel hashmap instead of sparsepp, unless you are stuck with a non C++11 compatible compiler, or if using a little bit more memory is not acceptable. He says he will personally switch to using the parallel hashmap, which he believes offers a significantly better tradeoff, namely slightly higher memory usage and much faster.

This is worth reading as an engineering statement rather than a retirement notice. The project is not dead. The last push to the repository was on 2026-09-19, and the most recent release is 1.23, named 2026.1 Stable, from 2026-06-13. But the author of the code is telling you that the code is not where he would start today.

That inverts the usual way of evaluating a library. Instead of asking whether it is fast enough, the question becomes whether your situation matches one of the two exceptions the author names, a pre C++11 compiler, or a hard memory ceiling.

The history explains the exception about the compiler. Sparsepp was derived from Google's excellent sparsehash implementation, and the earlier releases are named for the era they belong to, with 1.21 named 2018 Stable and 1.22 named 2018.2 Stable, both from 2018. The library predates the parallel hashmap, and it predates the C++11 requirement of that successor.

## Open addressing, and the memory problem it solves

Sparsepp is a hash map that, like Google's dense_hash_map, uses open addressing. The README explains the model: the hash table entries are conceptually stored in a big array, and collisions are not resolved using a linked list but by probing.

The problem with open addressing is the resize. When the array has to grow, the high mark for memory usage is typically three times the current map size, because a new array twice as big as the current one is allocated and the old contents are copied into it. So a map that is comfortably small most of the time still has a moment where it needs triple the memory.

Sparsepp's implementation resolves that, and the memory usage high mark shows only a small bump when resizing. Combined with the stated goal of extremely low memory usage, typically about one byte overhead per entry, that is the whole argument for the library.

The other goals are a drop-in alternative for unordered_map and unordered_set, and being very efficient, typically faster than your compiler's unordered map or set or Boost's. The README is honest about the comparison with Google's dense_hash_map, which is consistently faster but at the cost of much greater memory usage, especially when the final size of the map is not known in advance and insertions cause a resizing.

So the positioning is precise. It is the memory-lean option among the open addressing maps, and it is slower than the fastest one.

A detailed comparison of various hash implementations, including Sparsepp, is in the write-up the repository keeps at bench.md, which is the document to read before making a decision based on numbers.

## Installing it, and what the API looks like

No compilation is needed, because the library is header-only, and the installation consists in copying the sparsepp directory wherever it will be convenient to include in your project.

The example in the README shows the intended usage, and it is deliberately familiar.

```c++
#include <iostream>
#include <string>
#include <sparsepp/spp.h>

using spp::sparse_hash_map;

int main()
{
    sparse_hash_map<std::string, std::string> email =
    {
        { "tom",  "tom@gmail.com"},
        { "jeff", "jk@gmail.com"},
        { "jim",  "jimg@microsoft.com"}
    };

    for (const auto& n : email)
        std::cout << n.first << "'s email is: " << n.second << "\n";

    email["bill"] = "bg@whatever.com";

    return 0;
}
```

The class templates mirror the standard ones, with the hash function, the equality predicate and the allocator as template parameters.

```c++
namespace spp
{
    template <class Key,
              class T,
              class HashFcn  = spp_hash<Key>,
              class EqualKey = std::equal_to<Key>,
              class Alloc    = libc_allocator_with_realloc<std::pair<const Key, T>>>
    class sparse_hash_map;

    template <class Value,
              class HashFcn  = spp_hash<Value>,
              class EqualKey = std::equal_to<Value>,
              class Alloc    = libc_allocator_with_realloc<Value>>
    class sparse_hash_set;
};
```

The default allocator is libc_allocator_with_realloc, which is the realloc based allocator that is the point of the memory design, since it can grow a block in place instead of allocating a new one and copying.

The library is also packaged for Conan, with a conanfile.py at the root, and the repository has an examples directory with a makefile and projects for Visual Studio.

## The invalidation rules, and the one that differs from the standard

There is a warning section in the README, and it is the part to read before writing code against this map.

Erasing elements is likely to invalidate iterators, for example when calling erase. Inserting new elements is likely to invalidate iterators as well, and the README notes that iterator invalidation can also happen with std::unordered_map if rehashing occurs due to the insertion. But the third point is the one that differs. References to values stored in a sparse_hash_map or set are likely to be invalidated on insert and erase, and this is not the case for std::unordered_map or set.

That is a real semantic difference and it is not a detail you can ignore. Code that holds a reference or a pointer to a mapped value across an insertion is correct with the standard container and undefined with this one.

The erase behaviour is otherwise conformant. Calls to erase may invalidate iterators, but, conformant to the C++11 standard, the position and range erase functions return an iterator pointing to the position immediately following the last of the elements erased. That makes the erase-while-iterating pattern work, and the README shows it for deleting odd values.

```c++
for (auto it = c.begin(); it != c.end(); )
    if (it->first % 2 == 1)
       it = c.erase(it);
    else
       ++it;
```

The order of the elements that are not erased is preserved, as it is for std::unordered_map.

There is one more requirement on the values. Values inserted into sparsepp have to either be copyable and movable, or just movable, and the examples directory has a movable.cc showing that case.

## Bucket APIs, the Windows allocator and integer hashing

Three smaller details that each reflect a design decision.

The bucket API is adapted, because items are not grouped into buckets in an open addressing table. max_bucket_count is equivalent to max_size, and bucket_count returns the sparse table size, which is normally at least twice the number of items inserted. Code that uses the bucket API to reason about load factor will read a different number from the standard container, and code that sizes a bucket array from bucket_count will allocate more than it expects.

The Windows allocator is opt-in. When building with the Microsoft compiler, a custom allocator is provided because the default one from the Visual C++ runtime fragments memory when reallocating. It is enabled by defining a preprocessor variable before including the header, with SPP_USE_SPP_ALLOC set to 1.

The README is careful about when to use it, and the warning is the useful part. It is desirable only when creating large sparsepp hash maps. If you create lots of small hash maps, memory usage may increase instead of decreasing, because for each instance the custom allocator creates a new memory space to allocate from, which is typically 4K, so it may be a big waste if just a few items are allocated.

Integer keys get a default hash that mixes the bits of the keys, following the well known integer hashing, and the reason is a pathological case. If the inserted keys are sequential, the lookup on non-present keys becomes very slow, and mixing the bits prevents that. You can of course supply your own hash function, and the README shows a 64 bit and a 32 bit version using the FNV constants.

The repository also ships an spp.natvis file, which is a debugger visualisation file, and a tests directory.

## The alternatives, and what the project state tells you

Since the banner points elsewhere, it is worth being precise about what the alternatives are and what the difference is.

The first alternative is the author's parallel hashmap, which the banner names and describes as a significantly better tradeoff of slightly higher memory usage for much faster performance. It is also a different generation of code, since Sparsepp's C++11 support is listed as a goal of its own, which is the constraint the author calls out as the reason to stay with the older library.

The second alternative is simply std::unordered_map, with Boost's versions also mentioned in the comparison. The difference there is the memory overhead per entry and the resize behaviour, and the cost of Sparsepp over the standard container is the reference invalidation rule described earlier, which is a genuine difference in behaviour and not only in performance.

The third is Google's dense_hash_map, which is the fastest of the three in the comparison and the most memory hungry, particularly when the final size is unknown and insertions cause resizing.

On the state of the project, the release naming is worth reading. The current release is 1.23, tagged 2026.1 Stable, and the two before it are 1.22, tagged 2018.2 Stable from September 2018, and 1.21, tagged 2018 Stable from June 2018. The gap between the 2018 releases and the 2026 one is nearly eight years.

The licence recorded for the repository is one that GitHub could not classify, with a LICENSE file at the root, so the terms there are the ones to read if you are shipping this in a product. The CHANGELOG.md at the root is the history.

The project is tested on Windows with Visual Studio 2010 through 2015 and g++, on Linux with g++ and clang++, and on macOS with clang++, which is the compatibility statement in the README.

## Conclusion

Adopt Sparsepp only for a memory constrained C++ program on a pre C++11 toolchain, where the per entry overhead of std::unordered_map is the binding constraint and the parallel map's extra memory is not affordable, because that is the exact case the author describes in the banner. Do not adopt it for new work, since the author states he will personally switch to parallel-hashmap and believes it offers a significantly better tradeoff. Before you rely on it, read the invalidation rules, because references to stored values are likely to be invalidated by insert and erase, which is not true of std::unordered_map.

## FAQ

### Should I use Sparsepp or the parallel hashmap?

The author recommends the parallel hashmap, which he believes offers a significantly better tradeoff of slightly higher memory usage for much faster performance. He suggests sticking with Sparsepp only if you are stuck with a non C++11 compatible compiler, or if the extra memory is not acceptable.

### How is Sparsepp installed?

No compilation is needed, because the library is header-only. The installation consists in copying the sparsepp directory wherever it will be convenient to include in your project, and the header to include is <sparsepp/spp.h>. A conanfile.py is also provided.

### Does erasing from a Sparsepp map invalidate references?

Yes, and this is the difference from std::unordered_map. Erasing and inserting are likely to invalidate iterators, and references to values stored in the map or set are likely to be invalidated on insert and erase, which is not the case for the standard containers.

### Why does Sparsepp use open addressing?

Like Google's dense_hash_map, it stores entries in one array and resolves collisions by probing rather than with linked lists. That gives very low memory overhead, typically about one byte per entry, and the implementation avoids the three times memory high mark that a normal open addressing resize would cause.

## Sources

- [greg7mdp/sparsepp on GitHub](https://github.com/greg7mdp/sparsepp)
- [Issues](https://github.com/greg7mdp/sparsepp/issues)
- [README](https://github.com/greg7mdp/sparsepp/blob/master/README.md)
- [Releases](https://github.com/greg7mdp/sparsepp/releases)

---

Hysen Labs editorial analysis, written from the project's own repository and release notes. Cite the canonical page: https://hysenlabs.com/projects/greg7mdp-sparsepp