31

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

本质上，这意味着我正在寻找一个散列函数，它的值几乎等于相同的 unsigned int 值，并且如果散列值相等，则对应的相等运算符为真（不一定只有它们相等）

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

4

8 回答 8

16

我认为你正在寻找的东西是不可能的。等式的一个重要特性是它是可传递的。（即，如果 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 个向量，它们靠近在一起但散列为不同的值。您可以通过在所有相邻空间中搜索向量来解决此问题。（即在上面的一维情况下，您会将所有向量四舍五入到最接近的 1e-3 倍数，然后搜索邻居，因此 5.3e-3 将搜索 5e-3、4e-3 和 6-e3。在更高维度的情况下，您必须搜索所有维度的邻居。）

于 2009-03-16T12:28:37.183 回答
3

I'd convert the float values into integers like this:

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

so you get some of the first digits and then use

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

as a hash value (using (MULT * 2) + 1 because the IntValues will be between 0 and MULT * 2 inclusive).

The memory needed will be depending on the multiplicator MULT. For example, using 32 you'll get a hashtable using 64 * 64 * 64 * (Hash item size) = 262144 * (Hash item size) bytes.

于 2009-03-16T12:25:38.690 回答
3

某些语言（C、Java 5）允许您访问浮点数的二进制值。这样，您可以提取尾数的前 N ​​位（忽略在比较期间导致问题的最后几位）并从中计算散列。

于 2009-03-16T12:32:00.717 回答
2

我认为您正在有效地尝试解决 K 最近的问题。我相信您正在寻找的是localitysensitive hashing。您也可以使用四叉树结构来实现相同的结果。

于 2012-05-31T15:08:42.457 回答
1

你能详细说明你的问题吗？

假设您使用哈希图将一些附加数据映射到特定向量，您可以只使用组件的二进制表示的 XOR（如果这在您选择的语言中是可能的）。然后根据哈希映射的需要使用尽可能多的 LSB（以减少冲突）。这当然具有两个相等（通过浮点比较）向量可能不具有相同散列的属性（例如，IEEE 浮点 0 等于 -0，但它们具有不同的符号位）。

但是，如果您计划使用作为不同计算结果的向量来进行哈希查找，那么您将自己设置为由于舍入错误而没有匹配哈希码的可能性，并且您可能应该使用其他东西。

于 2009-03-16T12:49:43.327 回答
1

对的，这是可能的。我写了一篇文章如何散列浮点向量和用 Go 语言编写散列浮点向量。

于 2021-12-07T21:22:40.720 回答
0

你需要它是一个快速的哈希表还是树结构？

在我看来，在某种搜索树中查找匹配的浮点数会更容易。假设您选择了正确的节点大小，B-Tree 可以最大限度地减少缓存未命中的数量。这在实践中应该会很快。

于 2010-07-02T08:34:10.793 回答
0

不知道这可能有多快，但是由于您有单位向量，它们都位于球体的表面上。转换为http://en.wikipedia.org/wiki/Spherical_coordinate_system。然后使用 phi 和 theta 来选择一个桶。不会有误报。您可以在相邻单元格中查找假阴性。

于 2010-07-02T08:18:29.717 回答