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

问题一般: 我有一个很大的2d点空间,人口稀少的点.可以把它想象成一个涂有黑点的大白色帆布.我必须迭代并搜索这些点很多.Canvas(点空间)可能很大,接近int的限制,并且在设置点之前它的大小是未知的.

这让我想到了哈希:

理想: 我需要一个带2D点的哈希函数,返回一个唯一的uint32.这样就不会发生碰撞.您可以假设uint32可以轻松计算Canvas上的点数.

重要提示:事先不可能知道画布的大小(甚至可能会改变),所以就像这样

canvaswidth*y + x

遗憾的是,这是不可能的.

我也试过很天真

abs(x)+ abs(y)

但这会产生太多的碰撞.

妥协: 一种散列函数,它提供非常低的碰撞概率.

任何人的想法？谢谢你的帮助.

此致,Andreas T.

编辑:我不得不改变问题文本中的内容:我改变了"能够用uint32计算画布点数"的假设"能够计算画布上的点数(或者要存储的坐标对的数量")通过uint32.我原来的问题没有多大意义,因为我有一个sqrt(max(uint32))xsqrt(max(uint32))大小的画布,它可以通过16位移位和OR进行唯一表示.

我希望这是可以的,因为所有答案仍然对更新的假设最有意义

对不起.

康托尔的对数列举

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

可能很有趣,因为它最接近你的原始canvaswidth*y + x,但适用于任何x或y.但对于真实世界的int32哈希,而不是整数对与整数的映射,你可能会更好地使用一些操作,例如Bob Jenkin的混合,并用x,y和salt调用它.

GUARANTEED无冲突的哈希函数不是哈希函数:)

您可以考虑使用二进制空间分区树(BSP)或XY树(密切相关),而不是使用哈希函数.

如果你想将两个uint32散列到一个uint32中,不要使用像Y和0xFFFF这样的东西,因为它丢弃了一半的位.做点什么

(x * 0x1f1f1f1f) ^ y

(您需要首先转换其中一个变量以确保散列函数不可交换)