unordered_map 中已存在密钥，但 "find" returns 未找到

Question

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

#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 对象的同一组件的小范围内的条件定义的。

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

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

最后，我使用自定义哈希函数定义了一个从rot3d到RotMat的哈希table：

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;

我遇到的问题是，一个键被打印到散列中 table，但是函数“find”没有找到它。例如，我使用散列 table:

的迭代器打印了一个密钥

Key: (3.1415926535897931,2.8198420991931510,0.0000000000000000)

但是后来我也得到了这个信息，提示没有找到密钥：

(3.1415926535897931,2.8198420991931505,0.0000000000000000) not found in the hash table.

虽然两个键不是100%相同，但是“==”的定义应该保证它们是相等的。那么，为什么我在散列 table 中看到了这个键，但“find”却没有找到它？

Answer 1

Hash-based等价比较允许有误报，通过调用operator==.

解决

Hash-based 等价比较不允许有假阴性，但你的有。您的两个“并非 100% 相同”的键具有不同的哈希值，因此甚至找不到该元素作为使用 operator==.

进行测试的候选元素

(a == b) 暗示 (hash(a) == hash(b)) 是必要的，并且您的定义打破了这个先决条件。前提条件损坏的哈希表可能会以多种方式出现异常，包括找不到您要查找的项目。

使用不依赖于散列但 nearest-neighbor 匹配的不同数据结构。八叉树将是一个明智的选择。

Answer 2

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.

这不是等价的。你必须有 a==b 和 b==c 暗示 a==c。你的不符合这个要求。

在标准算法或容器中使用 non-equality 会破坏标准先决条件，这意味着您的程序是 ill-formed，不需要诊断。

您的散列也以不同方式散列等效值。也是违法的。

解决此问题的一种方法是构建存储桶。每个桶的大小都是你的 epsilon。

要查找某个值是否在您的存储桶中，请检查您将探测值放入的存储桶，以及所有相邻的存储桶（3^3 或 27 个）。

对于每个元素，仔细检查距离。

struct bucket; // array of 3 doubles, each a multiple of EPS6.  Has == and hash.  Also construct-from-rod3d that rounds.
bucket get_bucket(rot3d);

现在，很可能您只是在缓存。在 EPS-ish 之内就足够了。

template<class T, class B>
struct adapt:T{
  template<class...Args>
  auto operator()(Args&&...args)const{
    return T::operator()( static_cast<B>(std::forward<Args>(args))... );
  }
  using is_transparent=void;
};
std::unordered_map<bucket, RotMat, adapt<std::hash<rot3d>, bucket>, adapt<std::equal_to<>, bucket>> map;

这里我们将 rod3ds 动态转换为桶。

unordered_map 中已存在密钥，但 "find" returns 未找到

Key already exists in unordered_map, but "find" returns as not found

c++

unordered-map