问题一般: 我有一个很大的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进行唯一表示.
我希望这是可以的,因为所有答案仍然对更新的假设最有意义
对不起.