在没有密钥的情况下从哈希中找到unordered_map中的存储桶 [英] Find bucket in unordered_map from hash without a key

问题描述

我正在使用std :: unordered_map。我有一个哈希值，并且可以确定给定的候选键是否是我要寻找的键，但是我没有实际的键。我想查找与哈希值相对应的存储桶，并遍历该存储桶中的每个元素，以查看它是否是我要寻找的元素。不幸的是，函数std :: unordered_map :: bucket（x）要求x是键。

I am using a std::unordered_map. I have a hash value and a way to determine if a given candidate key is the key that I am looking for, but I do not have an actual key. I want to look up the bucket corresponding to the hash value and go through each element in that bucket to see if it is the element that I am looking for. Unfortunately, the function std::unordered_map::bucket(x) requires x to be a key. Is there really no way to get a bucket from a hash value without first constructing a key?

真的不需要从哈希值中获取桶吗？ 不需要回答这个问题的详细信息：我可以构造密钥，但是在通常没有冲突的情况下，这比只检查我在存储桶中找到的单个候选对象是否正确要花费更长的时间。我的负载因子很低，因此几乎没有冲突，甚至对于一次冲突，完整的哈希值都不太可能匹配，因此很快就确定不匹配。我之所以在意，是因为我已经通过探查器确定了密钥构造要花费大量时间-有很多查找，每次查找都需要构造密钥。

Details that you don't need to answer the question: I could construct the key but in the common case of no collisions this will take longer than only checking if the single candidate I have found in the bucket is the right one. I have a low load factor so there are few collisions and even for a collision the full hash value is unlikely to match, so non-matches are quickly determined not to match. I care about this because I have determined with a profiler that key construction is taking a significant amount of time - there are many lookups and each lookup requires the construction of a key.

您实际上不需要回答的更多详细信息：键是整数的向量，而我的查询是两个向量的和。检查给定向量V是否为两个向量A和B的总和比将两个向量求和为第三向量C = A + B然后将C与V进行比较要快得多。我能够确定H的哈希值A + B无需计算实际向量A + B，因为我存储了这些向量的哈希值，并且我的哈希函数f具有f（A + B）= f（A）+ f（B）的属性。因此，我只将两个存储的哈希值相加即可得到总和的哈希值。我已经确保保留一个备用向量，以便构造键不需要内存分配，但是添加向量的代码仍然需要花费大量时间。

Even more details that you really don't need to answer the question: The keys are vectors of integers and my query is for the sum of two vectors. It is faster to check if a given vector V is the sum of two vectors A and B than to sum the two vectors into a third vector C=A+B and then compare C to V. I am able to determine the hash value of A+B without calculating the actual vector A+B because I store the hash values of these vectors and my hash function f has the property that f(A+B)=f(A)+f(B). So I just add the two stored hash values to get the hash value of the sum. I have already made sure to keep a spare vector around so that constructing a key does not require memory allocation but the code for adding the vectors is still taking a significant amount of time on its own.

推荐答案

您无法避免构造密钥，但是可以避免构造整个密钥。

You cannot avoid constructing a key, but you can avoid constructing the entire key.

例如，假设您有一个键类 VectorKey ，其中封装了 std :: vector ，并缓存计算出的哈希码。进一步假设您提供了 Hash 和 KeyEqual 的实现，这些实现从访问缓存的哈希码VectorKey ，并比较封装的矢量是否相等。您可以定义 VectorKey 的构造函数，该构造函数始终构造一个空的 std :: vector 并将缓存的哈希码设置为传递给构造函数的值：

For example, let's say that you have a key class VectorKey that encapsulates an std::vector, and caches the computed hash code. Further suppose that you provide implementations of Hash and KeyEqual that access the cached hash code off your VectorKey, and compare encapsulated vectors for equality. You can define a constructor of VectorKey that always constructs an empty std::vector, and sets the cached hash code to a value passed to the constructor:

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

有了这样的密钥类，您可以通过构造假密钥来快速找到存储桶：

With a key class like that, you can quickly find buckets by constructing a fake key:

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

这篇关于在没有密钥的情况下从哈希中找到unordered_map中的存储桶的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！