散列浮点向量的好方法？

Question

我很清楚比较浮标所涉及的所有问题。这正是提出这个问题的原因。

我希望为三维向量(3 floats，y，z)的值创建一个快速哈希表。可以假定向量的长度总是1.0 (sqrt(x*x+y*y+z*z)为1.0)。

从本质上说，这意味着我正在寻找一个哈希函数，它的值几乎等于相同的无符号int值，如果散列值相等，则需要相应的相等运算符(而不一定是相等的)。

编辑-

误报(即不同的向量，但映射到同一个桶)是给定的，因为这是一个哈希表。

假否定(即接近但映射到不同桶的向量)是不受欢迎的，但似乎没有办法避免它们。在我的例子中，它们不会导致完全破坏，只是一些数据复制，这是我必须接受的。

Answer 1

我觉得你要找的东西是不可能的。平等的一个重要性质是它是可传递的。(即)如果== b和b == c，那么== c)。不过，用距离度量，你真的不想要这个属性。示例：

接受一个浮点(为简单起见)。假设我们希望散列每个浮点数，使浮点数小于1e-3是相同的值。现在，假设我们将1e-4相隔的1000浮点数添加到这个哈希表中。任何相邻的2值都应该散列到相同的浮点，因为它们比1e-3更接近。然而，由于传递性的存在，这些值的邻域也应该具有相同的值，以及它们的邻居等等。因此，所有1000个值，包括相距大于1e-3的对，都将散列为相同的整数。如果你要在一幅画上画这些点：

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

假设所有的空隙都< 1e-3，但A和Z的间隔都> 1e-3 (不是缩放！)。这是不能满足的，因为对于所有对，如果散列(A)、==散列(B)和散列(B)、==散列(C)等等，(因为它们相距< 1e-3 )，则==散列(A)必须是==散列(Z)。

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

Answer 2

我会将浮点值转换为如下整数：

unsigned int IntValue = (int)(floatValue * MULT) + MULT;

所以你得到一些第一个数字，然后用

const MULT1 = (MULT << 1) + 1;
unsigned long long HashValue = (xIntValue * MULT1  * MULT1) + (yIntValue * MULT1) + zIntValue;

作为散列值(使用(MULT * 2) +1，因为IntValues将介于0和MULT *2之间)。

所需内存将取决于乘法器MULT。例如，使用32可以得到一个哈希表，它使用64 * 64 * 64 *(哈希项大小)= 262144 *(哈希项大小)字节。

Answer 3

有些语言(C、Java 5)允许您访问浮点数的二进制值。通过这种方式，您可以提取尾数的前N位(忽略最后几个在比较期间造成麻烦的位)，并从中计算散列。