2011-05-08 79 views
34

散列由IEEE 32位浮点组成的2d和3d矢量的散列函数(快速,分布好,碰撞少)是什么?我假定一般的3d矢量,但是假设法线的算法(总是在[-1,1]中)也是受欢迎的。我也不害怕位操纵,因为IEEE浮动也是IEEE浮动的。散列2D,3D和nD矢量

另一个更普遍的问题是哈希一个Nd浮点向量,其中N非常小(3-12)并且是恒定的,但在编译时不知道。目前,我只是将这些花车作为提示并将它们异或,这可能不是最好的解决方案。

+2

...您是否测试过使用纯XOR方法分配散列的程度?你可能会感到惊讶。 – 2011-05-08 16:33:27

+0

@Matti似乎至少对于3D矢量的分布并不是非常糟糕(在斯坦福大学兔子35k verts上对65537大小的哈希表进行测试)。我只是觉得有人可能有一个更专业的解决方案,因为我前一段时间搜索了网络,并没有发现任何关于该主题的内容。 – 2011-05-08 17:31:48

+0

65537听起来像一个比你可能想要使用的数字更大(或是一个错字) – 2013-09-13 03:12:36

回答

39

存在Optimized Spatial Hashing for Collision Detection of Deformable Objects中描述的空间散列函数。他们使用的哈希函数

哈希(X,Y,Z)=(x p1的XORŸP2 XORž P3)模N

其中P1,P2,P3大 素数,在我们的案例分别为73856093, 19349663,83492791。 值n是哈希表大小。

在论文中,x,y和z是离散化坐标;你大概也可以使用你的浮点数的二进制值。

+14

请注意,19349663不是素数(它是41和471943的乘积) – sehe 2013-09-05 13:20:15

+4

我发现在二维情况下使用质数p1和p3会得到非常好的分布。 – axel22 2016-03-06 21:36:01

+1

当他们写了'x p1 xor y p2 xor z p3'时,他们的意思是'(x * p1)xor(y * p2)xor(z * p3)'还是'x *(p1 xor y)*(p2 xor z)* p3'? – emlai 2016-06-25 15:24:19

8

我有两个建议。

如果你不做量化,它不会对接近度(局部性)敏感。

  • Locality Sensitive Hashing已被提及用于散列更高维向量。为什么不把它们用于3d或2d矢量呢?使用适用于Eucledian距离度量(这是我们需要的2d和3d向量)的LSH变体称为使用p稳定分布的局部敏感散列。一个非常易读的教程是here