在没有密钥的情况下从散列中查找桶unobdered_map

Question

我正在使用std :: unordered_map。我有一个散列值和一种方法来确定给定的候选键是否是我正在寻找的键，但是我没有真正的键。我想查找与哈希值相对应的存储桶并遍历该存储桶中的每个元素，以查看它是否是我正在查找的元素。不幸的是，函数std :: unordered_map :: bucket（x）需要x是一个键。没有首先构造密钥，是否真的没有办法从哈希值获取桶？

，你不需要回答的问题详细信息：我可以构建的关键，但在没有冲突的常见情况，这将需要比如果单候选人我已经在桶中是唯一的检查长正确对象，真爱。我的负载因数很低，所以冲突很少，甚至在发生冲突时，完整的散列值不太可能匹配，因此很快就会判定不匹配。我关心这一点是因为我已经确定了一个关于剖析器的关键构造要花费大量时间 - 有很多查找，每次查找都需要构建一个关键。

甚至更​​多的细节，你真的不需要回答这个问题：关键是向量的整数，我的查询是两个向量的总和。检查给定向量V是否是两个向量A和B之和要比将两个向量求和成第三个向量C = A + B然后将C与V进行比较要快。我能够确定哈希值A + B，因为我存储了这些向量的散列值，而我的散列函数f具有f（A + B）= f（A）+ f（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));