哈希函数从整数坐标对中提供唯一的 uint

Question

一般问题:我有一个很大的二维点空间，里面稀疏地分布着点。把它想象成一 block 撒满黑点的白色大 Canvas 。我必须多次迭代和搜索这些点。 Canvas (点空间)可能很大，接近极限int 的值及其大小在设置点之前是未知的。

这让我想到了哈希的想法:

理想:我需要一个采用 2D 点的哈希函数，返回一个唯一的 uint32。这样就不会发生碰撞。 您可以假设 Canvas 上的点可以通过 uint32 轻松计数。

重要:事先不可能知道 Canvas 的大小(甚至可能会改变)，所以像

Canvas 宽度 * y + x

很遗憾，这是不可能的。

我也尝试过很天真的

abs(x) + abs(y)

但这会产生太多冲突。

妥协:提供 key 冲突概率非常的哈希函数。

Answer 1

康托尔的enumeration of pairs

   n = ((x + y)*(x + y + 1)/2) + y

可能很有趣，因为它最接近原始的 canvaswidth * y + x，但适用于任何 x 或 y。但对于现实世界中的 int32 哈希，而不是整数对到整数的映射，您可能最好进行位操作，例如 Bob Jenkin 的 mix并用 x,y 和盐来调用它。