12

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

您不需要回答问题的详细信息：我可以构造密钥，但在没有冲突的常见情况下，这将比仅检查我在存储桶中找到的单个候选者是否正确需要更长的时间。我的负载因子很低，因此碰撞很少，即使对于碰撞，完整的哈希值也不太可能匹配，因此不匹配很快就会被确定为不匹配。我之所以关心这一点，是因为我已经通过分析器确定密钥构建需要大量时间 - 有很多查找，每次查找都需要构建一个密钥。

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

4

1 回答 1

10

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

例如，假设您有一个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));
于 2012-10-15T16:34:27.060 回答