Home

Awesome

<img src="https://github.com/greg7mdp/parallel-hashmap/blob/master/html/img/phash.png?raw=true" width="120" align="middle">

The Parallel Hashmap

License: Apache-2.0 Linux MacOS Windows

Overview

This repository aims to provide a set of excellent hash map implementations, as well as a btree alternative to std::map and std::set, with the following characteristics:

@byronhe kindly provided this Chinese translation of the README.md.

Parallel-hashmap or GTL?

The observant among us may have noticed that I have two github repos, parallel-hashmap and gtl, which both provide very similar functionality. Indeed the hash tables in both are equivalent and the code mostly the same. The main difference is that parallel-hashmap only requires a C++11 compiler, while gtl requires a C++20 compiler.

My recommendation would be to use gtl if you are compiling with C++20 or higher, and parallel-hashmap otherwise. While the included hash maps are equivalent, gtl is where new development occurs, and it will include useful new classes.

Fast and memory friendly

Click here For a full writeup explaining the design and benefits of the Parallel Hashmap.

The hashmaps and btree provided here are built upon those open sourced by Google in the Abseil library. The hashmaps use closed hashing, where values are stored directly into a memory array, avoiding memory indirections. By using parallel SSE2 instructions, these hashmaps are able to look up items by checking 16 slots in parallel, allowing the implementation to remain fast even when the table is filled up to 87.5% capacity.

IMPORTANT: This repository borrows code from the abseil-cpp repository, with modifications, and may behave differently from the original. This repository is an independent work, with no guarantees implied or provided by the authors. Please visit abseil-cpp for the official Abseil libraries.

Installation

Copy the parallel_hashmap directory to your project. Update your include path. That's all.

If you are using Visual Studio, you probably want to add phmap.natvis to your projects. This will allow for a clear display of the hash table contents in the debugger.

A cmake configuration files (CMakeLists.txt) is provided for building the tests and examples. Command for building and running the tests is:

cmake -DPHMAP_BUILD_TESTS=ON -DPHMAP_BUILD_EXAMPLES=ON -B build

cmake --build build

ctest --test-dir build

Example

#include <iostream>
#include <string>
#include <parallel_hashmap/phmap.h>

using phmap::flat_hash_map;

int main()
{
    // Create an unordered_map of three strings (that map to strings)
    flat_hash_map<std::string, std::string> email =
    {
        { "tom",  "tom@gmail.com"},
        { "jeff", "jk@gmail.com"},
        { "jim",  "jimg@microsoft.com"}
    };

    // Iterate and print keys and values
    for (const auto& n : email)
        std::cout << n.first << "'s email is: " << n.second << "\n";

    // Add a new entry
    email["bill"] = "bg@whatever.com";

    // and print it
    std::cout << "bill's email is: " << email["bill"] << "\n";

    return 0;
}

Various hash maps and their pros and cons

The header parallel_hashmap/phmap.h provides the implementation for the following eight hash tables:

The header parallel_hashmap/btree.h provides the implementation for the following btree-based ordered containers:

The btree containers are direct ports from Abseil, and should behave exactly the same as the Abseil ones, modulo small differences (such as supporting std::string_view instead of absl::string_view, and being forward declarable).

When btrees are mutated, values stored within can be moved in memory. This means that pointers or iterators to values stored in btree containers can be invalidated when that btree is modified. This is a significant difference with std::map and std::set, as the std containers do offer a guarantee of pointer stability. The same is true for the 'flat' hash maps and sets.

The full types with template parameters can be found in the parallel_hashmap/phmap_fwd_decl.h header, which is useful for forward declaring the Parallel Hashmaps when necessary.

Key decision points for hash containers:

Key decision points for btree containers:

Btree containers are ordered containers, which can be used as alternatives to std::map and std::set. They store multiple values in each tree node, and are therefore more cache friendly and use significantly less memory.

Btree containers will usually be preferable to the default red-black trees of the STL, except when:

When an ordering is not needed, a hash container is typically a better choice than a btree one.

Changes to Abseil's hashmaps

Memory usage

typememory usageadditional peak memory usage when resizing
flat tablesflat_mem_usageflat_peak_usage
node tablesnode_mem_usagenode_peak_usage
parallel flat tablesflat_mem_usageparallel_flat_peak
parallel node tablesnode_mem_usageparallel_node_peak

Iterator invalidation for hash containers

The rules are the same as for std::unordered_map, and are valid for all the phmap hash containers:

OperationsInvalidated
All read only operations, swap, std::swapNever
clear, rehash, reserve, operator=Always
insert, emplace, emplace_hint, operator[]Only if rehash triggered
eraseOnly to the element erased

Iterator invalidation for btree containers

Unlike for std::map and std::set, any mutating operation may invalidate existing iterators to btree containers.

OperationsInvalidated
All read only operations, swap, std::swapNever
clear, operator=Always
insert, emplace, emplace_hint, operator[]Yes
eraseYes

Example 2 - providing a hash function for a user-defined class

In order to use a flat_hash_set or flat_hash_map, a hash function should be provided. This can be done with one of the following methods:

For example:

#include <parallel_hashmap/phmap_utils.h> // minimal header providing phmap::HashState()
#include <string>
using std::string;

struct Person
{
    bool operator==(const Person &o) const
    {
        return _first == o._first && _last == o._last && _age == o._age;
    }

    friend size_t hash_value(const Person &p)
    {
        return phmap::HashState().combine(0, p._first, p._last, p._age);
    }

    string _first;
    string _last;
    int    _age;
};

For example:

file "Person.h"

#include <parallel_hashmap/phmap_utils.h> // minimal header providing phmap::HashState()
#include <string>
using std::string;

struct Person
{
    bool operator==(const Person &o) const
    {
        return _first == o._first && _last == o._last && _age == o._age;
    }

    string _first;
    string _last;
    int    _age;
};

namespace std
{
    // inject specialization of std::hash for Person into namespace std
    // ----------------------------------------------------------------
    template<> struct hash<Person>
    {
        std::size_t operator()(Person const &p) const
        {
            return phmap::HashState().combine(0, p._first, p._last, p._age);
        }
    };
}

The std::hash specialization for Person combines the hash values for both first and last name and age, using the convenient phmap::HashState() function, and returns the combined hash value.

file "main.cpp"

#include "Person.h"   // defines Person  with std::hash specialization

#include <iostream>
#include <parallel_hashmap/phmap.h>

int main()
{
    // As we have defined a specialization of std::hash() for Person,
    // we can now create sparse_hash_set or sparse_hash_map of Persons
    // ----------------------------------------------------------------
    phmap::flat_hash_set<Person> persons =
        { { "John", "Mitchell", 35 },
          { "Jane", "Smith",    32 },
          { "Jane", "Smith",    30 },
        };

    for (auto& p: persons)
        std::cout << p._first << ' ' << p._last << " (" << p._age << ")" << '\n';

}

Thread safety

Parallel Hashmap containers follow the thread safety rules of the Standard C++ library. In Particular:

Using the Parallel Hashmap from languages other than C++

While C++ is the native language of the Parallel Hashmap, we welcome bindings making it available for other languages. One such implementation has been created for Python and is described below:

Acknowledgements

Many thanks to the Abseil developers for implementing the swiss table and btree data structures (see abseil-cpp) upon which this work is based, and to Google for releasing it as open-source.