c++ - 对于由计算的 double 值组成的键，在 map 或 unordered_map 之间进行选择。

Question

为了在 3d 空间中的一堆平面实体中快速找到共面实体，我想创建一个从 3d 平面到位于该平面中的实体集的映射(估计最多约 1000 个平面和 100000 个实体)

我可以创建自己的自定义类来表示 3D 平面键，但基本上这个类需要(在数学上)四个 double 来唯一标识一个平面:3 个坐标用于法 vector ，一个坐标用于指定平面上的一个点。所以我们有:

struct Plane3d
{
    double n_x, n_y, n_z;
    double u;   // (u*n_x, u*n_y, u*n_z) is a point on the plane

    // some constructors etc.
}

这四个 double 每次都是从所考虑的实体计算的，因此必须考虑舍入误差和 float 比较问题。假设我已经计算出一个合适的(相对)容错度:

const double EPSILON;

但我不想逐一比较所有实体对的共面性(在 O(n^2) 时间内进行分类)，而是创建一个 map 来对我的实体进行分类。

最理想的是 unordered_map(在 O(n) 时间内创建):

unordered_map<Plane3d, vector<Entity>, PlaneHash, PlaneEquality> mapping;

这需要编写两个仿函数:PlaneEquality 没问题，但是...

• 是否可以为四个 double (或什至只是一个普通的 double )编写一个考虑比较误差容限的哈希函数。
• 在规范中我读到相等仿函数仅用于区分同一桶内的相等键。有没有办法确保相同的键实际上最终在同一个桶中？

另一种选择是使用法线贴图(仍然在 O(n log n) 时间内创建)

map<Plane3d, vector<Entity>, PlaneCompare> mapping; 

PlaneCompare 仿函数听起来可行，我可以使用四个 double 的字典顺序并使用 EPSILON 检查每个“小于”。但是我还有几个问题:

• 这真的有用吗？有什么陷阱吗？
• 规范说明键的相等性，比如 p1 和 p2，由测试 !PlaneCompare(p1,p2) && !PlaneCompare(p2,p1) 确定。如果我使用字典顺序，这应该等同于具有容错性的直接相等测试，但这不是更慢吗？

Answer 1

“是否可以为四个 double (或者甚至只是一个普通的 double )编写一个考虑比较误差容限的哈希函数。”

不，不是。

这听起来像是一个非常明确的陈述，我怎么能这么肯定呢？

假设您需要 0.00001 的公差。该值无关紧要，我们只是将其用作示例。这意味着对于这个哈希函数:

• hash(1.0) 必须返回与 hash(1.00001) 相同的值

这样他们就可以被认为是平等的。但这也意味着:

• hash(1.00001) 必须返回与 hash(1.00002) 相同的值

出于同样的原因，和

• hash(1.00002) 必须返回与 hash(1.00003) 相同的值

...依此类推，直到 double 的最高可能值 - 无限有效。对于小于 1 的值也是如此。

因此任何允许容错的散列函数都必须为所有值返回相同的散列值，这使其毫无用处。

附言要实际推荐一种确实有效的方法，四维四叉树(技术上类似于 sedecimtree)可能是最好的。