具有高空间相干性的3D整数坐标的哈希码

Question

这是我在这些论坛上的第一个问题:)

我正在用Java编写一个空间八叉树体素系统的坐标类.这些坐标不是浮点坐标,它们是进入八叉树的4D整数索引(3个正常尺寸X,Y,Z和第四个深入到树中).前3个值都是短路,最后一个维度是一个字节.在实际使用中,现在只使用短路的前11位,只有3位的字节,但这可能会有所改变.

现在我正在尝试为这个类写一个'好'的哈希函数.我正在努力解决的问题是坐标通常会用于高度空间连贯的情况(希望我在那里使用正确的术语).我的意思是,通常会将坐标与其紧邻的邻居和其他附近坐标进行散列.

是否有一种有效的做法可以使这些"彼此靠近"的坐标产生明显不同的哈希码？

Answer 1

你很幸运:有一种方法可以使用称为Z阶曲线的东西获得具有高空间相干性的正确坐标编码.

诀窍是交错不同坐标分量的比特.所以如果你有3个8位坐标,比如:

[XXXXXXXX, YYYYYYYY, ZZZZZZZZ]

那么z曲线编码值将是一个24位值:

XYZXYZXYZXYZXYZXYZXYZXYZ

您可以根据需要扩展到更大的位数或坐标.

这种编码是有效的,因为在空间上接近的坐标将主要在较低阶位中存在差异.因此,通过交错坐标,您可以将差异集中在编码值的低位.

另一个有趣的特性是较低的位描述了空间立方体内的坐标.所以最低3位地址位置有2x2x2立方体,最低6位地址位置在4*4*4立方体内,最低9位位置在8*8*8立方体内等等所以这实际上是一个非常理想的寻址系统八叉树内的坐标.

Answer 2

“显着不同”实际上取决于您之后对哈希码所做的操作。hash % size在某些情况下，例如，它会通过获取size您正在使用的哈希图的大小来进行循环存储桶选择。显然，这会随着时间的推移而改变。我通常会使用类似的东西：

int hash = 23;
hash = hash * 31 + x;
hash = hash * 31 + y;
hash = hash * 31 + z;
hash = hash * 31 + depth;
return hash;

（基本上，这是从Effective Java(x1, y1, z1)抄袭来的。）显然，这意味着和(x1 + 1, y1 - 31, z1)会有相同的哈希码，但如果您主要担心非常近的邻居，那么这应该不是问题。

编辑： mikera 的答案可能会更好，但编码会更复杂。我个人会首先尝试这种非常简单的方法，看看它是否足以满足您的实际用例。逐步使用更有效但更复杂的方法，直到找到一种足够好的方法。