floating-point - 散列浮点向量的好方法？

Question

我很清楚比较 float 所涉及的所有问题。这正是这个问题的原因。
我正在寻找为 3D 向量(3 个浮点数 - x、y、z)的值创建一个快速哈希表。可以假设向量的长度总是1.0(sqrt(x*x+y*y+z*z)是1.0)

从本质上讲，这意味着我正在寻找一个散列函数，该函数采用几乎等于相同 unsigned int 值的值和一个对应的相等运算符，如果散列值相等(不一定只有它们相等)

编辑 ——
误报(即不同但映射到同一个桶的向量)是给定的，因为这是一个哈希表。
假阴性(即接近但映射到不同桶的向量)是不可取的，但似乎没有办法避免它们。就我而言，它们不会导致完全损坏，只会导致一些数据重复，这是我必须忍受的。

Answer 1

我认为你要找的东西不是直接可能的。平等的一个重要特性是它是可传递的。 (即，如果 a == b 和 b == c，则 a == c)。但是，使用距离度量，您确实不想要此属性。例子:

取一个浮点数(为简单起见)。假设我们想要散列每个浮点数，以便小于 1e-3 的浮点数是相同的值。现在，假设我们向这个哈希表添加 1000 个浮点值，所有 1e-4 相隔。任何相邻的 2 个值都应该散列到相同的浮点数，因为它们比 1e-3 更接近。但是，由于传递性，这些值的邻居也应该具有相同的值，以及它们的邻居等等。因此，所有 1000 个值，包括相距超过 1e-3 的对，都将散列到相同的整数。如果要在图片上绘制这些点:

A  B  C  D  E  F  G  H ... Y Z

假设所有间隙相距 < 1e-3，但 A 和 Z 相距 > 1e-3(不按比例!)。这不能被满足，因为如果 hash(A) == hash(B) 和 hash(B) == hash(C) 等等所有对，(因为它们相距 < 1e-3)比 hash(A ) 必须 == 哈希(Z)。

一种可能的选择是定义向量空间的区域，其中所有向量都将散列到相同的值(即在散列它们之前将它们舍入)，但您仍然可以在它们各自空间的边缘上得到 2 个向量，这些向量靠近在一起但散列到不同的值。您可以通过在所有相邻空间中搜索向量来解决这个问题。 (即在上面的 1-d 情况下，您会将所有向量四舍五入到 1e-3 的最近倍数，然后搜索邻居，因此 5.3e-3 将搜索 5e-3、4e-3 和 6-e3。在更高维度的情况下，您必须在所有维度上搜索邻居。)