c++ - 从没有 key 的散列中查找 unordered_map 中的桶

Question

我正在使用 std::unordered_map。我有一个哈希值和一种方法来确定给定的候选键是否是我正在寻找的键，但我没有实际的键。我想查找哈希值对应的桶，然后遍历该桶中的每个元素，看它是否是我要查找的元素。不幸的是，函数 std::unordered_map::bucket(x) 要求 x 是一个键。如果不首先构造键，真的没有办法从哈希值中获取桶吗？

您不需要回答问题的详细信息:我可以构造 key ，但在没有碰撞的常见情况下，这将比仅检查我在水桶是正确的。我有一个低负载因子，所以很少有冲突，即使是冲突，完整的哈希值也不太可能匹配，所以不匹配很快就被确定为不匹配。我很关心这一点，因为我已经通过探查器确定 key 构建需要花费大量时间 - 有很多查找，并且每次查找都需要构建一个 key 。

您实际上不需要回答问题的更多细节:键是整数 vector ，我的查询是两个 vector 的总和。检查给定 vector V 是否是两个 vector A 和 B 的总和比将两个 vector 求和为第三个 vector C=A+B 然后将 C 与 V 进行比较要快得多。我能够确定的哈希值A+B 而不计算实际 vector A+B，因为我存储了这些 vector 的哈希值，并且我的哈希函数 f 具有 f(A+B)=f(A)+f(B) 的属性。所以我只是将存储的两个哈希值相加，得到总和的哈希值。我已经确保保留一个备用 vector ，这样构建 key 就不需要分配内存，但是添加 vector 的代码本身仍然需要大量时间。

Answer 1

您无法避免构造一个键，但您可以避免构造整个键。

例如，假设您有一个 key 类 VectorKey，它封装了一个 std::vector，并缓存了计算出的哈希码。进一步假设您提供了 Hash 和 KeyEqual 的实现，它们从您的 VectorKey 访问缓存的哈希代码，并比较封装的 vector 是否相等。您可以定义 VectorKey 的构造函数，它总是构造一个空的 std::vector，并将缓存的哈希码设置为传递给构造函数的值:

class VectorKey{
    int cached_hash;
    std::vector<int> key;
public:
    VectorKey(const std::vector<int>& _key)
    :    key(_key)
    ,    cached_hash(calc_hash(_key)) {
    }
    // *** This is the centerpiece of the solution: *** 
    // *** this constructor effectively lets you access *** 
    // *** a bucket with nothing more than a hash code. *** 
    VectorKey(int hash)
    :    cached_hash(hash) {
    }
    // More code goes here for getting cached_hash
    // and also for checking equality
private:
    int calc_hash(const std::vector<int>& _key) {
         // calculate the hash code based on the vector
    }
};

有了这样的 key 类，你可以通过构造一个假 key 来快速找到桶:

size_type bucketIndex = myHashMap.bucket(VectorKey(precalculated_hash));