How to pass hash value into unordered map to reduce time lock held?

Question

I have an unordered map wrapped in a lock.

Multiple threads are doing lookups, inserts. Thus the need for a lock.

My question is I don't want the hash calculation being done in the unordered map code because that hash function does take time so lock is held unnecessarily for that time.

My idea is to have caller calculate hash outside of lock and pass it into the unordered map during lookups, inserts.

Is this possible with standard unordered map ?

Answer 1

You could pre-compute the hash and store it in the key, then use a custom hash function to retrieve it while the map's mutex is locked:

#include <iostream>
#include <unordered_map>
#include <string>
#include <utility>

struct custom_key
{
    custom_key(std::string s)
    : data(std::move(s))
    , hash_value(compute_hash(data))
    {}

    const std::string data;

    static std::size_t compute_hash(const std::string& dat) {
        return std::hash<std::string>()(dat);
    }

    // pre-computed hash
    const std::size_t hash_value;
};

bool operator==(const custom_key& l, const custom_key& r) {
    return l.data == r.data;
}

namespace std {
    template<> struct hash<custom_key> {
        using argument_type = custom_key;
        using result_type = size_t;
        result_type operator()(const argument_type& k) const {
            return k.hash_value;
        }
    };
}
using namespace std;

auto main() -> int
{
    unordered_map<custom_key, std::string> m;

    m.emplace(custom_key("k1"s), "Hello, World");

    return 0;
}

update:

since reviewing this answer, it occurs to me that we can do better:

#include <iostream>
#include <unordered_map>
#include <string>
#include <utility>


/* the precompute key type */

template<class Type>
struct precompute_key {

    /* may be constructed with any of the constructors of the underlying type */
    template<class...Args>
    precompute_key(Args &&...args)
            : value_(std::forward<Args>(args)...), hash_(std::hash<Type>()(value_)) {}

    operator Type &() { return value_; }

    operator Type const &() const { return value_; }

    auto hash_value() const { return hash_; }

    auto value() const { return value_; }

    auto value() { return value_; }

private:
    Type value_;
    std::size_t hash_;
};

template<class Type>
bool operator==(const precompute_key<Type> &l, const precompute_key<Type> &r) {
    return l.value() == r.value();
}

namespace std {
    template<class Type>
    struct hash<precompute_key<Type>> {
        auto operator()(precompute_key<Type> const &arg) const {
            return arg.hash_value();
        }
    };
}

auto main() -> int {
    std::unordered_map<precompute_key<std::string>, std::string> m;

    m.emplace("k1", "Hello, World");

    return 0;
}