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:
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.
A hash function that provides keys with a very low probability of collision.
Any ideas anybody? Thanks for any help.
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.