Parallel Hashmap

To use flat_hash_set or flat_hash_map with custom types, you must provide a hash function. You can do this in three ways:

1. Hash Functor: Provide a hash functor via the HashFcn template parameter.
2. hash_value() Friend Function: Add a friend size_t hash_value(const T &obj) function to your class. Use phmap::HashState().combine(...) to combine member variables.
3. std::hash Specialization: Inject a specialization of std::hash for your class into the std namespace. This is often done using the phmap_utils.h header to simplify combining hash values with phmap::HashState().

#include <parallel_hashmap/phmap_utils.h>
#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;
};

Include parallel_hashmap/phmap.h to use the hash map implementations. phmap::flat_hash_map is a high-performance, memory-efficient replacement for std::unordered_map that stores keys and values directly in a memory array.

#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;
}

You can achieve high-performance, lock-free concurrent insertion by ensuring each thread only operates on a specific subset of the internal submaps. This is done by computing the hash of the key, determining its target submap index, and having the thread only proceed if that index belongs to its assigned range.

To implement this, use the subcnt() method to get the number of submaps and subidx(hashval) to determine the submap index for a given hash.

template <class HT>
void _fill_random_inner_mt(int64_t cnt, HT &hash, RSU &rsu)
{
    constexpr int64_t num_threads = 8;   // has to be a power of two
    std::unique_ptr<std::thread> threads[num_threads];

    auto thread_fn = [&hash, cnt, num_threads](int64_t thread_idx, RSU rsu) {
        size_t modulo = hash.subcnt() / num_threads;        // subcnt() returns the number of submaps

        for (int64_t i=0; i<cnt; ++i)
        {
            unsigned int key = rsu.next();                  // get next key to insert
            size_t hashval = hash.hash(key);                // compute its hash
            size_t idx  = hash.subidx(hashval);             // compute the submap index for this hash
            if (idx / modulo == thread_idx)                 // if the submap is suitable for this thread
            {
                hash.insert(typename HT::value_type(key, 0)); // insert the value
                ++(num_keys[thread_idx]);                     // increment count of inserted values
            }
        }
    };

    for (int64_t i=0; i<num_threads; ++i)
        threads[i].reset(new std::thread(thread_fn, i, rsu));

    for (int64_t i=0; i<cnt; ++i)
        rsu.next();
    
    for (int64_t i=0; i<cnt; ++i)
        threads[i]->join();
}

You can specialize std::hash for a custom class to make it compatible with phmap containers. Use phmap::HashState().combine() within the specialization to aggregate the hashes of the class members.

// file "Person.h"
#include <parallel_hashmap/phmap_utils.h>
#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
{
    template<> struct hash<Person>
    {
        std::size_t operator()(Person const &p) const
        {
            return phmap::HashState().combine(0, p._first, p._last, p._age);
        }
    };
}

// file "main.cpp"
#include "Person.h"
#include <iostream>
#include <parallel_hashmap/phmap.h>

int main()
{
    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';
}