从没有密钥的散列中查找unordered_map中的桶

Question

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

详细介绍了您不需要回答的问题：，我可以构造密钥，但是在没有冲突的常见情况下，这将比只检查我在桶中找到的唯一候选对象是否正确要花费更长的时间。我的负载系数很低，所以冲突很少，即使是碰撞，完整的哈希值也不太可能匹配，所以非匹配很快就被确定为不匹配。我关心这一点，因为我已经用了一个分析器来确定密钥构造需要大量的时间--有很多查找，每次查找都需要构造一个键。

的更多细节，您真的不需要回答这个问题：，键是整数的向量，我的查询是两个向量之和。检验给定向量V是否为两个向量A和B的和，比将两个向量和为第三向量C=A+B，然后比较C和V要快得多，因为我存储了这些向量的哈希值，并且我的散列函数f具有f( A+B )=f(A)+f(B)的性质，所以我可以在不计算实际向量A+B的情况下确定A+B的哈希值。因此，我只是添加两个存储的哈希值，以得到和的哈希值。我已经确保在周围保留一个备用向量，这样构造密钥就不需要内存分配，但是添加向量的代码仍然要花费大量的时间。

Answer 1

您不能避免构造密钥，但可以避免构造整个密钥。

例如，假设您有一个键类VectorKey，它封装了一个std::vector，并缓存计算出来的哈希代码。此外，假设您提供了Hash和KeyEqual的实现，这些实现可以从VectorKey访问缓存的哈希代码，并比较封装的向量是否相等。可以定义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
    }
};

使用这样的键类，您可以通过构造假密钥快速找到桶：

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