散列函数从整数坐标对提供唯一的uint

前端之家收集整理的这篇文章主要介绍了散列函数从整数坐标对提供唯一的uint前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
一般问题:
我有一个很大的2d点空间,人口稀少。
认为它是一个大的白色画布上撒上黑点。
我必须遍历并搜索这些点很多。
帆布(点空间)可以是巨大的,接近极限
int和它的大小在设置点之前是未知的。

这带来了哈希的想法:

理想:
我需要一个采用2D点的哈希函数,返回一个唯一的uint32。
所以不会发生碰撞。你可以假设的数量
画布上的点很容易被uint32计数。

重要事项:事先无法知道画布的大小
(甚至可能会改变)
所以这样的东西

canvaswidth * y x

很遗憾的是这个问题。

我也尝试了一个非常幼稚的

abs(x)abs(y)

但是会产生太多的冲突。

妥协:
一个散列函数,提供非常低的碰撞概率的键。

有什么想法吗感谢任何帮助。

最好的祝福,
安德烈亚斯

编辑:
我不得不在问题文本中改变一些东西:
我改变了“能够计算画布点数”的假设
与uint32“成”能够计数画布上的点(或要存储的坐标对的数量)由uint32。
我原来的问题没有什么意义,因为我会有一个sqrt(max(uint32))xsqrt(max(uint32))大小的画布,这是独一无二的
通过16位移位和OR。

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

对不起,

保证无碰撞的哈希函数不是散列函数:)

您可以考虑使用二进制空间分区树(BSP)或XY树(密切相关)来代替使​​用散列函数

如果要将两个uint32的哈希值混合成一个uint32,不要使用像Y& 0xFFFF因为丢弃一半的位。做某事

(x * 0x1f1f1f1f) ^ y

(您需要首先转换一个变量,以确保哈希函数不可交换)

猜你在找的Windows相关文章