散列 2D、3D 和 nD 向量 [英] Hashing 2D, 3D and nD vectors

问题描述

用于散列由 IEEE 32 位浮点数组成的 2d 和 3d 向量的良好散列函数是什么(快速、良好分布、很少冲突).我假设一般的 3d 向量，但也欢迎假设法线(总是在 [-1,1] 中)的算法.我也不害怕位操作，因为 IEEE 浮点数总是 IEEE 浮点数.

What are good hashing functions (fast, good distribution, few collisions) for hashing 2d and 3d vectors composed of IEEE 32bit floats. I assume general 3d vectors, but algorithms assuming normals (always in [-1,1]) are also welcome. I also do not fear bit-manipulation as IEEE floats are alsways IEEE floats.

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

Another more general problem is hashing an Nd float-vector, where N is quite small (3-12) and constant but not known at compile time. At the moment I just take these floats as uints and XOR them together, which is probably not the best solution.

推荐答案

用于可变形物体碰撞检测的优化空间散列.他们使用哈希函数

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

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

其中 p1、p2、p3 较大质数，在我们的例子中是 73856093，分别为19349663、83492791.这值 n 是哈希表大小.

where p1, p2, p3 are large prime numbers, in our case 73856093, 19349663, 83492791, respectively. The value n is the hash table size.

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

In the paper, x, y, and z are the discretized coordinates; you could probably also use the binary values of your floats.

这篇关于散列 2D、3D 和 nD 向量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！