如何将哈希值传递到无序映射中以减少时间锁定？

Question

我有一个被锁包裹的无序映射。

多个线程正在进行查找、插入操作。因此需要锁。

我的问题是，我不希望在无序映射代码中进行哈希计算，因为该哈希函数需要时间，因此锁会被无谓地保持。

我的想法是，在锁外由调用者计算哈希并在查找和插入时将其传递到无序映射中。

使用标准的无序映射，这是否可行？

- steviekm3

---

哈希您的键真的很慢吗（对于字符串来说可能是这样！）。您是否进行了分析以确定这是否真正成为瓶颈？ - Chad

瓶颈在哈希函数和字符串比较中。最小化工作量需要进行哈希，然后进行比较。对于字符串，两者都是与键的长度成线性关系。 - steviekm3

Answer 1

您可以预先计算哈希值并将其存储在键中，然后在锁定映射的互斥量时使用自定义哈希函数来检索它：

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

更新:

自从审查了这个答案后，我想到我们可以做得更好：

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

- Richard Hodges