散列2D,3D和nD向量

Question

对于由IEEE 32位浮点数组成的散列2d和3d向量,有什么好的散列函数(快速,良好的分布,很少的碰撞).我假设一般的3d向量,但假设法线(始终在[-1,1])的算法也是受欢迎的.我也不担心比特操纵,因为IEEE浮动也是IEEE浮动.

另一个更普遍的问题是散列Nd浮点向量,其中N非常小(3-12)并且是常量但在编译时不知道.目前我只是将这些花车作为uint并将它们混合在一起,这可能不是最好的解决方案.

Answer 1

在可变形对象的碰撞检测的优化空间散列中描述了空间散列函数.他们使用哈希函数

hash(x,y,z)=(x p1 xor y p2 xor z p3)mod n

其中p1,p2,p3是大素数,在我们的例子中分别是73856093,19349663,83492791.值n是哈希表大小.

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

Answer 2

我有两个建议.

• 假设大小为l的网格单元并通过计算ix = floor(x/l),iy = floor(y/l)和iz = floor(z/l)来量化x,y和z坐标,其中ix ,iy和iz是整数.现在使用优化空间散列中定义的散列函数进行可变形对象的碰撞检测

如果你不进行量化,它就不会对亲密度(局部性)敏感.

• 已经提到了用于散列更高维向量的局部敏感散列.为什么不将它们用于3d或2d矢量？使用适应于Eucledian距离度量(我们需要2d和3d向量)的LSH的变体被称为使用p稳定分布的局部敏感哈希.这里有一个非常易读的教程.