Baike.dev
All toolsOnline toolsAI codingTrendingOpen sourceNewsSubmit
Log in
< Back to tools
S

sparse-map

> 编程语言
Open source

C++ implementation of a memory efficient hash map and hash set

367 stars0 likes1 views
WebsiteGitHub

About

C++ implementation of a memory efficient hash map and hash set

A C++ implementation of a memory efficient hash map and hash set

The sparse-map library is a C++ implementation of a memory efficient hash map and hash set. It uses open-addressing with sparse quadratic probing. The goal of the library is to be the most memory efficient possible, even at low load factor, while keeping reasonable performances. You can find an article of Stephen Merity which explains the idea behind google::sparse_hash_map and this project.

Four classes are provided: tsl::sparse_map, tsl::sparse_set, tsl::sparse_pg_map and tsl::sparse_pg_set. The first two are faster and use a power of two growth policy, the last two use a prime growth policy instead and are able to cope better with a poor hash function. Use the prime version if there is a chance of repeating patterns in the lower bits of your hash (e.g. you are storing pointers with an identity hash function). See GrowthPolicy for details.

A benchmark of tsl::sparse_map against other hash maps may be found here. The benchmark, in its additional tests page, notably includes google::sparse_hash_map and spp::sparse_hash_map to which tsl::sparse_map is an alternative. This page also gives some advices on which hash table structure you should try for your use case (useful if you are a bit lost with the multiple hash tables implementations in the tsl namespace).

Key features

  • Header-only library, just add the include directory to your include path and you are ready to go. If you use CMake, you can also use the tsl::sparse_map exported target from the CMakeLists.txt.
  • Memory efficient while keeping good lookup speed, see the benchmark for some numbers.
  • Support for heterogeneous lookups allowing the usage of find with a type different than Key (e.g. if you have a map that uses std::unique_ptr as key, you can use a foo* or a std::uintptr_t as key parameter to find without constructing a std::unique_ptr, see example).
  • No need to reserve any sentinel value from the keys.
  • If the hash is known before a lookup, it is possible to pass it as parameter to speed-up the lookup (see precalculated_hash parameter in API).
  • Support for efficient serialization and deserialization (see example and the serialize/deserialize methods in the API for details).
  • Possibility to control the balance between insertion speed and memory usage with the Sparsity template parameter. A high sparsity means less memory but longer insertion times, and vice-versa for low sparsity. The default medium sparsity offers a good compromise (see API for details). For reference, with simple 64 bits integers as keys and values, a low sparsity offers ~15% faster insertions times but uses ~12% more memory. Nothing change regarding lookup speed.
  • API closely similar to std::unordered_map and std::unordered_set.

Differences compared to std::unordered_map

tsl::sparse_map tries to have an interface similar to std::unordered_map, but some differences exist.

  • By default only the basic exception safety is guaranteed which mean that, in case of exception, all resources used by the hash map will be freed (no memory leaks) but the hash map may end-up in an undefined state (undefined here means that some elements may be missing). This can ONLY happen on rehash (either on insert or if rehash is called explicitly) and will occur if the Allocator can't allocate memory (std::bad_alloc) or if the copy constructor (when a nothrow move constructor is not available) throws and exception. This can be avoided by calling reserve beforehand. It is the same guarantee that the one provided by google::sparse_hash_map and spp::sparse_hash_map which don't provide the strong exception guarantee. For more information and if you need the strong exception guarantee, check the ExceptionSafety template parameter (see API for details).
  • Iterator invalidation doesn't behave in the same way, any operation modifying the hash table invalidate them (see API for details).
  • References and pointers to keys or values in the map are invalidated in the same way as iterators to these keys-values.
  • For iterators, operator*() and operator->() return a reference and a pointer to const std::pair instead of std::pair making the value T not modifiable. To modify the value you have to call the value() method of the iterator to get a mutable reference. Example:
cpp
tsl::sparse_map map = {{1, 1}, {2, 1}, {3, 1}};
for(auto it = map.begin(); it != map.end(); ++it) {
    //it->second = 2; // Illegal
    it.value() = 2; // Ok
}
  • Move-only types must have a nothrow move constructor.
  • No support for some buckets related methods (like bucket_size, bucket, ...).

These differences also apply between std::unordered_set and tsl::sparse_set.

Thread-safety guarantees are the same as std::unordered_map/set (i.e. possible to have multiple readers with no writer).

Optimization

Popcount

The library relies heavily on the popcount operation.

With Clang and GCC, the library uses the __builtin_popcount function which will use the fast CPU instruction POPCNT when the library is compiled with -mpopcnt. Using the POPCNT instruction offers an improvement of ~15% to ~30% on lookups. So if you are compiling your code for a specific architecture that support the operation, don't forget the -mpopcnt (or -march=native) flag of your compiler.

On Windows with MSVC, the detection is done at runtime.

Move constructor

Make sure that your key Key and potential value T have a noexcept move constructor. The library will work without it but insertions will be much slower if the copy constructor is expensive (the structure often needs to move some values around on insertion).

Growth policy

The library supports multiple growth policies through the GrowthPolicy template parameter. Three policies are provided by the library but you can easily implement your own if needed.

  • tsl::sh::power_of_two_growth_policy. Default policy used by tsl::sparse_map/set. This policy keeps the size of the bucket array of the hash table to a power of two. This constraint allows the policy to avoid the usage of the slow modulo operation to map a hash to a bucket, instead of hash % 2n, it uses hash & (2n - 1) (see fast modulo). Fast but this may cause a lot of collisions with a poor hash function as the modulo with a power of two only masks the most significant bits in the end.
  • tsl::sh::prime_growth_policy. Default policy used by tsl::sparse_pg_map/set. The policy keeps the size of the bucket array of the hash table to a prime number. When mapping a hash to a bucket, using a prime number as modulo will result in a better distribution of the hash across the buckets even with a poor hash function. To allow the compiler to optimize the modulo operation, the policy use a lookup table with constant primes modulos (see API for details). Slower than tsl::sh::power_of_two_growth_policy but more secure.
  • tsl::sh::mod_growth_policy. The policy grows the map by a customizable growth factor passed in parameter. It then just use the modulo operator to map a hash to a bucket. Slower but more flexible.

To implement your own policy, you have to implement the following interface.

…

Installation

To use sparse-map, just add the include directory to your include path. It is a header-only library.

If you use CMake, you can also use the tsl::sparse_map exported target from the CMakeLists.txt with target_link_libraries.

cmake
# Example where the sparse-map project is stored in a third-party directory
add_subdirectory(third-party/sparse-map)
target_link_libraries(your_target PRIVATE tsl::sparse_map)  

If the project has been installed through make install, you can also use find_package(tsl-sparse-map REQUIRED) instead of add_subdirectory.

The code should work with any C++17 standard-compliant compiler.

To run the tests you will need the Boost Test library and CMake.

bash
git clone https://github.com/Tessil/sparse-map.git
cd sparse-map/tests
mkdir build
cd build
cmake ..
cmake --build .
./tsl_sparse_map_tests 

Usage

The API can be found here.

All methods are not documented yet, but they replicate the behaviour of the ones in std::unordered_map and std::unordered_set, except if specified otherwise.

Example

…

c++ #include #include #include #include

struct employee { employee(int id, std::string name) : m_id(id), m_name(std::move(name)) { }

// Either we include the comparators in the class and we use `std::equal_to<>`...
friend bool operator==(const employee& empl, int empl_id) {
    return empl.m_id == empl_id;
}

friend bool operator==(int empl_id, const employee& empl) {
    return empl_id == empl.m_id;
}

friend bool operator==(const employee& empl1, const employee& empl2) {
    return empl1.m_id == empl2.m_id;
}


int m_id;
std::string m_name;

};

// ... or we implement a separate class to compare employees. struct equal_employee { using is_transparent = void;

bool operator()(const employee& empl, int empl_id) const {
    return empl.m_id == empl_id;
}

bool operator()(int empl_id, const employee& empl) const {
    return empl_id == empl.m_id;
}

bool operator()(const employee& empl1, const employee& empl2) const {
    return empl1.m_id == empl2.m_id;
}

};

struct hash_employee { std::size_t operator()(const employee& empl) const { return std::hash()(empl.m_id); }

std::size_t operator()(int id) const {
    return std::hash()(id);
}

};

int main() { // Use std::equal_to<> which will automatically deduce and forward the parameters tsl::sparse_map> map; map.insert({employee(1, "John Doe"), 2001}); map.insert({employee(2, "Jane Doe"), 2002}); map.insert({employee(3, "John Smith"), 2003});

// John Smith 2003
auto it = map.find(3);
if(it != map.end()) {
    std::cout first.m_name second  if a map is used or Key for a set.
template
void operator()(const U& value);

};


```c++
struct deserializer {
    // Must support the following types for U: std::uint64_t, float 
    // and std::pair if a map is used or Key for a set.
    template
    U operator()();
};

Note that the implementation leaves binary compatibility (endianness, float binary representation, size of int, ...) of the types it serializes/deserializes in the hands of the provided function objects if compatibility is required.

More details regarding the serialize and deserialize methods can be found in the API.

Issues· 0 open

View all issuesOpen on GitHub

No open issues yet, or sync has not completed.

> Tags

C++c-plus-pluscppdata-structureshash-map

No comments yet. Be the first to share.

> Details

PublishedAug 1, 2026
UpdatedSep 17, 2026
Category编程语言
PricingOpen source

> Related tools

T
TypeScript
JavaScript 的超集,为前端与全栈提供静态类型
P
Python
通用编程语言,广泛用于 Web、数据与 AI
G
Go
Google 推出的简洁高效系统语言