对于由计算出的双精度值组成的键，在 map 或 unordered_map 之间进行选择。

Question

为了在 3d 中的一堆平面实体中快速找到共面实体 space，我想创建一个从 3d 平面到位于该平面中的实体集的映射（估计最大值约为 ~1000平面和约 100000 个实体）

我可以创建自己的自定义 class 来表示 3D 平面键，但基本上这个 class 需要（在数学上）四个双打来唯一标识一个平面：3 个法向量坐标和一个坐标来指定平面上的一个点。所以我们有：

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

这四个双打每次都是从所考虑的实体计算的，因此必须考虑舍入误差和浮点数比较问题。假设我已经计算出一个合适的（相对）容错度：

const double EPSILON;

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

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

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

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

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

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

PlaneCompare 仿函数听起来可行，我可以使用四个双打的字典顺序并使用 EPSILON 检查每个 "less than"。但是我还有几个问题：

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

Answer 1

"is it possible to write a Hash function for four doubles (or even just a regular double) that takes a comparison error tolerance into account."

不，不是。

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

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

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

出于同样的原因，

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

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

P.S。要实际推荐一种有效的方法，四维四叉树（技术上类似于 sedecimtree）可能是最好的。

Answer 2

你可以四舍五入你的双打，例如[n - epsilon, n + epsilon) 范围内的所有值都四舍五入为 n，其中 n mod epsilon == 0，并对其进行哈希处理。在这种情况下，您的接近值将具有相同的哈希值。

如何更好地哈希 4 个双精度值取决于您的情况，但即使对它们求和也足够好。

choice between map or unordered_map for keys consisting of calculated double values.