一般问题: 我有一个很大的二维点空间,里面稀疏地分布着点。 把它想象成一 block 撒满黑点的白色大 Canvas 。 我必须多次迭代和搜索这些点。 Canvas (点空间)可能很大,接近极限 int 的值及其大小在设置点之前是未知的。
这让我想到了哈希的想法:
理想: 我需要一个采用 2D 点的哈希函数,返回一个唯一的 uint32。 这样就不会发生碰撞。 您可以假设 Canvas 上的点可以通过 uint32 轻松计数。
重要:事先不可能知道 Canvas 的大小 (甚至可能会改变), 所以像
Canvas 宽度 * y + x
很遗憾,这是不可能的。
我也尝试过很天真的
abs(x) + abs(y)
但这会产生太多冲突。
妥协: 提供 key 冲突概率非常的哈希函数。
最佳答案
n = ((x + y)*(x + y + 1)/2) + y
可能很有趣,因为它最接近原始的 canvaswidth * y + x,但适用于任何 x 或 y。但对于现实世界中的 int32 哈希,而不是整数对到整数的映射,您可能最好进行位操作,例如 Bob Jenkin 的 mix并用 x,y 和盐来调用它。
关于哈希函数从整数坐标对中提供唯一的 uint,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/682438/