散列函数提供整数坐标对的唯一性uint [英] hash function providing unique uint from an integer coordinate pair

问题描述

一般问题：
我有一个很大的2D点空间，里面填充了点。
把它想象成一个洒满黑点的大白色帆布。
我必须迭代并搜索这些点。
Canvas（点空间）可能非常庞大，接近int的限制
，其大小在设置点之前未知。

这让我想到了散列：

理想：
我需要一个采用二维点的散列函数，返回一个独特的UINT32。
这样就不会发生碰撞。 您可以假设画布上
点的数量很容易被uint32计数。

重要提示： strong>不可能事先知道画布的大小
（它甚至可能改变），
所以像

canvaswidth * y + x

令人遗憾地不存在这个问题。

我也尝试过很天真的

abs（x）+ abs（y）

但是会产生太多冲突。

妥协：
提供的键的冲突概率很低。

任何人的想法？感谢您的帮助。

最好的问候，
Andreas T。

编辑：
我必须改变问题文本中的内容：
我改变了能够用uint32计算画布
的点数的假设为能够计算画布上的点（或（uint32）。
我原来的问题没有多大意义，因为我会有一个sqrt（max（uint32））xsqrt（max（uint32））大小的画布，它是唯一的$ 16



$ p

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

对不起。

解决方案

保证无碰撞的散列函数不是一个散列函数：）

代替使用散列函数，可以考虑使用二进制空间分区树（BSP）或XY树（密切相关）。

如果你想散列两个uint32's进入一个uint32，不要使用Y& 0xFFFF因为丢弃了一半的位。做一些像

 （x * 0x1f1f1f1f）^ y 
   b 
 $ b 
（您需要首先转换其中一个变量以确保散列函数不可交换）
The problem in general:
I have a big 2d point space, sparsely populated with dots.
Think of it as a big white canvas sprinkled with black dots.
I have to iterate over and search through these dots a lot.
The Canvas (point space) can be huge, bordering on the limits
of int and its size is unknown before setting points in there.

That brought me to the idea of hashing:

Ideal:
I need a hash function taking a 2D point, returning a unique uint32. 
So that no collisions can occur. You can assume that the number of
dots on the Canvas is easily countable by uint32.

IMPORTANT: It is impossible to know the size of the canvas beforehand
(it may even change),
so things like 

canvaswidth * y + x

are sadly out of the question.

I also tried a very naive 

abs(x) + abs(y) 

but that produces too many collisions.

Compromise:
A hash function that provides keys with a very low probability of collision.

Any ideas anybody? Thanks for any help.

Best regards,
Andreas T.

Edit:
I had to change something in the question text:
I changed the assumption "able to count the number of points of the canvas
with uint32" into "able to count the dots on the canvas (or the number of coordinate pairs to store" by uint32.
My original question didn't make much sense, because I would have had a sqrt(max(uint32))xsqrt(max(uint32)) sized canvas, which is uniquely representable
by a 16 bit shift and OR. 

I hope this is ok, since all answers still make most sense with the updated assumptions

Sorry for that.
解决方案
a hash function that is GUARANTEED collision-free is not a hash function :)

Instead of using a hash function, you could consider using binary space partition trees (BSPs) or XY-trees (closely related).

If you want to hash two uint32's into one uint32, do not use things like Y & 0xFFFF because that discards half of the bits. Do something like
(x * 0x1f1f1f1f) ^ y
(you need to transform one of the variables first to make sure the hash function is not commutative)

                        
这篇关于散列函数提供整数坐标对的唯一性uint的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！