键已经存在于 unordered_map 中，但是“find"没有返回未找到 [英] Key already exists in unordered_map, but "find" returns as not found

问题描述

我使用键类型 rot3d 构建了一个 unordered_map，其定义如下:

I constructed an unordered_map using key type rot3d, which is defined below:

#ifndef EPS6
#define EPS6 1.0e-6
#endif

struct rot3d
{
    double agl[3]; // alpha, beta, gamma in ascending order
    bool operator==(const rot3d &other) const
    {
        // printf("== used\n");
        return abs(agl[0]-other.agl[0]) <= EPS6 && abs(agl[1]-other.agl[1]) <= EPS6 && abs(agl[2]-other.agl[2]) <= EPS6;
    }
};

rot3d 的相等性由以下条件定义:每个组件都在与另一个 rot3d 对象相同的组件的小范围内.

Equality of rot3d is defined by the condition that each component is within a small range of the same component from the other rot3d object.

然后我定义了一个值类型 RotMat:

Then I defined a value type RotMat:

struct RotMat // rotation matrix described by a pointer to matrix and trunction number
{
    cuDoubleComplex *mat = NULL;
    int p = 0;
};

最后我用自定义的hash函数定义了一个从rot3d到RotMat的hash表:

In the end, I defined a hash table from rot3d to RotMat using self-defined hash function:

struct rot3dHasher
{
    std::size_t operator()(const rot3d& key) const
    {
        using std::hash;
        return (hash<double>()(key.agl[0]) ^ (hash<double>()(key.agl[1]) << 1) >> 1) ^ (hash<double>()(key.agl[2]) << 1);
    }
};

typedef std::unordered_map<rot3d,RotMat,rot3dHasher> HashRot2Mat; 

我遇到的问题是，一个键被打印在哈希表中，但函数find"却没有被打印出来.没找到.例如，我使用哈希表的迭代器打印了一个键:

The problem I met was, a key was printed to be in the hash table, but the function "find" didn't find it. For instance, I printed a key using an iterator of the hash table:

键:(3.1415926535897931,2.8198420991931510,0.0000000000000000)

但后来我也得到了这个信息，表明没有找到密钥:

But then I also got this information indicating that the key was not found:

(3.1415926535897931,2.8198420991931505,0.00000000000000000)未在哈希表中找到.

虽然这两个键不是 100% 相同，但是=="的定义是一致的.应该确保它们是平等的.那么为什么我在哈希表中看到了这个键，但是find"却没有找到它?

Although the two keys are not 100% the same, the definition of "==" should ensure them to be equal. So why am I seeing this key in the hash table, but it was not found by "find"?

推荐答案

基于哈希的等价比较允许有误报，通过调用operator==来解决.

Hash-based equivalence comparisons are allowed to have false positives, which are resolved by calling operator==.

基于哈希的等价比较不允许有假阴性，但你的有.你的两个不是 100% 相同"键具有不同的散列值，因此该元素甚至无法用作使用 operator== 进行测试的候选元素.

Hash-based equivalence comparisons are not allowed to have false negatives, but yours does. Your two "not 100% the same" keys have different hash values, so the element is not even found as a candidate for testing using operator==.

有必要 (a == b) 暗示 (hash(a) == hash(b)) 并且您的定义打破了这个先决条件.具有损坏前提条件的哈希表可能会在许多方面出现错误行为，包括找不到您要查找的项目.

It is necessary that (a == b) implies (hash(a) == hash(b)) and your definitions break this precondition. A hashtable with a broken precondition can misbehave in many ways, including not finding the item you are looking for.

使用不依赖于散列而是最近邻匹配的不同数据结构.八叉树将是一个明智的选择.

Use a different data structure that is not dependent on hashing, but nearest-neighbor matching. An octtree would be a smart choice.

这篇关于键已经存在于 unordered_map 中，但是“find"没有返回未找到的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！